Fibonacci
Her sayı önceki ikisinin toplamı: 0, 1, 1, 2, 3, 5, 8, 13…
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
Sorun: eksponansiyel patlama
fib(50) bu haliyle milyonlarca kez kendini çağırır.
Çözüm: memoizasyon
Hesaplananları sakla, tekrar hesaplama:
const bellek = new Map();
function fib(n) {
if (n < 2) return n;
if (bellek.has(n)) return bellek.get(n);
const s = fib(n - 1) + fib(n - 2);
bellek.set(n, s);
return s;
}
Artık O(n)!