Глибока рекурсія

JavaScriptMiddle~3 хв читання

За дуже глибокої рекурсії в JavaScript стається переповнення стека викликів: рушій кидає RangeError: Maximum call stack size exceeded. Глибока рекурсія означає, що функція викликає саму себе багато разів, перш ніж дійти до базового випадку, і всі ці незавершені виклики одночасно займають місце в стеку.

Теорія

TL;DR

Кожен рекурсивний виклик створює новий контекст виконання (stack frame) у стеку викликів.
Фрейм зберігає локальні змінні, аргументи та адресу повернення.
Стек «розмотується» назад тільки після того, як досягнуто базового випадку.
Розмір стека обмежений: зазвичай приблизно 10 000 - 20 000 вкладених викликів.
Перевищення ліміту дає RangeError: Maximum call stack size exceeded.
Навіть коректний базовий випадок не рятує, якщо глибина завелика.
Виходи: цикл, хвостова рекурсія (де вона оптимізується) або порції через setTimeout.

Швидкий приклад

javascript

function recurse(n) {
  console.log(n);
  recurse(n + 1); // немає базового випадку
}

recurse(1);

Результат:

javascript

RangeError: Maximum call stack size exceeded

Що відбувається «під капотом»

Щоразу, коли функція викликає саму себе, JavaScript створює новий контекст виконання (stack frame) у стеку викликів:

javascript

factorial(5)
-> factorial(4)
-> factorial(3)
-> factorial(2)
-> factorial(1)

Кожен виклик зберігає:

локальні змінні,
аргументи,
адресу повернення.

Коли базовий випадок досягнуто, стек «розмотується» назад: найглибший виклик повертає значення, його фрейм звільняється, і так до самого верху. Але якщо викликів забагато, стек переповнюється ще до того, як почнеться розмотування.

Браузер (або Node.js) виділяє обмежений розмір стека, зазвичай це близько 10 000 - 20 000 вкладених викликів. Точне число залежить від рушія, платформи і навіть від того, скільки аргументів та локальних змінних має ваша функція: що «важчий» фрейм, то менше їх поміститься.

Навіть із базовим випадком можна впертися в ліміт

javascript

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

countdown(100000); // RangeError

Попри наявність базового випадку, глибина рекурсії (100 000) завелика для стека JavaScript. Тобто базовий випадок захищає від нескінченної рекурсії, але не від глибокої. Це важлива різниця на співбесіді: правильна логіка і безпечна глибина, це дві окремі вимоги.

Як уникнути проблеми

1. Переписати рекурсію в цикл

javascript

function countdown(n) {
  while (n > 0) n--;
}

Цикл тримає стан в одній змінній і не додає жодного фрейму, тому глибина перестає бути обмеженням.

2. Використати хвостову рекурсію (якби була оптимізація)

javascript

function countdown(n) {
  if (n === 0) return;
  return countdown(n - 1); // хвостовий виклик
}

Хвостовий виклик, це коли рекурсивний виклик є останньою дією функції, тож її фрейм більше не потрібен і теоретично може бути перевикористаний. Але у більшості рушіїв JavaScript tail call optimization не реалізована, тому покладатися на це не можна: код вище так само впаде.

3. Розбити рекурсію на «порції» через setTimeout

javascript

function countdown(n) {
  if (n === 0) return;
  console.log(n);
  setTimeout(() => countdown(n - 1), 0); // не нарощує стек
}

Тут кожен виклик виконується в новій ітерації event loop: попередній виклик уже завершився і його фрейм звільнився, тому стек не росте. Ціною є те, що функція стає асинхронною, тож повернути результат можна лише через колбек або Promise.

4. Перенести стан у власний стек-масив

javascript

function collectValues(root) {
  const out = [];
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    out.push(node.value);
    for (const child of node.children ?? []) stack.push(child);
  }
  return out;
}

Масив живе в купі (heap), а не в стеку викликів, тому обмеження на глибину фактично зникає.

Підсумкова таблиця

Явище	Що відбувається
Глибока рекурсія	Багато вкладених викликів однієї функції
Результат	Переповнення стека (`RangeError`)
Чому	Кожен виклик створює новий контекст у стеку
Як уникнути	Використати цикл, хвостову рекурсію або `setTimeout`

Типові помилки

Плутати нескінченну і глибоку рекурсію. Базовий випадок рятує від першої, але не від другої: countdown(100000) логічно правильний і все одно падає.
Розраховувати на tail call optimization. У специфікації вона є, у реальних рушіях JavaScript здебільшого ні, тому переписаний «у хвостовий стиль» код не стає безпечнішим.
Вважати ліміт фіксованим числом. Він залежить від рушія, платформи і розміру фрейму, тому тест, що проходить на одній машині, може впасти на іншій.
Ловити RangeError у try/catch і вважати проблему розв'язаною. Перехоплення приховує баг, але робота все одно не виконана, а стан може лишитися напівзміненим.
Забувати, що setTimeout робить функцію асинхронною. Після такої заміни return уже не віддасть результат викликачу, потрібен колбек або Promise.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.