TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Рисуем фракталы
Что ты узнаешь
- Фрактал это фигура из уменьшенных копий самой себя: дерево это ствол с двумя деревьями поменьше наверху.
- Глубина рекурсии это сколько уровней копий рисуется. Глубина 0 это базовый случай: одна палочка.
- У дерева глубины d 2^d кончиков: ещё один уровень их удваивает.
- Кривая Коха превращает каждую палочку в 4 палочки втрое короче, поэтому каждый уровень умножает её длину на 4/3.
Как идёт урок
Папоротники, брокколи, молнии. Почему так многое похоже на уменьшенные копии себя?
Этот папоротник нарисовала программа. Приблизь один из его боковых листьев.
Дерево это ствол с двумя деревьями поменьше наверху.
Дотяни глубину до 3 и посчитай кончики.
У этого дерева глубина 3 и 8 кончиков. Сколько кончиков на глубине 6?
Каждый кончик дерева глубины 5 получает две ветки на глубине 6. Поэтому кончики идут 1, 2, 4, 8, 16, 32, 64: 2 в степени глубины.
Фракталы и глубина рекурсии.
Фрактал это фигура, построенная из уменьшенных копий себя. Код рисует его рекурсией: нарисуй кусочек, потом вызови себя, поменьше.
Глубина рекурсии это на сколько уровней вглубь идут вызовы. Глубина 0 это базовый случай: нарисуй одну палочку и остановись.
Удвоение на каждом уровне объясняет, почему фракталы так быстро становятся подробными: на глубине 10 уже 1024 кончика.
Придумай своё дерево.
Меняй угол между ветками и то, насколько каждая уменьшается.
Смотри, как код рисует твоё дерево.
Перо следует за tree(depth, length). Заметь, какие ветки идут первыми.
tree(4) не может нарисовать правую ветку, пока tree(3) слева не закончит всё, а тот ждёт tree(2) и так далее. Поэтому перо сначала забирается к самому левому кончику.
Собери правило Коха: одна палочка становится четырьмя.
Четыре одинаковые палочки втрое короче: ровно, вверх к пику, вниз, ровно. Потом правило работает на каждой палочке.
Первая палочка длиной 1. Какой длины кривая Коха после 3 уровней?
Каждый уровень: 4 палочки, каждая втрое короче. Засчитывается с точностью до 0,08.
Каждая палочка становится 4 палочками втрое короче: 4/3 прежней длины. Три уровня: (4/3)^3 = 64/27, около 2,37. Это геометрическая прогрессия.
Цели по кончикам: вырасти дерево ровно до 32 кончиков, потом до 128.
Задай глубину и нажми «Вырастить». Побеждает меньше попыток.
Предыдущий урок: Ханойские башни · Следующий урок: Разделяй и властвуй · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
