Функція Фібоначчі (рекурсія vs динаміка)

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

Коротке пояснення

Фібоначчі – послідовність, у якій кожен наступний елемент дорівнює сумі двох попередніх. Алгоритм обчислює n‑й член, починаючи з 0 і 1.

Аналогія

Уявіть, що ви підраховуєте кількість кроків у сходинках: кожен новий крок – це сума двох попередніх.

Коли застосовувати

• Потрібно знайти n‑й член послідовності Фібоначчі.
• Вхід – невелике ціле число (наприклад, до 40).
• Потрібна швидка відповідь без надмірного використання пам’яті.
• Не потрібна точність для дуже великих n (наприклад, > 90), коли числа виходять за межі типу Number.

Кроки алгоритму (рекурсія)

1. Якщо n дорівнює 0 або 1, повернути n.
2. Інакше обчислити fib(n‑1) і fib(n‑2).
3. Повернути суму результатів кроку 2.

Кроки алгоритму (динаміка – ітерація)

1. Ініціалізувати prev = 0, curr = 1.
2. Для i від 2 до n виконувати:
   • temp = curr;
   • curr = prev + curr;
   • prev = temp.
3. Повернути curr (або prev, якщо n == 0).

Візуальна інтуїція (текстова)

n=5
prev=0, curr=1
i=2: temp=1 → curr=1, prev=1
i=3: temp=1 → curr=2, prev=1
i=4: temp=2 → curr=3, prev=2
i=5: temp=3 → curr=5, prev=3
результат = 5

Складність

• Рекурсивний варіант: O(2^n) часу, O(n) пам’яті (через стек).
• Ітеративний варіант: O(n) часу, O(1) пам’яті.

Код (js)

// Функція, що обчислює n‑й член послідовності Фібоначчі
function fibIterative(n) {
  // Якщо запитуємо перший або другий елемент, повертаємо їх без обчислень
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Ініціалізуємо змінні для двох попередніх членів
  let prev = 0; // fib(0)
  let curr = 1; // fib(1)

  // Проходимо від 2 до n, обчислюючи новий член як суму двох попередніх
  for (let i = 2; i <= n; i++) {
    const next = prev + curr; // новий член
    prev = curr;              // оновлюємо попередній
    curr = next;              // ставимо новий як поточний
  }

  // Після завершення циклу curr містить fib(n)
  return curr;
}

// Тестовий приклад
console.log(fibIterative(10)); // очікуваний результат: 55

Типові помилки і поради

1. Переповнення стеку – рекурсивний варіант працює лише для невеликих n; використовуйте ітерацію або мемоізацію.
2. Неправильне ініціалізування – не забудьте обробити випадки n = 0 і n = 1, інакше цикл не запрацює.
3. Використання глобальних змінних – залишайте змінні локальними, щоб уникнути конфліктів.
4. Пам’ять – ітеративний підхід потребує лише дві змінні, тоді як рекурсія зберігає стек.
5. Оптимізація – можна використовувати мемоізацію (об’єкт або Map) для збереження вже обчислених значень.

Перевір себе

1. Яка складність ітеративного підходу до обчислення fib(n)?
2. Чому рекурсивний варіант має експоненційну складність?