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

Повне пояснення

Що це і навіщо

Рекурсія — механізм, коли функція викликає саму себе. Це корисно для задач, що мають ітеративну структуру: дерев’яні об’єкти, графи, пошук у бінарному дереві тощо.

Ключові принципи

• Базовий випадок (base case) – умова, при якій рекурсія завершується.
• Рекурсивний крок – виклик функції з новим аргументом, що наближає до базового випадку.
• Стек викликів – кожен рекурсивний виклик додає новий кадр до call stack.

Як це працює

1. Функція перевіряє базовий випадок.
2. Якщо умова не виконана, виконується рекурсивний крок і функція знову викликає саму себе.
3. Коли базовий випадок досягається, стек розпаковується, повертаючи значення.

Практика і реалізація

JavaScript / TypeScript

function factorial(n: number): number {
  return n <= 1 ? 1 : n * factorial(n - 1);
}

function sumArray(arr: number[], idx = 0): number {
  if (idx >= arr.length) return 0;
  return arr[idx] + sumArray(arr, idx + 1);
}

Тестування

import { describe, it, expect } from 'vitest';

describe('factorial', () => {
  it('returns 120 for 5', () => {
    expect(factorial(5)).toBe(120);
  });
});

Оптимізація

• Тейл‑рекурсія (tail recursion) дозволяє компілятору оптимізувати стек, але в JavaScript це ще не підтримується.
• Мемоізація зменшує кількість повторних обчислень, особливо у функціях Фібоначчі.

Часті помилки

1. Відсутність базового випадку → StackOverflowError.
2. Неправильна зміна аргументу → нескінченний цикл.
3. Перевищення глибини рекурсії у великих даних → використання ітераційного підходу.

Дизайн‑рішення

• Для обчислення великих факторіалів використовуйте BigInt.
• У випадку обходу графа застосуйте DFS рекурсивно, але з обмеженням глибини.

Cheatsheet

• Базовий випадок: if (condition) return value;
• Рекурсивний крок: return expression + recursiveCall(newArg);
• Мемоізація:

const memo = new Map();
function fib(n: number): number {
  if (memo.has(n)) return memo.get(n)!;
  const result = n < 2 ? n : fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}

Follow‑up питання

• Як обмежити глибину рекурсії у JavaScript?
• Чому tail recursion не працює в сучасних браузерах?