Как работает рекурсия и как она влияет на call stack
На этой странице
Рекурсия - подход, где функция вызывает саму себя для решения меньшей версии задачи. Чтобы рекурсия была корректной, нужны base case, recursive case и движение к завершению.
Рекурсия использует call stack: каждый незавершенный вызов функции занимает место в стеке. Поэтому у рекурсивного алгоритма нужно учитывать не только время, но и память на глубину рекурсии.
Вопрос
Как работает рекурсия, как она использует call stack и когда заменить ее итерацией?
Пример
function factorial(n: number): number {
if (n <= 1) return 1
return n * factorial(n - 1)
}Здесь:
- base case (базовый случай):
n <= 1- ответ известен сразу, дальше вызывать себя не нужно; - recursive case (рекурсивный шаг):
n * factorial(n - 1)- задача сводится к такой же, но меньшей; - progress:
nуменьшается на каждом вызове, поэтому мы гарантированно дойдем до base case.
Ментальная модель: спуск и подъем
Рекурсия работает в две фазы. Сначала вызовы спускаются до base case, и каждый ждет результата следующего. Потом ответы поднимаются обратно:
спуск:
factorial(4) ждет factorial(3)
factorial(3) ждет factorial(2)
factorial(2) ждет factorial(1)
factorial(1) = 1 <- base case
подъем:
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24Что такое call stack?
Call stack - стек активных вызовов функций. Каждый вызов кладет на стек свою "рамку" с аргументами и локальными переменными, а при return рамка снимается.
function countDown(n: number): void {
if (n === 0) return
countDown(n - 1)
}
countDown(3)В самый глубокий момент на стеке лежат 4 рамки:
countDown(0) <- вершина стека, выполняется сейчас
countDown(1)
countDown(2)
countDown(3)Глубина рекурсии n, значит память:
O(n)Stack overflow
Размер call stack ограничен (в браузерах обычно порядка 10 000 рамок, точное число зависит от движка). Если рекурсия слишком глубокая, JavaScript выбросит ошибку:
RangeError: Maximum call stack size exceededСамый частый случай - забытый base case:
function bad(n: number): number {
return bad(n + 1)
}Но ошибка возможна и в корректной рекурсии, если данные большие: например, рекурсивный обход linked list на 100 000 узлов.
Где нужна рекурсия?
- деревья;
- DFS;
- backtracking;
- divide and conquer;
- dynamic programming top-down;
- парсинг вложенных структур.
Рекурсия для дерева
type TreeNode = {
value: number
left: TreeNode | null
right: TreeNode | null
}
function sumTree(root: TreeNode | null): number {
if (!root) return 0
return root.value + sumTree(root.left) + sumTree(root.right)
}Time O(n) - каждый узел посещается один раз.
Space O(h), где h - высота дерева: на стеке одновременно лежат вызовы только для одного пути от корня вниз. Для сбалансированного дерева это O(log n), для вырожденного (похожего на список) - O(n).
Когда заменить рекурсию итерацией?
Если глубина может быть большой:
- linked list на 100000 узлов;
- очень глубокое дерево;
- большой граф;
- рекурсивный DFS без контроля глубины.
Тогда вместо call stack используют явный stack - обычный массив в куче, у которого нет такого ограничения:
function sumTreeIterative(root: TreeNode | null): number {
if (!root) return 0
let sum = 0
const stack = [root]
while (stack.length > 0) {
const node = stack.pop()!
sum += node.value
if (node.left) stack.push(node.left)
if (node.right) stack.push(node.right)
}
return sum
}Рекурсивная версия обычно короче и понятнее, поэтому на собеседовании начинают с нее, а итеративную предлагают, если спросят про глубину.
Что отвечать на собеседовании?
Рекурсия решает задачу через меньшие подзадачи. Для корректности нужны base case, recursive transition и гарантия, что мы приближаемся к base case. Каждый незавершенный вызов занимает рамку в call stack, поэтому глубина рекурсии d дает space complexity минимум O(d): для дерева это O(h), для линейной рекурсии O(n). В JavaScript слишком глубокая рекурсия приводит к Maximum call stack size exceeded, поэтому для больших данных рекурсивный DFS заменяют явным стеком.
Что важно помнить: частые ошибки
- Нет base case или он недостижим.
- Задача не уменьшается на каждом вызове.
- Не вернуть результат рекурсивного вызова через
return. - Считать рекурсивное решение
O(1)по памяти. - Рекурсивно обходить огромный массив или список.
- Думать, что tail call optimization гарантирована в JavaScript - на практике ее поддерживает только Safari.
Мини-шпаргалка
- Base case + recursive case + progress.
- Сначала спуск до base case, потом подъем с ответами.
- Каждый вызов - рамка в call stack.
- Глубина
d-> spaceO(d); дерево ->O(h). - Нет base case -> бесконечная рекурсия и stack overflow.
- Большая глубина -> явный stack вместо рекурсии.