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

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

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

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

Контент

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

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

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

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

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

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

Рекурсія - це спосіб розв'язання задач, при якому функція викликає сама себе, поки не досягне базової умови (бази), після чого "розгортається" назад, збираючи результат.

- Ключові елементи: базовий випадок, рекурсивний крок, гарантований прогрес до бази.
- Підходить для задач із природною ієрархією: дерева, графи, розбиття і завоювання (divide and conquer).

## Докладне пояснення

### Як влаштована рекурсивна функція

- Базовий випадок: умова зупинки, за якої відповідь відома одразу (без подальших викликів).
- Рекурсивний крок: зменшення задачі до підзадачі меншого розміру і виклик тієї самої функції для підзадачі.
- Прогрес до бази: на кожному кроці ми наближаємося до виконання базового випадку (інакше - нескінченна рекурсія).

### Стек викликів і складність

Кожен рекурсивний виклик кладеться в стек викликів. Глибина рекурсії = висота стека = додаткова пам'ять O(depth). При занадто великій глибині можливий Stack Overflow. Час роботи залежить від кількості викликів і роботи на кожному рівні (наприклад, O(n) для простого лінійного зменшення, O(2^n) для наївного Фібоначчі).

### Приклад 1: факторіал (рекурсія)

```
function factorial(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0 || n === 1) return 1; // базовий випадок
  return n * factorial(n - 1);      // рекурсивний крок
}

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

База: 0! = 1 і 1! = 1. Прогрес: зменшуємо n до n-1 на кожному кроці.

### Ітераційний еквівалент (те саме без рекурсії)

```
function factorialIter(n) {
  if (n < 0) throw new Error('n must be >= 0');
  let res = 1;
  for (let i = 2; i <= n; i++) res *= i;
  return res;
}

console.log(factorialIter(5)); // 120
```

### Де рекурсія особливо доречна

- Обхід дерев і графів (DOM, AST, файлові системи).
- Divide and Conquer: швидке/злиттьове сортування, бінарний пошук.
- Динамічне програмування (згори вниз із мемоізацією).

### Приклад 2: обхід дерева (DFS)

```
const tree = {
  value: 1,
  children: [
    { value: 2, children: [ { value: 4, children: [] } ] },
    { value: 3, children: [] }
  ]
};

function dfs(node, visit) {
  if (!node) return; // базовий випадок: порожній вузол
  visit(node.value);
  for (const child of node.children) {
    dfs(child, visit); // рекурсивний крок
  }
}

dfs(tree, v => console.log(v)); // 1, 2, 4, 3
```

Ітераційний варіант із явним стеком:

```
function dfsIter(root, visit) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    visit(node.value);
    // Кладемо дітей у зворотному порядку, щоб лівий оброблявся першим
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

dfsIter(tree, v => console.log(v)); // 1, 2, 4, 3
```

### Оптимізація: хвостова рекурсія

Хвостова рекурсія - коли рекурсивний виклик є останньою операцією функції. Теоретично це дозволяє компілятору не нарощувати стек (tail call optimization), але в більшості JS-рушіїв TCO не увімкнено, тому розраховувати на економію стека в продакшені не варто.

```
function sumTo(n, acc = 0) {
  if (n === 0) return acc;        // базовий випадок
  return sumTo(n - 1, acc + n);    // хвостовий виклик
}

console.log(sumTo(5)); // 15
// У JS це все одно може переповнити стек при великих n.
```

### Мемоізація: прискорюємо експоненційну рекурсію

Наївне обчислення чисел Фібоначчі рекурсією дає експоненційний час через повторні обчислення. Мемоізація знижує складність до O(n) за часом і O(n) за пам'яттю.

```
const fib = (function () {
  const memo = new Map([[0, 0], [1, 1]]);
  return function f(n) {
    if (n < 0) throw new Error('n must be >= 0');
    if (memo.has(n)) return memo.get(n);
    const val = f(n - 1) + f(n - 2);
    memo.set(n, val);
    return val;
  };
})();

console.log(fib(10)); // 55
```

### Переваги і недоліки рекурсії

- Плюси: простота і виразність коду для ієрархічних структур; природний опис алгоритмів Divide and Conquer.
- Мінуси: накладні витрати на виклики; ризик переповнення стека; іноді складніше налагоджувати; без мемоізації можливі експоненційні повтори.

### Рекурсія vs ітерація: як обрати

- Якщо структура задачі ієрархічна (дерево/граф) - рекурсія часто чистіша.
- Якщо глибина може бути великою - перевагу віддають ітерації (або власному стеку).
- Якщо важлива продуктивність - порівняйте накладні витрати викликів із вигодою читабельності та простоти.

### Часті помилки і як їх уникати

- Немає базового випадку, або він недосяжний - призводить до нескінченної рекурсії і Stack Overflow.
- Немає прогресу до бази (наприклад, забули зменшити n) - ті самі наслідки.
- Повторні обчислення однакових підзадач - використовуйте мемоізацію або DP.

### Поради на співбесіді

1. Одразу сформулюйте базовий випадок і прогрес до нього.
2. Оцініть час і пам'ять: складність за глибиною стека.
3. Проговоріть граничні випадки (порожні структури, n=0, n=1).
4. За потреби запропонуйте ітераційний варіант або мемоізацію.

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

Для рев’юера

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

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