Из-за чего ломается рекурсия при работе с большими числами

Рекурсия использует call stack. Когда функция вызывает сама себя, текущий вызов не исчезает. Он ждет результата вложенного вызова. Поэтому в стеке накапливаются фреймы с параметрами, локальными переменными и адресом возврата.

Если рекурсивных шагов слишком много, стек заканчивается. В JavaScript это обычно выглядит как RangeError: Maximum call stack size exceeded или, в некоторых окружениях, как сообщение про too much recursion.

На интервью отвечайте точнее: ломается не магически из-за большого числа. Проблема в том, что это число превращается в большую глубину рекурсии или слишком большой объем синхронной работы.

Плохой вариант для большого n:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

factorial(100000);

Здесь глубина вызовов примерно равна n. Даже если забыть про то, что результат факториала быстро станет огромным и потеряет точность в типе number, сама цепочка вызовов слишком глубокая для стека.

Более безопасный вариант по стеку:

function factorial(n) {
  let result = 1n;

  for (let i = 2n; i <= n; i++) {
    result *= i;
  }

  return result;
}

factorial(100000n);

Цикл не создает новую вложенную функцию на каждый шаг, поэтому не переполняет call stack. Но он все равно может быть тяжелым для main thread, если запускать его прямо во время взаимодействия пользователя с интерфейсом.

Хвостовая рекурсия, это случай, когда рекурсивный вызов является последним действием функции. В языках с tail call optimization такой вызов можно выполнить без роста стека.

Но для JavaScript на frontend-интервью важна практическая оговорка. Не обещайте, что браузер или Node.js обязательно оптимизируют хвостовую рекурсию. Такая версия выглядит аккуратнее, но не является надежной защитой от переполнения стека.

function factorial(n, acc = 1n) {
  if (n === 0n) return acc;
  return factorial(n - 1n, acc * n);
}

Это хвостовая форма, но для больших n в реальном JS-коде ее все равно лучше заменить циклом.

Если на интервью спрашивают про большие числа, не ограничивайтесь словом стек. Добавьте практический выбор. Для простой линейной задачи подойдет цикл, для обхода дерева подойдет явный стек или очередь, для повторяющихся подзадач подойдет мемоизация вместе с контролем глубины.

Хорошая формулировка звучит спокойно: сначала я оцениваю максимальную глубину, потом сложность и влияние на UI. Если глубина может расти вместе с пользовательскими данными, рекурсия становится рискованной.

Мемоизация помогает, когда функция много раз считает одни и те же подзадачи. Например, наивный рекурсивный Fibonacci делает очень много повторных вызовов, и кеш резко уменьшает число операций.

Но мемоизация не всегда уменьшает глубину самой длинной цепочки вызовов. Если функция идет от n к 0 по одному шагу, глубина все равно может быть слишком большой. Поэтому сильный ответ разделяет две проблемы: сколько всего вызовов будет сделано и насколько глубокой будет самая длинная цепочка.

Во frontend-коде проблема рекурсии часто проявляется не только как ошибка, но и как плохой UX. Большой синхронный расчет блокирует main thread, из-за этого перестают плавно работать скролл, ввод, анимации и обработчики кликов.

Если нужно обработать много данных в браузере, выбирайте один из вариантов: итеративный алгоритм, разбиение работы на чанки, Web Worker для тяжелой задачи или перенос вычисления на сервер. В React не запускайте глубокий обход прямо во время render и не пересчитывайте его без зависимости от входных данных. Главное, не оставляйте глубокую рекурсию на данных, размер и форму которых вы не контролируете.