Рекурсия

Рекурсия

Почему рекурсия кажется сложной

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

  • текущий вызов;
  • следующий вложенный вызов;
  • момент остановки;
  • как результаты "собираются обратно" при выходе из стека.

Ключевой момент: рекурсия всегда решает задачу через более маленькую версию той же задачи.

Два обязательных элемента рекурсии

У любой корректной рекурсии есть:

  1. Базовый случай - когда дальнейшие вызовы не нужны.
  2. Рекурсивный шаг - как задача приближается к базовому случаю.
function factorial(n) {
  if (n <= 1) return 1; // базовый случай
  return n * factorial(n - 1); // шаг уменьшения
}

Если шаг не ведет к базе, функция уйдет в бесконечную рекурсию.

Как "увидеть" стек вызовов

function trace(n) {
  console.log('enter', n);
  if (n === 0) {
    console.log('base');
    return;
  }
  trace(n - 1);
  console.log('exit', n);
}

trace(3);

Ты увидишь, что сначала вызовы "проваливаются" внутрь (enter 3 -> 2 -> 1 -> 0), а потом выходят обратно (exit 1 -> 2 -> 3).

Валидация входа в рекурсивных функциях

Рекурсия должна быть не только математически корректной, но и безопасной для реальных входов.

function factorialSafe(n) {
  if (!Number.isInteger(n) || n < 0) return null;
  if (n <= 1) return 1;
  return n * factorialSafe(n - 1);
}

console.log(factorialSafe(5)); // 120
console.log(factorialSafe(-1)); // null

Такой guard защищает от некорректных аргументов до рекурсивного шага.

Рекурсия по массиву

function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0;
  return arr[index] + sumArray(arr, index + 1);
}

console.log(sumArray([4, 6, 10])); // 20

Здесь "меньшая задача" - сумма хвоста массива, начиная с index + 1.

Рекурсия по дереву (реальный сценарий)

function countNodes(node) {
  if (!node) return 0;

  let total = 1;
  for (const child of node.children ?? []) {
    total += countNodes(child);
  }
  return total;
}

const tree = {
  value: 'root',
  children: [
    { value: 'a', children: [] },
    { value: 'b', children: [{ value: 'b1', children: [] }] },
  ],
};

console.log(countNodes(tree)); // 4

Иерархии - одна из лучших областей применения рекурсии.

Рекурсия vs цикл на одной задаче

function sumToRecursive(n) {
  if (n <= 0) return 0;
  return n + sumToRecursive(n - 1);
}

function sumToIterative(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

console.log(sumToRecursive(5)); // 15
console.log(sumToIterative(5)); // 15

Оба решения корректны. Выбор зависит от читаемости и ожидаемой глубины.

Ограничения: глубина стека

Каждый рекурсивный вызов занимает место в стеке.
Слишком глубокая рекурсия может привести к ошибке Maximum call stack size exceeded.

Смотри, что важно: в большинстве JS-движков нет гарантированной оптимизации хвостовой рекурсии, поэтому даже "хвостовые" варианты могут переполнить стек при большой глубине.

Практическое правило:

  • если глубина небольшая и структура естественно рекурсивная (дерево), рекурсия часто удобна;
  • если глубина может быть очень большой, чаще надежнее итеративное решение.

Частые ошибки новичков

  • нет базового случая;
  • базовый случай есть, но шаг к нему не приближает;
  • забыть return перед рекурсивным вызовом, когда нужен результат;
  • путаница в том, что возвращает функция на каждом уровне;
  • попытка "понять все вызовы сразу", вместо пошаговой трассировки.

Анти-провал: сначала сформулируй базу одной строкой, потом - рекурсивный переход одной строкой.

Краткий итог

  • Рекурсия = базовый случай + шаг уменьшения задачи.
  • Вызовы сначала углубляются, потом разворачиваются обратно через стек.
  • Рекурсия особенно полезна для деревьев и вложенных структур.
  • Входные данные нужно валидировать до рекурсивного шага.
  • Всегда сравнивай с итеративным вариантом, если ожидается большая глубина.