Рекурсія простими словами — стек викликів, мемоізація та оптимізація хвостових викликів

1. Стек викликів

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

// Проста лінійна рекурсія
function factorial(n) {
  if (n <= 1) return 1;           // базовий випадок
  return n * factorial(n - 1);    // рекурсивний крок
}

2. Базові випадки та структурна індукція

Кожна рекурсивна функція повинна мати базовий випадок — умову завершення, що повертає значення без рекурсивного виклику. Без нього рекурсія працює нескінченно (на практиці — переповнення стека).

Коректність рекурсивних функцій зазвичай доводять методом структурної індукції:

1. Базовий випадок: Довести, що функція коректна для найменшого вхідного значення.
2. Індуктивний крок: Припустити, що функція коректна для всіх вхідних значень, менших за n. Довести, що вона коректна для n, використовуючи це припущення.

3. Деревоподібна рекурсія: пастка Фібоначчі

4. Мемоізація

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

// Мемоізований Фібоначчі (зверху вниз)
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
// O(n) час — кожне унікальне n обчислюється один раз
// O(n) пам'ять — memo зберігає n значень + глибина стека викликів O(n)

5. Динамічне програмування (знизу вгору)

ДП знизу вгору обчислює підзадачі по порядку від найменшої до найбільшої, зберігаючи лише необхідне. Повністю уникає накладних витрат рекурсії та глибини стека:

// ДП Фібоначчі знизу вгору — O(n) час, O(1) пам'ять
function fibDP(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];   // потрібні лише два останні значення
  }
  return b;
}

ДП знизу вгору лежить в основі: найкоротших шляхів Флойда-Воршелла, пошуку рядка Кнута-Морріса-Пратта, вирівнювання послідовностей (Сміта-Вотермана), оптимального двійкового дерева пошуку, розміну монет, задачі про рюкзак та алгоритму Вітербі у прихованих марковських моделях.

6. Оптимізація хвостових викликів

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

// Не хвостова рекурсія: множення виконується ПІСЛЯ повернення factorial
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);   // ← не хвостовий: "n *" виконується після повернення
}

// Хвостова рекурсія: акумулятор несе поточний добуток
function factTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factTail(n - 1, n * acc);   // ← хвостовий: останнє — це виклик
}
// З TCO: O(1) пам'ять стека — компілюється в цикл
// Специфікація JavaScript ES2015 вимагає TCO; V8 прибрав його у 2016 (обхід через ShadowRealm)

7. Взаємна рекурсія та трампліни

Взаємна рекурсія: функція A викликає B, яка викликає A. Приклад: `isEven(n) = isOdd(n-1); isOdd(n) = isEven(n-1)`. Створює глибокі стеки для великих n, навіть якщо кожна функція окремо є хвостовою рекурсією.

Трамплін — це цикл, який багаторазово викликає функцію, доки вона не поверне звичайне значення замість нової функції:

// Трамплін: перетворює глибоку рекурсію на стек O(1)
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

// Кожен крок повертає thunk (функцію без аргументів) замість прямого виклику
const isEven = trampoline(function _isEven(n) {
  if (n === 0) return true;
  return () => _isOdd(n - 1);    // повертаємо thunk, а не прямий виклик
});

Трампліни відокремлюють глибину рекурсії від глибини стека викликів. Цикл трампліна використовує стек O(1) під час обробки скільки завгодно глибокої взаємної рекурсії. Цей патерн часто застосовують у Scheme, Clojure та під час реалізації інтерпретаторів.