Рекурсия

Многие данные устроены вложенно: папка содержит папки, рубрика — подрубрики, пункт меню — подпункты, комментарий — ответы на него. Обходить такую структуру циклом неудобно, потому что заранее неизвестно, сколько уровней вложенности будет. Рекурсивная функция решает задачу для одного уровня и поручает следующий уровень самой себе.

Любая рекурсия держится на двух частях. Базовый случай — условие, при котором функция возвращает результат без новых вызовов. Шаг — вызов себя для уменьшенной задачи. Если базового случая нет или он недостижим, вызовы будут копиться до исчерпания памяти.

Пример: дерево рубрик на PHP

Есть плоский массив рубрик, у каждой указан родитель. Функция печатает дерево с отступами:

function printTree(array $items, int $parent = 0, int $level = 0): void
{
    foreach ($items as $item) {
        if ($item['parent'] === $parent) {
            echo str_repeat('— ', $level) . $item['name'] . PHP_EOL;
            printTree($items, $item['id'], $level + 1);
        }
    }
}

Здесь базовый случай неявный: если у рубрики нет детей, цикл не найдёт совпадений и функция просто завершится. По похожему принципу класс Walker в WordPress обходит вложенные меню и рубрики.

Цена рекурсии

Каждый вызов занимает место в стеке вызовов: там хранятся аргументы и место возврата. При слишком глубокой рекурсии стек заканчивается. В JavaScript это ошибка «Maximum call stack size exceeded», в Python по умолчанию срабатывает ограничение примерно в тысячу уровней, в PHP скрипт упирается в лимит памяти.

Вторая проблема — повторные вычисления. Наивная рекурсивная функция для чисел Фибоначчи многократно считает одни и те же значения. Это лечится мемоизацией: результаты сохраняются и переиспользуются.

Когда лучше цикл

Если вложенность линейная, например нужно пройти по списку или посчитать сумму, обычный цикл проще и не расходует стек. Рекурсию стоит выбирать там, где структура данных сама по себе рекурсивна: деревья, графы, вложенные JSON-объекты, алгоритмы «разделяй и властвуй».