Основы и концепции

Рекурсия простыми словами: как понять, а не просто зазубрить

23 августа 2026 · 8 мин чтения

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

Что на самом деле происходит при рекурсивном вызове

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

Возьмём классический факториал:

function factorial(n) {
  if (n <= 1) return 1;       // базовый случай
  return n * factorial(n - 1); // рекурсивный случай
}

Вызов factorial(4) не вычисляет ответ сразу. Он откладывает умножение на 4 до тех пор, пока не узнает результат factorial(3), тот в свою очередь ждёт factorial(2), и так до factorial(1), которая наконец возвращает готовое число без дальнейших вызовов. После этого стек начинает «разворачиваться» в обратном порядке: каждый приостановленный вызов получает результат вложенного, домножает его и возвращает уже своё значение наверх. Именно эти два разнонаправленных прохода — «вглубь» и «наружу» — и есть вся механика рекурсии.

Зачем нужен базовый случай и что будет, если его не поставить

Базовый случай — это условие, при котором функция перестаёт вызывать себя и просто возвращает значение. Без него рекурсия не имеет способа остановиться: каждый вызов будет порождать следующий, стек вызовов будет расти бесконечно, и рано или поздно программа упадёт с ошибкой переполнения стека (RangeError: Maximum call stack size exceeded в JavaScript, RecursionError в Python).

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

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

Рекурсия против цикла: когда каждый вариант уместнее

У рекурсии и цикла одна и та же вычислительная мощность — всё, что можно решить рекурсивно, можно переписать циклом с явным стеком или очередью, и наоборот. Выбор между ними — вопрос не правильности, а того, что естественнее описывает задачу и что дешевле по ресурсам:

Рекурсия хорошо подходит, когда данные сами по себе имеют рекурсивную структуру: деревья, вложенные объекты, файловые системы с папками внутри папок. Обход такой структуры циклом требует ручной эмуляции стека, а рекурсивная функция делает это естественно, за счёт стека вызовов языка.
Цикл предпочтительнее для простых последовательных проходов по линейным данным — массивам, спискам, диапазонам чисел, — там рекурсия не добавляет ясности, а только тратит память на кадры вызовов, которые циклу не нужны.
Глубина имеет значение. Если рекурсивных вызовов будет условно десятки или сотни — переполнение стека маловероятно. Если структура может уйти на десятки тысяч уровней вглубь (например, очень длинный связный список), рекурсия рискует упасть там, где цикл отработал бы без проблем.

Хвостовая рекурсия — не универсальное решение в JS

В некоторых языках существует оптимизация хвостовых вызовов (tail call optimization): если рекурсивный вызов — самая последняя операция в функции и результат возвращается без дальнейших преобразований, движок может переиспользовать текущий кадр стека вместо создания нового, и рекурсия перестаёт расходовать стек вообще.

Проблема в том, что в JavaScript эта оптимизация формально есть в спецификации ES2015, но фактически не реализована в большинстве современных движков, включая V8 (Chrome, Node.js). Поэтому переписывание факториала в «хвостовую» форму — где умножение происходит до рекурсивного вызова, через дополнительный аккумулятор, — не спасёт от переполнения стека в браузере или Node.js, даже если в теории должно было бы:

function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // хвостовой вызов
}

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

Итог

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

← Все статьи