Fibonacci: rekurencja, pętla, pamięć

Algorytmy z egzaminu różnymi sposobami - JavaScript od podstaw: konsola (JavaScript)

Ciąg Fibonacciego: F(1) = F(2) = 1, a każdy następny to suma dwóch poprzednich. Rekurencja przepisuje definicję wprost, ale liczy to samo wiele razy: licznik wywołań rośnie lawinowo. Pętla pamięta tylko dwie ostatnie wartości i jest błyskawiczna. Trzecia wersja to rekurencja z pamięcią (obiekt `memo`): raz policzony wynik jest zapamiętany, więc każde F(n) liczy się tylko raz.

let calls = 0;
function fibRec(n) {
  calls++;
  if (n <= 2) return 1;
  return fibRec(n - 1) + fibRec(n - 2);
}

function fibLoop(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

const memo = {};
function fibMemo(n) {
  if (n <= 2) return 1;
  if (memo[n] === undefined) memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
  return memo[n];
}

console.log('Rekurencja F(20) =', fibRec(20), 'wywołań:', calls);
console.log('Pętla F(20) =', fibLoop(20), 'F(70) =', fibLoop(70));
console.log('Pamięć F(70) =', fibMemo(70), 'zapamiętanych:', Object.keys(memo).length);

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu JavaScript od podstaw: konsola·Zaloguj się, aby zapisać postęp na koncie.