Рекурсия и стек вызовов

Внутри функции можно вызвать любую функцию — в том числе ту, внутри которой мы находимся. Никакого особого синтаксиса для этого нет: имя функции доступно в её собственном теле, и вызов работает точно так же, как любой другой.

function countdown(n) {
  if (n === 0) return "пуск";
  console.log(n);
  return countdown(n - 1);
}
console.log(countdown(3));

Здесь countdown(3) печатает тройку и зовёт countdown(2), тот печатает двойку и зовёт countdown(1), и так до нуля. Важно, что каждый новый вызов получает меньший аргумент — иначе спуск никогда не дойдёт до дна.

Такую функцию называют рекурсивной, а количество вложенных вызовов — глубиной рекурсии. У примера выше глубина равна четырём: вызовы с аргументами 3, 2, 1 и 0.

У любой рабочей рекурсии две части. Базовый случай — вариант, который решается сразу, без новых вызовов. Шаг рекурсии — сведение задачи к такой же, но меньшей, плюс вызов себя. Классика жанра — факториал: n! — это n, умноженное на (n - 1)!.

function factorial(n) {
  if (n <= 1) return 1; // базовый случай: дальше не спускаемся
  return n * factorial(n - 1); // шаг: та же задача, но меньше
}
console.log(factorial(5));

Пиши базовый случай первой строкой функции, а шаг — после. Тогда бесконечному спуску просто неоткуда взяться, и не придётся отлаживать зависшую вкладку.

Проверить рекурсию в голове проще всего доверием: считайте, что factorial(4) уже умеет возвращать 24. Тогда factorial(5) — это 5 * 24. Не нужно прослеживать всю цепочку, достаточно убедиться, что шаг корректен и что он приближает к базовому случаю.

Когда функция вызывает другую, первая никуда не исчезает — она ждёт результата. Движок хранит такие ожидающие вызовы в стеке вызовов: на каждый вызов заводится кадр с аргументами, локальными переменными и точкой, куда вернуться. Новый вызов кладётся сверху, завершившийся — снимается. Отсюда и порядок: кто зашёл последним, тот выходит первым.

function sum(n) {
  console.log("вход", n);
  if (n === 0) return 0;
  const result = n + sum(n - 1);
  console.log("выход", n);
  return result;
}
console.log(sum(3));

Обратите внимание на порядок строк «выход»: он ровно обратный порядку «входов». Вызов sum(3) начался первым, а закончился последним — всё это время его кадр лежал в основании стека и держал в себе значение n, равное 3.

Факториал — учебный пример, в жизни его пишут циклом. Настоящая территория рекурсии — данные, вложенные сами в себя: массив массивов, дерево комментариев, папки внутри папок. Заранее неизвестно, сколько там уровней, и вложенными циклами это не берётся.

function sumDeep(list) {
  let total = 0;
  for (const item of list) {
    total += Array.isArray(item) ? sumDeep(item) : item;
  }
  return total;
}
console.log(sumDeep([1, [2, [3, 4]], 5]));

Логика читается вслух почти дословно: число — прибавляем, массив — просим ту же функцию посчитать его сумму. Базовый случай тут спрятан в самой структуре: у массива без вложенностей рекурсивная ветка просто не срабатывает.

const team = {
  budget: 100,
  subs: [{ budget: 50, subs: [] }, { budget: 20, subs: [{ budget: 5, subs: [] }] }],
};
function total(node) {
  return node.budget + node.subs.reduce((acc, sub) => acc + total(sub), 0);
}
console.log(total(team));

Память под стек выделена заранее и невелика. Если кадры всё прибывают, движок останавливает программу ошибкой — в Chrome это RangeError: Maximum call stack size exceeded, в Firefox InternalError: too much recursion: ни вид такой ошибки, ни её текст стандартом не описаны. Чаще всего причина банальна: забыт базовый случай или шаг не приближает к нему.

function deep(n) {
  return deep(n + 1); // базового случая нет
}
try {
  deep(1);
} catch (error) {
  console.log(error.name);
}

Точный предел глубины не описан в стандарте: он зависит от движка, размера кадров и настроек браузера. Ориентир — единицы или десятки тысяч вызовов. Полагаться на конкретное число нельзя, а вот держать глубину заведомо небольшой — можно и нужно. Само переполнение — обычная ошибка времени выполнения, со своим видом и объектом: про них статья «Виды ошибок и объект Error».

let depth = 0;
function dive() {
  depth += 1;
  dive();
}
try { dive(); } catch (error) { /* переполнение поймали */ }
console.log(depth > 1000);

function factTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factTail(n - 1, n * acc); // вызов последний, но кадр всё равно создаётся
}
console.log(factTail(5));

Любую рекурсию можно переписать циклом, и наоборот. Выбор делают не по красоте, а по форме данных: линейный перебор — цикл, вложенная структура — рекурсия. Цикл к тому же не тратит стек и обычно быстрее: вызов функции стоит дороже перехода на следующую итерацию.

function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i += 1) total += i;
  return total;
}
console.log(sumLoop(100000));

Тот же счёт рекурсией потребовал бы ста тысяч кадров и упал бы с переполнением. Зато sumDeep из раздела выше циклом пишется заметно уродливее — придётся вручную заводить массив-хранилище и складывать в него необработанные ветки, то есть строить свой стек в обычной памяти.