Dynamic Programming

Call Tree — fib(6)

Debugger · v1.0

LIVE

1function fib(n, memo = {}) {

2 // Base cases

3 if (n <= 1) return n;

5 // Check memo (cache)

6 if (memo[n] !== undefined)

7 return memo[n]; // ← cache HIT

9 // Recurse and store result

10 memo[n] = fib(n-1, memo)

11 + fib(n-2, memo);

13 return memo[n]; // ← new result cached

14}

Debugger · v1.0

LIVE

1function fib(n, memo = {}) {

2 // Base cases

3 if (n <= 1) return n;

5 // Check memo (cache)

6 if (memo[n] !== undefined)

7 return memo[n]; // ← cache HIT

9 // Recurse and store result

10 memo[n] = fib(n-1, memo)

11 + fib(n-2, memo);

13 return memo[n]; // ← new result cached

14}

State Inspector

No variables in scope.

n =6

210

Dynamic Programming

Fibonacci with Memoization

Step 1 of 6

Memoization (Top-Down DP) caches the result of each sub-problem the first time it's solved. When the same sub-problem appears again, the answer is returned directly from the cache — no recomputation needed.

The Overlapping Sub-Problems Problem

Naive recursive fib(n) recomputes fib(2), fib(3)… exponentially many times. For fib(5), fib(3) is computed twice and fib(2) is computed three times. Time complexity: O(2ⁿ).