</> HackerX

Рекурсия в JavaScript: когда функция вызывает себя

Алгоритмы и структуры данных Автор: Редакция HackerX · · 4 мин чтения
Содержание

О проверке кода. Примеры не запускались — в отличие от материалов по Node.js с фактическим выводом. Говорим прямо, а не ставим бейдж «проверено».

Рекурсия пугает новичков, но идея простая: решить задачу, сведя её к меньшей версии себя же. Для одних задач это громоздко, для других — единственный естественный способ. Разберём, когда она уместна.

Анатомия рекурсии

У правильной рекурсивной функции всегда две части:

function factorial(n) {
  if (n <= 1) return 1;          // 1. БАЗОВЫЙ СЛУЧАЙ — остановка
  return n * factorial(n - 1);   // 2. ШАГ — вызов себя с меньшим аргументом
}

factorial(4);   // 4 * 3 * 2 * 1 = 24
  • базовый случай — условие, при котором функция возвращает результат без нового вызова себя. Это точка остановки;
  • шаг рекурсии — вызов себя с аргументом, который приближает к базовому случаю.

Уберите базовый случай — и вызовы никогда не остановятся. Сделайте шаг, который не приближает к базе, — то же самое. Оба элемента обязательны.

Как разворачивается factorial(4)
  1. 1 factorial(4)4 * factorial(3) — ждёт
  2. 2 factorial(3)3 * factorial(2) — ждёт
  3. 3 factorial(1)n <= 1 → возвращает 1 — БАЗА, разворот назад
  4. 4 Сборка результата1 → 2 → 6 → 24, стек сворачивается

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

Где рекурсия действительно нужна: вложенные структуры

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

// посчитать сумму чисел в произвольно вложенном массиве
function deepSum(arr) {
  let sum = 0;
  for (const item of arr) {
    if (Array.isArray(item)) {
      sum += deepSum(item);      // вложенный массив — уходим вглубь
    } else {
      sum += item;
    }
  }
  return sum;
}

deepSum([1, [2, 3, [4, 5]], 6]);   // 21 — глубина заранее неизвестна

Здесь рекурсия сияет. Глубина вложенности неизвестна — цикл не знает, на сколько уровней спускаться, а рекурсия спускается ровно на столько, сколько нужно. Тот же приём — обход дерева комментариев, файловой системы, DOM, вложенного JSON. Базовый случай тут — «элемент не массив», шаг — «уйти в подмассив».

Обход дерева

const tree = {
  name: 'корень',
  children: [
    { name: 'A', children: [] },
    { name: 'B', children: [
      { name: 'B1', children: [] },
    ] },
  ],
};

function printTree(node, depth = 0) {
  console.log(' '.repeat(depth * 2) + node.name);   // текущий узел
  node.children.forEach(child => printTree(child, depth + 1)); // рекурсия в детей
}

Дерево — рекурсивная структура по своей природе (узел содержит узлы), поэтому и обход рекурсивный. Базовый случай тут неявный: у листа children пустой, forEach ничего не вызывает — рекурсия сама останавливается.

Ловушка: переполнение стека

// ❌ забыт/недостижим базовый случай
function endless(n) {
  return endless(n + 1);         // никогда не остановится
}
endless(1);   // RangeError: Maximum call stack size exceeded

// ❌ слишком глубоко даже с базой
function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1);
}
sumTo(100000);   // упадёт — стек не бесконечен

Каждый рекурсивный вызов занимает место в стеке вызовов, и оно ограничено (обычно порядка десятков тысяч кадров). Забытый базовый случай или очень большая глубина дают Maximum call stack size exceeded. В отличие от некоторых языков, JavaScript на практике не оптимизирует хвостовую рекурсию, поэтому глубокая линейная рекурсия опасна — её переписывают циклом.

Рекурсия против цикла

// рекурсивно — красиво, но рискует стеком на больших n
function sumRec(n) {
  return n === 0 ? 0 : n + sumRec(n - 1);
}

// циклом — прозаично, но без риска переполнения
function sumLoop(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) sum += i;
  return sum;
}

Любую рекурсию можно переписать циклом (иногда с явным стеком-массивом). Выбор — вопрос ясности и безопасности:

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

Правило: берите рекурсию, когда она делает код заметно понятнее (обход деревьев), и цикл — когда задача линейна. Красота рекурсии не стоит падения на больших данных.

Смежные темы: функции — основа рекурсии; итераторы и генераторы — обход по требованию; массивы — вложенные структуры. Полный список — в уроках JavaScript.

Частые вопросы

Что такое рекурсия?
Приём, когда функция вызывает саму себя, чтобы решить задачу через её меньшие версии. У правильной рекурсии есть базовый случай, который останавливает вызовы, и шаг, который сводит задачу к более простой.
Что такое базовый случай в рекурсии?
Условие, при котором функция возвращает результат без нового вызова себя. Без базового случая рекурсия не остановится и приведёт к переполнению стека. Это первое, что пишут в рекурсивной функции.
Когда рекурсия лучше цикла?
Когда данные вложенные и заранее неизвестной глубины: дерево комментариев, файловая система, вложенные объекты. Рекурсия описывает такой обход естественно, тогда как цикл потребовал бы ручного стека и был бы громоздким.
Что такое переполнение стека?
Ошибка Maximum call stack size exceeded, возникающая, когда рекурсия уходит слишком глубоко — забыт базовый случай или данные огромны. Каждый вызов занимает место в стеке, и оно заканчивается. Лечится циклом или ограничением глубины.
Всегда ли рекурсию можно заменить циклом?
Да, любую рекурсию теоретически можно переписать циклом, иногда с явным стеком. Для линейных задач цикл проще и безопаснее. Рекурсию оставляют там, где она делает код заметно понятнее — при обходе вложенных структур.