Что такое рекурсия — функция, которая зовёт саму себя (и где у неё дно)

Если ты хоть раз видел в консоли красное Maximum call stack size exceeded или RecursionError — ты уже встречался с рекурсией. Просто с той, у которой забыли сделать дно. Смешное тут вот что: рекурсия — это не про умный код, а про задачи, которые содержат сами себя. Папки внутри папок. Комментарии к комментариям. Разберёмся за пять минут.
Что такое рекурсия простыми словами
Рекурсия — это когда функция вызывает саму себя, чтобы решить кусочек той же задачи поменьше.
Аналогия — матрёшка. Чтобы «открыть матрёшку», надо открыть её и проделать то же самое с той, что внутри. И так далее — пока не дойдёшь до самой маленькой, цельной, которая не открывается. Вот эта последняя и есть дно.
Смотри на живой пример: тебе надо посчитать все файлы в папке. Внутри неё лежат другие папки, внутри тех — ещё. Ты не знаешь заранее, насколько глубоко. Циклом такое писать больно, а рекурсией задача формулируется в одну фразу: «файлов в папке — это файлы прямо здесь плюс файлы в каждой вложенной папке, посчитанные тем же способом».
Два обязательных куска: дно и шаг к нему
Любая рабочая рекурсия состоит ровно из двух частей. Если одной нет — программа падает.
- Базовый случай — ситуация, где функция отвечает сразу, никого не вызывая. Это дно. Для матрёшки — самая маленькая. Для папок — «вложенных папок больше нет».
- Шаг к дну — каждый следующий вызов должен работать с задачей строго меньше предыдущей. Иначе ты будешь бесконечно вызывать то же самое.
Вот классика на десять строк — сумма чисел от 1 до n:
function sum(n) {
if (n === 0) return 0; // базовый случай: дно
return n + sum(n - 1); // шаг к дну: задача стала меньше
}
sum(4); // 4 + 3 + 2 + 1 + 0 = 10
Убери первую строку — и функция будет уходить в минус бесконечно. Оставь первую, но напиши sum(n) вместо sum(n - 1) — то же самое: задача не уменьшается, дна не достичь.
Откуда берётся ошибка про стек
Каждый незавершённый вызов функции занимает место в стеке вызовов — это та самая стопка, которую ты видишь в стек-трейсе при падении. Пока sum(4) ждёт ответа от sum(3), он лежит в стопке. Стопка не бесконечная: в Python по умолчанию около тысячи уровней, в браузерном JavaScript — обычно несколько тысяч, зависит от движка.
Дошёл до потолка — получаешь RecursionError или Maximum call stack size exceeded. Практически всегда это значит одно: дна нет или до него не доходят. Не увеличивай лимит — почини условие выхода.
Где ты встретишь рекурсию на самом деле
Не в задачках про факториал, а в данных, у которых форма дерева:
- Файлы и папки. Обойти проект целиком, найти все картинки.
- JSON любой вложенности. Объект внутри объекта внутри массива — обход одной функцией.
- Комментарии с ответами. Ветка ответов на ответы на любую глубину.
- HTML-страница. Элемент внутри элемента — та же матрёшка, поэтому обход страницы почти всегда рекурсивный.
- Меню и категории. Раздел, подраздел, под-подраздел.
Общий признак простой: если объект содержит объекты того же вида — почти наверняка удобнее рекурсия.
Когда рекурсия — плохая идея
Честно: чаще, чем кажется новичкам.
- Простой перебор списка — бери обычный цикл. Он быстрее, понятнее и не грозит стеком.
- Очень глубокая вложенность — тысячи уровней стек не переварит; такое пишут циклом со своим списком «что осталось обойти».
- Тебе тяжело её читать — это не стыдно. Рекурсивный код короче, но держать его в голове труднее.
И отдельная просьба: если ИИ написал тебе рекурсию, первым делом найди глазами базовый случай. Это самое частое место, где сгенерированный код выглядит красиво и не работает.
Рекурсия медленнее цикла?
Обычно да, чуть-чуть: каждый вызов — это работа с памятью и стеком. На обходе дерева разница незаметна, на миллионе простых шагов — заметна. Выбирай не по скорости, а по форме задачи: дерево — рекурсия, список — цикл.
Что делать с ошибкой про переполнение стека?
Три проверки по порядку: (1) есть ли вообще условие выхода; (2) действительно ли аргумент уменьшается с каждым вызовом; (3) нет ли случайного кольца — функция A зовёт B, а B зовёт A обратно. Третье встречается реже, но ищется дольше всего.
Нужно ли новичку уметь писать рекурсию?
Писать — не срочно. Узнавать — да. Ты будешь встречать её в чужом и сгенерированном коде, и понимание «тут функция зовёт себя, а вот её дно» экономит часы отладки.
Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.





