Введение: визуализация рекурсии¶

В предыдущих разделах мы рассматривали задачи, которые могут быть легко решены с помощью рекурсии. Однако, найти ментальную модель или способ визуализации того, что происходит с рекурсивной функцией, по-прежнему непросто. Это делает рекурсию трудной для понимания. Поэтому в данной части мы рассмотрим несколько примеров использования рекурсии для рисования неких любопытных изображений. В процессе “прорисовки” этих картинок вы получите новое понимание рекурсивных процессов, что может быть полезным для закрепления вашего понимания рекурсии в целом.

Для наших иллюстраций мы воспользуемся графическим модулем Python под названием turtle. Он входит в стандартный набор модулей для всех версий Python и очень прост в применении. Метафора, объясняющее его название (turtle (англ.) - черепаха) крайне проста: вы можете создать черепаху, которая умеет двигаться вперёд-назад, поворачивать направо-налево и т.п. У неё есть хвост, который она может поднимать или опускать. Когда черепаший хвост опущен и она движется, то он рисует линию. Чтобы увеличить художественную ценность черепахи, вы можете менять толщину хвоста и цвет чернил, в которые он был окрашен.

Вот простой пример, показывающий основы “черепашьего рисования”. Мы используем модуль turtle, чтобы рекурсивно нарисовать спираль. ActiveCode 1 показывает, как это делается. После подключения модуля turtle создаётся черепаха, вместе с которой появляется и окно для рисования. Потом мы определяем функцию drawSpiral. Её базовым случаем будет момент, когда длина линии, которую мы хотим нарисовать (параметр len), станет меньшей или равной нулю. Если же она больше нуля, то мы даём черепахе задание пройти len единиц, а затем повернуть на 90 градусов. Рекурсивным шагом будет вызов drawSpiral с уменьшенной длиной. В конце ActiveCode 1 вы увидитевызов функции myWin.exitonclick(). Она управляет маленьким оконным методом, который переводит черепаху в режим ожидания до тех пор, пока вы не кликните внутри окна. После этого программа очистит полотно и закроется.

Вот и всё о “черепашьей графике”, что вам нужно знать для рисования некоторых довольно впечатляющих картинок. В нашей следующей программе мы собираемся изобразить фрактальное дерево. Фракталы - это одна из ветвей математики, и они имеют с рекурсией много общего. Определение фрактала заключается в том, что вне зависимости от приближения он всегда содержит некоторую основную фигуру. Примерами из живой природы могут послужить береговые линии континентов, снежинки, горы и даже деревья или кустарники. Фрактальная природа этих объектов позволяет программистам генерировать очень реалистично выглядящие пейзажи для компьютерных изображений. Да и мы в следующем примере будем генерировать фрактальное дерево.

Чтобы понять, как всё это работает, полезно подумать над тем, как можно описать дерево, используя терминологию фракталов. Вспомните, что мы говорили выше: фрактал - это то, что выглядит одинаково на всех уровнях увеличения. Транслируя эту мысль на деревья и кустарники, можно сказать, что даже самая маленькая веточка имеет ту же форму и характеристики, что и целое дерево. Т.е. можно сказать, что дерево - это ствол от которого вправо и влево отходят меньшие деревья. Если вы подумете об этом определении, то поймёте, что его можно рекурсивно применить и для меньших правого и левого деревьев.

Давайте переведём эти мысли в код на Python. Листинг 1 демонстрирует, как можно использовать нашу черепаху для генерации фрактального дерева. Посмотрим на код поближе. Хорошо видно, что рекурсивные вызовы делаются в строках 5 и 7. В строке 5 сразу после него черепаха поворачивает вправо на 20 градусов - это правое дерево. Затем в строке 7 вновь делается рекурсивный вызов, но в этот раз с поворотом влево на 40 градусов. Выбор этого числа связан с необходимостью скомпенсировать уже сделанный поворот на 20 градусов, а затем повернуть ещё на 20 влево с целью нарисовать левое дерево. Также обратите внимание, что при каждом рекурсивном вызове tree мы вычитаем из параметра branchLen некую величину. Это делается для того, чтобы рекурсивные деревья становились всё меньше и меньше. Вы также можете разобраться, что первоначальный оператор if в строке 2 проверяет базовый случай: branchLen стала слишком маленькой.

Листинг 1

1
2
3
4
5
6
7
8
9

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-10,t)
        t.right(20)
        t.backward(branchLen)

Полностью программа для примера с деревом показана в ActiveCode 2. До того, как вы запустите её, подумайте: как должно выглядеть дерево? Посмотрите на рекурсивные вызовы и представьте, как оно будет разворачиваться. Будут ли его правая и левая части рисоваться симметрично и одновременно? Или сначала нарисуется правая, а затем левая половина?

Обратите внимание, как каждая точка разветвления соотносится с рекурсивным вызовом и как дерево прорисовывается вправо до самой короткой веточки. Вы можете это увидеть на рисунке 1. А теперь посмотрите, как программа работает в обратном направлении - к стволу, - когда нарисована вся правая часть. Вы можете увидеть правую половину дерева на рисунке 2. Затем рисуется левая сторона дерева, но не от самой левой её части. Вместо этого вновь прорисовывается правая сторона левого дерева, и так до тех пор, пока не будет создана самая маленькая левая ветвь.

Рисунок 1: Начало фрактального дерева.

Рисунок 2: Первая половина фрактального дерева.

Эта простая программа - всего лишь точка отсчёта для вас. Легко заметить, что дерево не выглядит особенно реалистичным, поскольку природа не настолько симметрична, как компьютерные программы. Упражнения в конце этой главы подадут вам несколько идей для исследования интересных опций, позволяющих вашему дереву выглядеть более натурально.