Рекурсия: рисуем фрактальное дерево

Сегодня одна короткая функция нарисует целое дерево — потому что научится вызывать саму себя.

Рекурсия — это когда функция, решая задачу, вызывает саму себя для куска поменьше. Большое дерево — это всего лишь ствол плюс два дерева поменьше на его конце.

Помнишь, как в прошлом уроке мы сохраняли и восстанавливали систему координат через push() и pop()? Сегодня этот приём наконец заиграет в полную силу. Мы соберём из него фрактальное дерево — и подарим нашему CodeChick настоящее гнездо на ветвях.

Зачем цыплёнку дерево

Представь: ты открываешь любимую игру, и там на фоне качаются деревья. Сотни веточек, листики, всё разное — кажется, художник рисовал это неделю. А теперь секрет: очень часто такие деревья рисует не художник, а маленький кусочек кода, который умеет одну вещь — рисовать ветку. Просто он делает это снова, и снова, и снова, каждый раз чуть-чуть меняя масштаб.

Вот к чему мы придём за этот урок:

function setup() {
  createCanvas(600, 600);
}

function draw() {
  background(135, 206, 235); // небо
  stroke(90, 60, 40);        // цвет коры
  translate(width / 2, height); // встаём в центр снизу
  branch(150);                  // рисуем ствол длиной 150
  noLoop();                     // дерево статичное — один кадр
}

function branch(len) {
  strokeWeight(map(len, 4, 150, 1, 10));
  line(0, 0, 0, -len);   // ветка вверх
  translate(0, -len);    // переезжаем на её конец

  if (len > 4) {         // базовый случай: совсем короткие не делим
    push();
    rotate(0.4);
    branch(len * 0.67);  // правое поддерево
    pop();

    push();
    rotate(-0.4);
    branch(len * 0.67);  // левое поддерево
    pop();
  }
}

Результат: на голубом небе из центра нижнего края растёт коричневое дерево. Толстый ствол раздваивается на две ветки потоньше, каждая — ещё на две, и так далее, пока веточки не станут тонкими, как волоски. Получается пышная симметричная крона. И всё это нарисовала одна функция branch в дюжину строк.

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

Что такое рекурсия (на пальцах)

Представь два зеркала напротив друг друга. Ты встаёшь между ними — и видишь коридор из отражений, который уходит в бесконечность. Каждое отражение содержит внутри себя такое же отражение, только чуть меньше. Зеркало не рисует весь коридор сразу — оно просто отражает то, что перед ним, а остальное делает соседнее зеркало.

Ещё один пример из жизни: матрёшка. Открываешь большую куклу — внутри такая же, но поменьше. Открываешь её — снова такая же. И так до самой маленькой, которая уже не открывается. Маленькая неоткрывающаяся матрёшка — это и есть точка остановки, до которой мы скоро доберёмся. А сам принцип «внутри большого спрятано такое же, но меньше» — это рекурсия.

Рекурсия работает точно так же. Это функция, которая вызывает сама себя, чтобы решить кусок задачи поменьше. А тот вызов снова вызывает себя для куска ещё меньше. И так до тех пор, пока кусок не станет таким крошечным, что решается без всякого деления.

Думай про дерево так:

Дерево = ствол + два дерева поменьше, растущие с его верхушки.

Заметь, как хитро устроено это определение: внутри слова «дерево» снова есть слово «дерево». Это и есть рекурсия в чистом виде. Мы описываем большую штуку через её же уменьшенную копию.

Базовый случай — кнопка «стоп»

У двух зеркал отражения тускнеют и в какой-то момент пропадают — иначе коридор был бы и правда бесконечным. У рекурсии должна быть такая же точка остановки, иначе функция будет вызывать себя вечно и программа зависнет.

Эта точка называется базовый случай — условие, при котором функция больше не зовёт себя, а просто заканчивает работу. В нашем дереве базовый случай прячется в строке if (len > 4): пока ветка длиннее четырёх пикселей — делим её дальше; как только короче — рисуем последнюю веточку и останавливаемся.

Запомни главное правило: у каждой рекурсии обязан быть базовый случай, и каждый новый вызов должен приближать нас к нему. В дереве мы приближаемся, потому что каждый раз умножаем длину на 0.67 — ветки неизбежно становятся короче и рано или поздно пробьют порог в 4 пикселя.

Стек вызовов — стопка тарелок

Когда функция вызывает сама себя, старый вызов не исчезает — он ставится «на паузу» и ждёт, пока новый закончит. Эти приостановленные вызовы складываются в стопку, которую называют стеком вызовов. Представь стопку тарелок: ты кладёшь новую тарелку сверху (новый вызов branch), а убираешь всегда только верхнюю (вызов завершился — тарелку сняли). Это ровно тот же стек, что прячется за push() и pop(), с которым ты уже знаком.

Почему это важно знать? Потому что у стопки есть предел высоты. Если базовый случай не сработает, тарелки будут накапливаться без конца — и в какой-то момент стопка рухнет. Браузер скажет тебе об этом ошибкой «переполнение стека». Так что базовый случай — это не формальность, а буквально то, что не даёт стопке тарелок вырасти до потолка.

Разбираем дерево по веткам

Пример 1. Одна ветка без рекурсии

Начнём с самого скромного — нарисуем одну-единственную ветку, ещё без всякого самовызова. Это фундамент, на котором держится всё остальное.

function setup() {
  createCanvas(600, 600);
}

function draw() {
  background(135, 206, 235);
  stroke(90, 60, 40);
  strokeWeight(8);
  translate(width / 2, height); // в центр нижнего края
  line(0, 0, 0, -150);          // линия вверх на 150 пикселей
}

Результат: на голубом небе из середины нижнего края торчит вертикальная коричневая палка длиной 150 пикселей. Пока это просто ствол без веток.

Разберём построчно:

• translate(width / 2, height) — сдвигаем начало координат в центр по горизонтали и в самый низ. Теперь точка (0, 0) — это основание будущего дерева.
• line(0, 0, 0, -len) — рисуем линию из текущего нуля вверх. Помни: ось Y направлена вниз, поэтому минус ведёт ветку вверх.

Пример 2. Превращаем ветку в функцию, которая зовёт себя

Теперь главный фокус. Завернём рисование ветки в функцию branch(len) и заставим её после рисования вызвать саму себя для двух веток поменьше.

function branch(len) {
  line(0, 0, 0, -len); // 1. рисуем текущую ветку
  translate(0, -len);  // 2. переезжаем на её верхушку

  if (len > 4) {       // 3. базовый случай: если ветка ещё длинная
    push();            // запомнили систему координат
    rotate(0.4);       // повернули вправо на ~23 градуса
    branch(len * 0.67);// вызвали себя для ветки покороче
    pop();             // вернули координаты обратно

    push();
    rotate(-0.4);      // повернули влево
    branch(len * 0.67);// и ещё раз — для левой ветки
    pop();
  }
}

Результат: функция рисует ветку, переезжает на её конец и, если ветка достаточно длинная, выпускает из верхушки две ветки поменьше — одну вправо, одну влево. Каждая из них делает то же самое. Так из одного вызова вырастает целое дерево.

Самое важное здесь — танец push() / rotate() / pop(). Без него ветки бы накапливали повороты и улетали в одну сторону спиралью. Давай распишем, что происходит у верхушки ствола:

1. push() — сохраняем текущую систему координат (мы на верхушке, смотрим вверх).
2. rotate(0.4) — наклоняем мир вправо. Теперь «вверх» для дочерней ветки — это вправо-вверх.
3. branch(len * 0.67) — рисуем правое поддерево целиком в этом наклонённом мире.
4. pop() — возвращаемся ровно туда, где были до наклона.
5. Повторяем с rotate(-0.4) для левой ветки.

Метафора: push() — это как поставить закладку в книге перед тем, как уйти читать другую главу. pop() — вернуться к закладке, будто никуда и не уходил. Каждая ветка уходит в свою «главу» рисования и возвращает координаты в исходное состояние, чтобы соседка стартовала с того же места.

Давай мысленно проследим самый первый шаг. Ствол длиной 150 рисуется и заканчивается на высоте 150 над землёй. Мы переезжаем туда через translate. Дальше первый push запоминает эту точку, мы наклоняемся вправо и зовём branch(100) (это примерно 150 умножить на 0.67). Внутри этого вызова всё повторяется: рисуется ветка длиной 100, мы снова переезжаем на её конец, снова делимся надвое... и так вглубь, пока длина не упадёт ниже четырёх. Только когда самая глубокая правая веточка дорисована, цепочка pop разворачивается обратно — и мы оказываемся ровно на верхушке ствола, готовые рисовать левую половину дерева. Вот эта способность «нырнуть глубоко, а потом аккуратно вернуться» и делает рекурсию такой удобной для ветвящихся структур.

Пример 3. Гнездо для CodeChick на верхушке

Дерево есть — пора поселить на нём нашего героя. Добавим в базовый случай рисование гнезда: когда ветка стала совсем короткой, вместо нового деления нарисуем маленькую тёплую точку-гнездо. А на главной верхушке посадим самого цыплёнка.

function setup() {
  createCanvas(600, 600);
}

function draw() {
  background(135, 206, 235);
  translate(width / 2, height);
  stroke(90, 60, 40);
  branch(150);
  noLoop();
}

function branch(len) {
  strokeWeight(map(len, 4, 150, 1, 10));
  line(0, 0, 0, -len);
  translate(0, -len);

  if (len > 4) {
    push();
    rotate(0.4);
    branch(len * 0.67);
    pop();
    push();
    rotate(-0.4);
    branch(len * 0.67);
    pop();
  } else {
    // базовый случай: кончик ветки — рисуем гнездо
    noStroke();
    fill(150, 100, 60); // бурое гнездо
    ellipse(0, 0, 6, 4);
    fill(255, 215, 0);  // жёлтый цыплёнок
    ellipse(0, -3, 4, 4);
    stroke(90, 60, 40);
  }
}

Результат: то же пышное дерево, но теперь толщина ветвей плавно убывает от толстого ствола к тоненьким кончикам (за это отвечает map). А на конце каждой самой маленькой веточки сидит крошечное бурое гнездо с жёлтой точкой-цыплёнком внутри. Десятки маленьких CodeChick рассыпаны по всей кроне, как игрушки на новогодней ёлке.

Обрати внимание: мы вынесли рисование гнезда в else. То есть когда ветка перестаёт делиться (базовый случай), она не остаётся голой — она получает гнездо. Так базовый случай не просто «ничего не делает», а становится самой красивой частью картинки.

Частые ошибки и подводные камни

Рекурсия — мощная, но коварная. Вот на чём спотыкаются почти все новички (и иногда не новички тоже).

1. Забыл базовый случай — браузер завис

Если убрать if (len > 4) и звать branch всегда, функция будет вызывать себя бесконечно. Браузер либо намертво подвиснет, либо выдаст ошибку Maximum call stack size exceeded («стек вызовов переполнен»). Это самый частый и самый болезненный баг рекурсии. Сначала пиши условие остановки, потом — самовызов.

2. Базовый случай есть, но к нему не приближаешься

Допустим, ты написал if (len > 4), но в самовызове забыл уменьшить длину и оставил branch(len). Условие вроде бы есть, но len никогда не меняется — значит, порог никогда не пробьётся. Результат тот же: бесконечный цикл. Каждый вызов обязан придвигать тебя к базовому случаю — у нас это len * 0.67.

3. Потерял push() и pop()

Если убрать пары push() / pop(), повороты rotate начнут накапливаться. Правая ветка повернётся, левая повернётся ещё сильнее относительно неё, и вместо дерева ты получишь скрученную спираль или хаос из линий. Запомни: каждому push() нужен ровно один pop(), иначе система координат «уплывёт».

4. Слишком большой коэффициент — экспоненциальный взрыв

Дерево с двумя ветками на каждом шаге растёт экспоненциально: 1 ветка, потом 2, потом 4, 8, 16... Если поставить очень маленький множитель уменьшения (например, len * 0.95) и низкий порог остановки, вызовов станут десятки тысяч, и скетч начнёт тормозить. Держи множитель в районе 0.6–0.75 и не опускай порог ниже 2–4 пикселей.

5. Перепутал знак угла или оси Y

Если написать line(0, 0, 0, len) вместо -len, дерево вырастет вниз, под землю. А если оба rotate сделать с одинаковым знаком, обе ветки уйдут в одну сторону, и дерево скособочится. Помни: Y растёт вниз, поэтому ветки рисуем в минус, а для симметрии один поворот делаем положительным, другой — отрицательным.

Мини-практика: вырасти своё дерево

Теперь твоя очередь. Возьми код из примера 3 и поэкспериментируй — рекурсия особенно благодарна к экспериментам, потому что одно изменённое число меняет всё дерево целиком.

• Поиграй с углом. Поменяй 0.4 на 0.2 — дерево станет узким и устремлённым вверх, как тополь. Поставь 0.9 — получится раскидистый, почти круглый куст.
• Добавь живости. Вместо жёсткого rotate(0.4) напиши rotate(0.4 + random(-0.1, 0.1)). Каждая ветка чуть-чуть отклонится по-своему, и дерево станет живым и неровным, как настоящее. (Случайность мы проходили раньше — самое время её вспомнить.)
• Сделай три ветки вместо двух. Добавь третий блок push() / rotate(0) / branch(len * 0.67) / pop() — пусть из каждой верхушки растёт ещё и прямая ветка по центру.
• Преврати дерево в осеннее. В базовом случае вместо гнезда рисуй маленький жёлто-оранжевый листик: fill(random(200, 255), random(120, 180), 40).

Цель-максимум: добиться, чтобы дерево выглядело так, будто на нём и правда могла бы жить стая маленьких CodeChick. Поменяй пару чисел, посмотри на результат, поменяй ещё — это и есть креативное кодирование.

Если хочется челлендж посерьёзнее — попробуй сделать дерево несимметричным: пусть правая ветка укорачивается множителем 0.7, а левая — 0.6. Левая половина станет компактнее, и дерево будто бы наклонится на ветру. А ещё можно завести у функции второй параметр — угол — и передавать его внутрь вместо жёсткого числа 0.4. Тогда одной строкой в draw ты сможешь управлять «характером» всего дерева. Не бойся сломать: рекурсию очень легко вернуть назад, ведь весь рисунок живёт в одной маленькой функции.

Итоги

Сегодня ты приручил одну из самых красивых идей в программировании.

• Рекурсия — это функция, которая вызывает саму себя для задачи поменьше.
• Базовый случай — обязательное условие остановки; без него программа зависнет.
• Каждый самовызов должен приближать к базовому случаю (у нас длина каждый раз умножается на 0.67).
• Пары push() / pop() позволяют каждой ветке рисоваться в своей системе координат и не ломать соседям.
• Из одной крошечной функции branch вырастает целое дерево — это и есть сила рекурсии.

Ты уже умеешь сдвигать, поворачивать и масштабировать мир, сохранять его состояние стеком, а теперь ещё и строить сложные структуры из самоповторения. Дальше мы соберём всё это вместе и заставим наши трансформации двигаться во времени — превратим статичное дерево в анимацию, где ветки качаются на ветру, а CodeChick покачивается в своём гнезде. Увидимся в следующем уроке!