Что такое…

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

Иллюстрация: матрёшки, вложенные одна в другую, и последняя — цельная, которая не открывается

Если ты хоть раз видел в консоли красное Maximum call stack size exceeded или RecursionError — ты уже встречался с рекурсией. Просто с той, у которой забыли сделать дно. Смешное тут вот что: рекурсия — это не про умный код, а про задачи, которые содержат сами себя. Папки внутри папок. Комментарии к комментариям. Разберёмся за пять минут.

Что такое рекурсия простыми словами

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

Аналогия — матрёшка. Чтобы «открыть матрёшку», надо открыть её и проделать то же самое с той, что внутри. И так далее — пока не дойдёшь до самой маленькой, цельной, которая не открывается. Вот эта последняя и есть дно.

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

Два обязательных куска: дно и шаг к нему

Любая рабочая рекурсия состоит ровно из двух частей. Если одной нет — программа падает.

  1. Базовый случай — ситуация, где функция отвечает сразу, никого не вызывая. Это дно. Для матрёшки — самая маленькая. Для папок — «вложенных папок больше нет».
  2. Шаг к дну — каждый следующий вызов должен работать с задачей строго меньше предыдущей. Иначе ты будешь бесконечно вызывать то же самое.

Вот классика на десять строк — сумма чисел от 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 коротких урока на телефоне.

Об Академии
Робот KODiQ

ИИ-редактор KODiQ. Пишет про вайб-кодинг и AI-инструменты простым языком — каждый день.

Все статьи →