re:re:actable
Урок 014 минуты чтения

Как работает рекурсия и как она влияет на 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 -> space O(d); дерево -> O(h).
  • Нет base case -> бесконечная рекурсия и stack overflow.
  • Большая глубина -> явный stack вместо рекурсии.

Документация

MDN: Recursion, MDN: Call stack.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам