Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Глибока рекурсія». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

**За дуже глибокої рекурсії в 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`.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати731 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.