Почему в JS стек переполняется при вызове рекурсии?

Почему в JavaScript переполняется стек при рекурсии

Stack Overflow — распространенная ошибка при работе с рекурсией в JavaScript. Давайте разберемся, почему это происходит и как это предотвратить.

Что такое Call Stack (стек вызовов)

Стек вызовов — это структура данных в памяти, которая отслеживает иерархию вызовов функций:

function a() {
  b();
}

function b() {
  c();
}

function c() {
  console.log("c");
}

a();

// Стек вызовов:
// c()
// b()
// a()
// <main>

Когда функция вызывает другую, JavaScript добавляет новый фрейм (frame) в стек. Когда функция заканчивается, фрейм удаляется.

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

При рекурсии функция вызывает саму себя. Каждый вызов добавляет новый фрейм в стек:

function countdown(n) {
  console.log(n);
  countdown(n - 1); // Каждый вызов = новый фрейм в стеке
}

countdown(1000000);
// RangeError: Maximum call stack size exceeded

Почему переполняется:

1. Каждый рекурсивный вызов добавляет фрейм в стек
2. Память, выделенная на стек, ограничена (обычно несколько мегабайт)
3. При глубокой рекурсии стек заполняется и происходит overflow
4. Без базового случая рекурсия никогда не заканчивается

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

В разных средах лимиты разные:

function getMaxCallStackSize() {
  let count = 0;
  function recurse() {
    count++;
    recurse();
  }
  try {
    recurse();
  } catch (e) {
    console.log("Max depth:", count);
  }
}

getMaxCallStackSize();
// В Chrome: примерно 15000-20000
// В Node.js: примерно 10000-15000

Правильная рекурсия с базовым случаем

С базовым случаем рекурсия останавливается:

// Плохо: бесконечная рекурсия
function badCountdown(n) {
  countdown(n - 1);
}

// Хорошо: есть базовый случай
function goodCountdown(n) {
  if (n < 0) return; // Базовый случай
  console.log(n);
  goodCountdown(n - 1);
}

goodCountdown(5);
// 5, 4, 3, 2, 1, 0

Примеры рекурсивных функций

Факториал

function factorial(n) {
  if (n <= 1) return 1; // Базовый случай
  return n * factorial(n - 1); // Рекурсивный случай
}

console.log(factorial(5)); // 120

Поиск в дереве

function findInTree(node, value) {
  if (!node) return null; // Базовый случай: пустой узел
  if (node.value === value) return node; // Найдено
  
  const foundLeft = findInTree(node.left, value);
  if (foundLeft) return foundLeft;
  
  return findInTree(node.right, value);
}

Flatten массива

function flatten(arr) {
  let result = [];
  
  for (let item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item)); // Рекурсия
    } else {
      result.push(item);
    }
  }
  
  return result;
}

console.log(flatten([1, [2, [3, 4]], 5]));
// [1, 2, 3, 4, 5]

Оптимизация: Tail Call Optimization (TCO)

Tail recursion — когда рекурсивный вызов — это последний оператор в функции. Некоторые движки (например Safari) оптимизируют это:

// Обычная рекурсия (не TCO)
function sum(n, acc = 0) {
  if (n === 0) return acc;
  return sum(n - 1, acc + n); // Последний вызов — рекурсия
}

sum(100000); // Может переполниться

Решение: Итеративный подход

Для глубокой рекурсии часто лучше использовать итерацию:

// Рекурсия (ограничена глубиной)
function recursiveSum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + recursiveSum(arr.slice(1));
}

// Итерация (безопаснее)
function iterativeSum(arr) {
  let sum = 0;
  for (let num of arr) {
    sum += num;
  }
  return sum;
}

const largeArray = Array.from({length: 100000}, (_, i) => i);
iterative Sum(largeArray); // Работает быстро, без переполнения

Практические советы

1. Всегда определи базовый случай — без него рекурсия бесконечна
2. Проверь глубину — если данные большие, используй итерацию
3. Используй memoization для оптимизации повторных вычислений
4. Профилируй — проверь, насколько глубока рекурсия
5. Рассмотри стек явно — используй объект для имитации стека в итерации

Заключение

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