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

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

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

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

Контент

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

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

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

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

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

При **глибокій рекурсії** (тобто коли функція викликає саму себе **багато разів**, перш ніж дійти до базового випадку) у JavaScript може статися **переповнення стека викликів** - помилка `RangeError: Maximum call stack size exceeded`.

---

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

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

```javascript
factorial(5)
→ factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1)
```

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

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

Коли базовий випадок досягнуто, стек "розмотується" назад.
Але якщо викликів **занадто багато** - стек переповнюється.

---

## Приклад переповнення стека

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

recurse(1);
```

Помилка:

```javascript
RangeError: Maximum call stack size exceeded
```

Браузер (або Node.js) виділяє обмежений розмір стека -
зазвичай близько **10 000-20 000** вкладених викликів.

---

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

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

countdown(100000); // RangeError
```

Попри наявність базового випадку,
глибина рекурсії (100 000) занадто велика для стека JS.

---

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

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

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

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

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

Але: у більшості рушіїв JS **tail call optimization не реалізована**.

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

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

Тут кожен виклик виконується **в новому циклі подій**,
тому стек не росте.

---

## Підсумок

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

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

Для рев’юера

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

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