Що таке рекурсія?

АлгоритмиJunior~2 хв читання

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

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

Ключові елементи: базовий випадок, рекурсивний крок, гарантований прогрес до бази.
Підходить для задач із природною ієрархією: дерева, графи, розбиття і завоювання (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.

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

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

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

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

Premium

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