Кривая дракона
Фрактальная кривая, которая получается, если многократно складывать полоску бумаги пополам и затем развернуть все сгибы под прямым углом. Строится двумя взаимно рекурсивными алгоритмами.
Разбор
Перемещаем черепаху влево, чтобы кривая поместилась на поле, и запускаем построение с глубиной 14 и шагом 8:
использовать Черепаха
алг
нач
поднять хвост
назад(90)
опустить хвост
дракон(14, 8.0)
кон
Алгоритм дракон --- первая половина взаимной рекурсии. Базовый случай ($n = 0$) --- просто шаг вперёд. На каждом уровне рекурсии алгоритм вызывает сам себя для первой половины, поворачивает налево на $90°$ и вызывает зеркальный алгоритм крыла для второй:
алг дракон(цел n, вещ step)
нач
если n = 0 то
вперед(step)
иначе
дракон(n - 1, step)
влево(90)
крыла(n - 1, step)
все
кон
Алгоритм крыла --- зеркальная копия дракон. Он тоже вызывает дракон для первой части, но поворачивает направо на $90°$ и вызывает сам себя для второй:
алг крыла(цел n, вещ step)
нач
если n = 0 то
вперед(step)
иначе
дракон(n - 1, step)
вправо(90)
крыла(n - 1, step)
все
кон
Взаимная рекурсия означает, что дракон вызывает крыла, а крыла вызывает дракон. Разница только в направлении поворота --- влево или вправо. Именно это создаёт характерный узор, который никогда не пересекает сам себя. На глубине 14 кривая состоит из $2^{14} = 16384$ отрезков.
Полная программа
использовать Черепаха
алг
нач
поднять хвост
назад(90)
опустить хвост
дракон(14, 8.0)
кон
алг дракон(цел n, вещ step)
нач
если n = 0 то
вперед(step)
иначе
дракон(n - 1, step)
влево(90)
крыла(n - 1, step)
все
кон
алг крыла(цел n, вещ step)
нач
если n = 0 то
вперед(step)
иначе
дракон(n - 1, step)
вправо(90)
крыла(n - 1, step)
все
кон