Рекурсия: базовый случай, задачи и глубокая рекурсия
На этой странице
Рекурсия — вызов функции из самой себя. Любая рекурсивная функция состоит из базового случая, который возвращает результат без нового вызова, и рекурсивного шага, который сводит задачу к меньшей. Рекурсия естественна для деревьев, вложенных структур и «разделяй и властвуй». Каждый вызов занимает кадр в стеке, поэтому слишком глубокая рекурсия приводит к RangeError: Maximum call stack size exceeded.
Вопрос
Что такое рекурсия? Что такое базовый случай? Какие задачи решает рекурсия и что происходит при слишком глубокой рекурсии?
Структура
function factorial(n) {
if (n <= 1) return 1; // базовый случай
return n * factorial(n - 1); // рекурсивный шаг: задача меньше на 1
}
factorial(5); // 120factorial(5)
5 * factorial(4)
4 * factorial(3)
3 * factorial(2)
2 * factorial(1) → 1Стек растет до базового случая, затем результаты «сворачиваются» обратно.
Базовый случай
Без базового случая (или если шаг не приближает к нему) рекурсия бесконечна:
function countdown(n) {
if (n < 0) return; // базовый случай
console.log(n);
countdown(n - 1);
}Проверяйте граничные входы: 0, отрицательные числа, пустой массив, null.
Какие задачи решает рекурсия
// обход дерева
function countFiles(node) {
if (node.type === "file") return 1;
return node.children.reduce((sum, child) => sum + countFiles(child), 0);
}
// глубокое копирование и сравнение вложенных структур
function deepFlat(arr) {
return arr.reduce(
(acc, item) => (Array.isArray(item) ? acc.concat(deepFlat(item)) : acc.concat(item)),
[],
);
}
// рендер вложенного меню или комментариев в React
function Comments({ items }) {
return items.map((c) => (
<li key={c.id}>
{c.text}
{c.replies.length > 0 && <ul><Comments items={c.replies} /></ul>}
</li>
));
}Типичные области: деревья (DOM, файловая система, AST, JSON), графы (DFS), перебор вариантов (backtracking), сортировки merge sort и quick sort, динамическое программирование с мемоизацией.
Глубокая рекурсия
function sumTo(n) {
return n === 0 ? 0 : n + sumTo(n - 1);
}
sumTo(10_000); // работает
sumTo(1_000_000); // RangeError: Maximum call stack size exceededЛимит стека зависит от движка и обычно составляет порядка 10 000 кадров. Решения:
| Способ | Идея |
|---|---|
| Итерация | переписать через цикл |
| Явный стек | хранить «что обработать» в массиве |
| Мемоизация | не пересчитывать одни и те же подзадачи |
| Trampoline | возвращать функцию вместо вызова и выполнять в цикле |
// обход дерева без рекурсии
function countFilesIterative(root) {
const stack = [root];
let count = 0;
while (stack.length) {
const node = stack.pop();
if (node.type === "file") count++;
else stack.push(...node.children);
}
return count;
}Хвостовая рекурсия
Хвостовой вызов — когда рекурсивный вызов последний и его результат возвращается без вычислений. Спецификация ES2015 описывает оптимизацию хвостовых вызовов (TCO), но ее реализовал только Safari. В V8 (Chrome, Node.js) TCO нет, поэтому на хвостовую рекурсию в JS полагаться нельзя.
Что важно помнить
- Рекурсивное решение часто короче, но итеративное — экономнее по памяти.
- Наивная рекурсия Фибоначчи —
O(2^n); мемоизация даетO(n). - Глубина вложенности данных извне (JSON от пользователя) может быть большой — рекурсивная обработка уязвима для переполнения стека.
- На собеседовании называйте базовый случай, рекурсивный шаг, сложность по времени и памяти (глубина стека).
Мини-шпаргалка
- Рекурсия = базовый случай + шаг, уменьшающий задачу.
- Без базового случая — бесконечная рекурсия.
- Задачи: деревья, вложенные структуры, DFS, backtracking, merge sort.
- Глубокая рекурсия →
Maximum call stack size exceeded. - Решения: цикл, явный стек, мемоизация; TCO в V8 нет.