JavaScript: memoization trades memory for time

Count the calls made by a naive recursive Fibonacci and a memoized one.

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");

fib(25) naive: 75025 in 242785 calls
fib(25) memo:  75025 in 49 calls

Explanation

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.

Memoization stores each computed answer in a Map and reuses it. Each value of n is computed once, so the number of calls becomes linear in n, at the cost of O(n) memory for the cache and recursion depth. This is a time–space trade-off, and the idea behind dynamic programming for problems with overlapping subproblems.

—

—

fib(25) naive: 75025 in 242785 calls

fib(25) naive: 75025 in 242785 calls
fib(25) memo:  75025 in 49 calls

Cost and common mistakes

Naive: Θ(φⁿ) time. Memoized: Θ(n) time and Θ(n) space.

• Memoizing a function with side effects, or one that depends on outside state, can return stale answers.
• Deep recursion can overflow the call stack in JavaScript. A bottom-up loop avoids that.
• Numbers above 2^53 lose precision. Use BigInt for large Fibonacci values.

Try it yourself

How many calls does fibMemo(10) make?

Further reading

• MDN JavaScript guide (external)
• Node.js API documentation (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)