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

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

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

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

Контент

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

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

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

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

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

**Рекурсія** - це функція, яка викликає саму себе, щоб розбити задачу на менші версії тієї ж задачі, поки не дійде до базового випадку, який можна вирішити напряму.

## Теорія

### TL;DR

- Уяви матрьошку: відкриваєш одну, всередині менша, і так далі, поки не дійдеш до найменшої, всередині якої вже нічого немає.
- Кожна рекурсивна функція потребує двох речей: **базового випадку** (умова зупинки) і **рекурсивного виклику** (виклик себе з меншим аргументом).
- Рекурсія добре підходить для дерев, графів і вкладених структур. Для плоских даних використовуй цикл, щоб не переповнити стек.
- Node.js і браузери дозволяють приблизно 10,000 фреймів у стеку викликів, після чого кидають `RangeError: Maximum call stack size exceeded`.

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

```javascript
function factorial(n) {
  if (n <= 1) return 1;        // базовий випадок: зупинка
  return n * factorial(n - 1); // рекурсивний виклик: менша задача
}

console.log(factorial(5)); // 120
// Стек: factorial(5) -> 5 * factorial(4) -> ... -> 5 * 4 * 3 * 2 * 1
```

Кожен виклик додає фрейм до стека викликів. Коли `factorial(1)` повертає `1`, стек розкручується назад, і кожен фрейм множить своє `n` на результат попереднього.

### Як це працює в стеку викликів

V8 (Chrome/Node.js) кладе кожен рекурсивний виклик у стек як новий контекст виконання зі своїми локальними змінними. Фрейми чекають там, поки не спрацює базовий випадок. Потім значення розкручуються назад через кожен фрейм у зворотному порядку.

Стандартна глибина стека в Node.js становить близько 10,000 фреймів. Перевищиш і отримаєш `RangeError: Maximum call stack size exceeded`. Саме тому `factorial(100000)` завалить Node.js, і саме тому рекурсія для великих плоских масивів є поганим вибором.

### Коли використовувати

- **Обхід дерева або графу** (DOM, файлова система, дерево компонентів): структура вкладена, тому рекурсія відображає її напряму.
- **Парсинг вкладених даних** (JSON, HTML): кожен вузол може мати дочірні вузли тієї ж форми.
- **Алгоритми "розділяй і пануй"** (quicksort, merge sort): задача ділиться навпіл з кожним викликом.
- **Великі плоскі масиви**: використовуй цикл. Немає вкладеності, немає переваги, є тільки ризик переповнення стека.
- **Fibonacci без оптимізації**: підходить для демонстрацій, але складність O(2^n). Перед деплоєм додай мемоізацію.

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

**Немає базового випадку:**
```javascript
function bad(n) {
  return n * bad(n - 1); // немає умови зупинки
}
// RangeError: Maximum call stack size exceeded
```
Рішення: додати `if (n <= 1) return 1;` перед рекурсивним викликом.

**Аргумент не зменшується:**
```javascript
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n); // n не змінюється, нескінченний цикл
}
```
Передати `n` замість `n - 1` - одна з найпоширеніших помилок у код-рев'ю. Функція виглядає нормально на перший погляд. Node.js повідомить про проблему тільки коли стек вичерпається.

Рішення: передавати `n - 1`. Кожен виклик повинен наближати до базового випадку.

**Ігнорування глибини стека:**
`factorial(100000)` завалить Node.js. Якщо вхідні дані можуть бути великими, використовуй ітеративний підхід. Можна збільшити стек через `node --stack-size=65500`, але це обхідне рішення, не виправлення.

### Де зустрічається

- React Fiber обходить дерево компонентів рекурсивно під час рендерингу (reconciler йде вглибину).
- Lodash `_.flattenDeep` рекурсивно обходить вкладені масиви для повного вирівнювання.
- Обхід директорій у Node.js використовує рекурсивні патерни для обходу файлової ієрархії.
- D3.js рекурсивно обходить ієрархії вузлів для розрахунку позицій у деревовидних візуалізаціях.

### Питання на співбесіді

**Q:** Напиши `factorial` ітеративно.
**A:** `function factIter(n, acc = 1) { if (n <= 1) return acc; return factIter(n - 1, acc * n); }`. Формально це хвостова рекурсія, але V8 її не оптимізує, тому стек все одно зростає.

**Q:** Яка часова складність наївної рекурсії для Fibonacci?
**A:** O(2^n). Кожен виклик розгалужується на два, тому загальна кількість викликів подвоюється на кожному рівні. Виправляється мемоізацією або ітеративним підходом знизу вгору.

**Q:** Чи підтримує JavaScript оптимізацію хвостових викликів (TCO)?
**A:** Ні. V8 не виконує TCO на практиці. Навіть правильно написаний хвостовий виклик все одно додає фрейм у стек. Для глибокої рекурсії використовуй цикл.

**Q:** Що відбувається з рекурсивним стеком, якщо користувач переключає вкладку браузера під час виконання?
**A:** JavaScript однопотоковий. Браузер призупиняє виконання, коли вкладка втрачає фокус, і відновлює при поверненні. Важка рекурсія, що блокує головний потік, заморожує UI до повного розкручування стека. Для затратних операцій використовуй `setTimeout` або Web Workers.

## Приклади

### Базовий: сума всіх чисел у масиві

```javascript
function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0;            // базовий випадок: вийшли за межі
  return arr[index] + sumArray(arr, index + 1); // додаємо поточний, рекурсія на решту
}

console.log(sumArray([1, 2, 3, 4])); // 10
// Розкручується як: 1 + (2 + (3 + (4 + 0)))
```

Базовий випадок спрацьовує, коли `index` досягає довжини масиву. Далі кожен фрейм повертає свій елемент плюс суму всього, що правіше.

### Середній: рендер вкладеного дерева компонентів

Спрощена версія того, що React робить при обході дерева компонентів:

```javascript
function renderTree(node) {
  if (!node.children || node.children.length === 0) {
    return `<div>${node.text}</div>`; // базовий випадок: листовий вузол
  }

let html = `<div>${node.text}`;
  node.children.forEach(child => {
    html += renderTree(child); // рекурсія для кожного дочірнього вузла
  });
  return html + '</div>';
}

const tree = {
  text: 'App',
  children: [
    { text: 'Header', children: [] },
    { text: 'Main', children: [{ text: 'Article', children: [] }] }
  ]
};

console.log(renderTree(tree));
// <div>App<div>Header</div><div>Main<div>Article</div></div></div>
```

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

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

Для рев’юера

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

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