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

Рекурсия: базовый случай, задачи и глубокая рекурсия

На этой странице
Кратко

Рекурсия — вызов функции из самой себя. Любая рекурсивная функция состоит из базового случая, который возвращает результат без нового вызова, и рекурсивного шага, который сводит задачу к меньшей. Рекурсия естественна для деревьев, вложенных структур и «разделяй и властвуй». Каждый вызов занимает кадр в стеке, поэтому слишком глубокая рекурсия приводит к RangeError: Maximum call stack size exceeded.

Вопрос

Что такое рекурсия? Что такое базовый случай? Какие задачи решает рекурсия и что происходит при слишком глубокой рекурсии?

Структура

function factorial(n) {
  if (n <= 1) return 1;          // базовый случай
  return n * factorial(n - 1);   // рекурсивный шаг: задача меньше на 1
}
 
factorial(5); // 120
factorial(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 нет.

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

MDN: Рекурсия, learn.javascript.ru: Рекурсия и стек.

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

Поиск

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