Recursion· 20 min

Fibonacci with Memoization

Cache subproblem results — O(n) instead of O(2ⁿ)

Setup

Total calls: 1
Step 1 / 33

Current step

1 / 33

Call fib(5).

Step log

Push (call)Call StackPop (return)
Stack is empty
Top of stack = active call; bottom = first call (root)
fibonacci.java
1int fib(int n, Map<Integer,Integer> memo) {
2    if (memo.containsKey(n)) return memo.get(n);
3    if (n <= 1) return n;
4    int r = fib(n-1, memo) + fib(n-2, memo);
5    memo.put(n, r);
6    return r;
7}
● Java

Fibonacci (memoized)

Computes the nth Fibonacci number. Without memoization, time is O(2ⁿ); with memoization, O(n). Watch how cached results prevent redundant calls.

Time
O(n)
Space
O(n)
Calls so far
1
Stack depth
0
33 / 46