JavaScript · Course navigation

JavaScript: memoization trades memory for time

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

On this page

Before you start

JavaScript functions, recursion, and Map.

Count the calls made by a naive recursive Fibonacci and a memoized one.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Output

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1let naiveCalls = 0;

2function fibNaive(n) {

3 naiveCalls++;

4 return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);

5}

7let memoCalls = 0;

8const cache = new Map();

9function fibMemo(n) {

10 memoCalls++;

11 if (n < 2) return n;

12 if (cache.has(n)) return cache.get(n);

13 const value = fibMemo(n - 1) + fibMemo(n - 2);

14 cache.set(n, value);

15 return value;

16}

18console.log("fib(25) naive: " + fibNaive(25) + " in " + naiveCalls + " calls");

19console.log("fib(25) memo: " + fibMemo(25) + " in " + memoCalls + " calls");

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Every call, including repeated ones, is counted.	`—`	—
A value computed before is returned immediately without recursing again.	`—`	—
The naive version makes 242785 calls for the same answer.	`—`	fib(25) naive: 75025 in 242785 calls
The memoized version needs only 49 calls, about 2n.	`—`	fib(25) naive: 75025 in 242785 calls fib(25) memo: 75025 in 49 calls

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

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?

Reveal answer and reasoning

19 calls: about 2n − 1, since each value is computed once and looked up once.