JavaScript: memoization trades memory for time
The naive recursive Fibonacci recomputes the same subproblems again and again. fib(n) calls fib(n − 1) and fib(n − 2), and those calls overlap heavily, so the number of calls grows exponentially, roughly like 1.6 raised to n.
JavaScript
let naiveCalls = 0;
function fibNaive(n) {
naiveCalls++;
return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
let memoCalls = 0;
const cache = new Map();
function fibMemo(n) {
memoCalls++;
if (n < 2) return n;
if (cache.has(n)) return cache.get(n);
const value = fibMemo(n - 1) + fibMemo(n - 2);
cache.set(n, value);
return value;
}
console.log("fib(25) naive: " + fibNaive(25) + " in " + naiveCalls + " calls");
console.log("fib(25) memo: " + fibMemo(25) + " in " + memoCalls + " calls");