15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Memoization stores the result of each recursive call under its input, so a repeated subproblem returns the stored answer instead of being recomputed. Check the cache before recursing, and store the result only after computing it. For Fibonacci it cuts the O(2^n) call tree to O(n) work, with O(n) cache and O(n) call-stack space.
| Cache key | The subproblem input; for Fibonacci that is n |
|---|---|
| Invariant | If cache[k] is present, it equals fib(k) |
| Time (memoized fib) | O(n) with an array or expected O(1) map lookups; O(n^2) with worst-case O(n) lookups |
| Auxiliary space | O(n) cache plus O(n) call stack |
| Use when | The recursion tree has repeated subproblems |
Assume you can design a recursive function with:
For Fibonacci, use these mathematical definitions:
A direct recursive implementation follows that recurrence. Its recursion tree contains repeated calls.
For example, when computing fib(4), the value fib(2) is needed in two places. The mathematical recurrence remains unchanged. Repeated computation causes the extra work.
Memoization retains the recursive structure and remembers a result after computing it once.
The subproblem input is the cache key. For Fibonacci, the complete subproblem is identified by n, so the cache key is also n.
Use this example throughout:
1memoFib(4)
2initial cache: empty
3base values: fib(0) = 0, fib(1) = 1Without a cache, the recursive requests form this tree:
1fib(4)
2├── fib(3)
3│ ├── fib(2)
4│ │ ├── fib(1)
5│ │ └── fib(0)
6│ └── fib(1)
7└── fib(2)
8 ├── fib(1)
9 └── fib(0)There are two requests for fib(2):
fib(3).fib(4).Both requests ask the same question: “What is Fibonacci value 2?” The answer is always 1.
Store the first result instead of expanding the second fib(2) call again:
1cache[2] = 1The later request returns the stored value.
A cache entry has two pieces of information:
1key: 2
2value: 1The key identifies the subproblem. The value is the solved answer for that subproblem.
Start with no stored results.
1cache = {}Here are the calls and cache changes for memoFib(4).
| Step | Active request | Cache action | Cache after the step |
|---|---|---|---|
| 1 | Request memoFib(4) | 4 is absent: cache miss. Begin memoFib(3) + memoFib(2). | {} |
| 2 | Request memoFib(3) | 3 is absent: cache miss. Begin memoFib(2) + memoFib(1). | {} |
| 3 | Request memoFib(2) | 2 is absent: cache miss. Compute base values memoFib(1) = 1 and memoFib(0) = 0. Store cache[2] = 1. | {2 → 1} |
| 4 | Return to memoFib(3) | memoFib(1) returns 1. Now memoFib(3) = 1 + 1 = 2. Store cache[3] = 2. | {2 → 1, 3 → 2} |
| 5 | Request memoFib(2) from memoFib(4) | 2 is present: cache hit. Return 1 with no child calls. | {2 → 1, 3 → 2} |
| 6 | Return to memoFib(4) | memoFib(4) = 2 + 1 = 3. Store cache[4] = 3, then return 3. | {2 → 1, 3 → 2, 4 → 3} |
Step 5 returns immediately because key 2 is already present.
The first request for memoFib(2) expands into two base-case calls:
memoFib(4) misses on 4, 3 and 2, fills cache[2] = 1 and cache[3] = 2, then hits cache[2] and skips its subtree. The root stores cache[4] = 3.
The second request returns from the cache:
1memoFib(2) → cache hit → return 1The cache maintains this invariant:
Whenever
cache[k]is marked present, it equalsfib(k).
The invariant gives two rules.
cache[2] is present, returning its value returns the correct value of fib(2).For the example:
1cache[2] = 1 because fib(2) = fib(1) + fib(0) = 1 + 0
2cache[3] = 2 because fib(3) = fib(2) + fib(1) = 1 + 1
3cache[4] = 3 because fib(4) = fib(3) + fib(2) = 2 + 1The cache invariant is:
Whenever
cache[k]is marked present, it equalsfib(k); a cache hit returns that correct value, and a cache miss stores a value only after correctly computingfib(k).
A numeric value is not itself a presence check.
For example, fib(0) is a valid result of 0. If an implementation uses this incorrect test:
1if cache[n]then a stored 0 may be mistaken for “not present.” Use one of these instead:
n exist?”Start from the ordinary Fibonacci recurrence:
1fib(n) = fib(n - 1) + fib(n - 2)Check the cache before recursive expansion:
1Have we already solved the subproblem for this n?There are two possible answers.
If key n is present:
1return cache[n]Do not make child calls. The stored value already answers the current subproblem.
If key n is absent:
n is 0 or 1.memoFib(n - 1).memoFib(n - 2).n.The recursive recurrence remains the same. Memoization reuses earlier results instead of recomputing them.
Use a fresh cache for each independent top-level call. For example, a call to memoFib(4) should create its own cache unless the API explicitly promises shared-cache behavior.
The public function creates a new cache for one computation.
1function memoFib(n) -> integer
2 input:
3 n, a nonnegative integer
4 returns:
5 fib(n)
6 mutation:
7 creates and mutates a fresh cache for this call only
8
91. cache = empty map from integer to integer
102. return memoFibHelper(n, cache)The helper shares that cache across all recursive calls belonging to the same top-level request.
1function memoFibHelper(n, cache) -> integer
2 input:
3 n, a nonnegative integer
4 cache, a mutable map from integer keys to integer values
5 returns:
6 fib(n)
7 mutation:
8 may add computed non-base Fibonacci values to cache
9 helper contract:
10 every present entry cache[k] equals fib(k)
11
121. if n == 0
132. return 0
14
153. if n == 1
164. return 1
17
185. if cache contains key n
196. return cache[n]
20
217. left = memoFibHelper(n - 1, cache)
228. right = memoFibHelper(n - 2, cache)
239. value = left + right
2410. cache[n] = value
2511. return valueThe pseudocode returns base cases directly and stores non-base results consistently.
An implementation may also store base cases. That implementation must distinguish a present value 0 from an absent entry.
Run memoFib(4) using the line numbers above.
Initial call:
1memoFib(4)| Action | Current call | Executed line(s) | Result or cache state |
|---|---|---|---|
| Create fresh cache. | memoFib(4) | 1 | cache = {} |
| Start helper. | memoFibHelper(4, cache) | 2 | Continue with n = 4 |
4 is not a base case. | memoFibHelper(4, cache) | 1–4 | No return |
4 is not in the cache. | memoFibHelper(4, cache) | 5 | Cache miss |
| Compute left child. | memoFibHelper(4, cache) | 7 | Call memoFibHelper(3, cache) |
3 is not a base case or cache hit. | memoFibHelper(3, cache) | 1–5 | Cache remains {} |
| Compute left child. | memoFibHelper(3, cache) | 7 | Call memoFibHelper(2, cache) |
2 is not a base case or cache hit. | memoFibHelper(2, cache) | 1–5 | Cache remains {} |
| Compute left child. | memoFibHelper(2, cache) | 7 | Call memoFibHelper(1, cache) |
| Base case. | memoFibHelper(1, cache) | 3–4 | Return 1 |
| Receive left value. | memoFibHelper(2, cache) | 7 | left = 1 |
| Compute right child. | memoFibHelper(2, cache) | 8 | Call memoFibHelper(0, cache) |
| Base case. | memoFibHelper(0, cache) | 1–2 | Return 0 |
| Receive right value. | memoFibHelper(2, cache) | 8 | right = 0 |
| Add child values. | memoFibHelper(2, cache) | 9 | value = 1 + 0 = 1 |
| Store result. | memoFibHelper(2, cache) | 10 | cache = {2 → 1} |
| Return result. | memoFibHelper(2, cache) | 11 | Return 1 |
| Receive left value. | memoFibHelper(3, cache) | 7 | left = 1 |
| Compute right child. | memoFibHelper(3, cache) | 8 | Call memoFibHelper(1, cache) |
| Base case. | memoFibHelper(1, cache) | 3–4 | Return 1 |
| Add child values. | memoFibHelper(3, cache) | 9 | value = 1 + 1 = 2 |
| Store result. | memoFibHelper(3, cache) | 10 | cache = {2 → 1, 3 → 2} |
| Return result. | memoFibHelper(3, cache) | 11 | Return 2 |
| Receive left value. | memoFibHelper(4, cache) | 7 | left = 2 |
| Compute right child. | memoFibHelper(4, cache) | 8 | Call memoFibHelper(2, cache) |
Not a base case; key 2 is present. | memoFibHelper(2, cache) | 1–5 | Cache hit |
| Return stored result. | memoFibHelper(2, cache) | 6 | Return 1 |
| Receive right value. | memoFibHelper(4, cache) | 8 | right = 1 |
| Add child values. | memoFibHelper(4, cache) | 9 | value = 2 + 1 = 3 |
| Store result. | memoFibHelper(4, cache) | 10 | cache = {2 → 1, 3 → 2, 4 → 3} |
| Return result. | memoFibHelper(4, cache) | 11 | Return 3 |
The final result is:
1memoFib(4) = 3The stored non-base results are:
1cache[2] = 1
2cache[3] = 2
3cache[4] = 3We show that memoFib(n) returns fib(n) for every nonnegative integer n.
The cache invariant is the key fact:
Whenever
cache[k]is present, it equalsfib(k).
Because the code is recursive, use a structural argument over the recursive calls.
If n == 0, lines 1–2 return 0, which equals fib(0).
If n == 1, lines 3–4 return 1, which equals fib(1).
So the helper is correct for both base inputs.
Suppose n >= 2 and key n is already present.
By the cache invariant:
1cache[n] = fib(n)Lines 5–6 return cache[n]. Therefore, the helper returns fib(n) without further recursion.
Suppose n >= 2 and key n is absent.
The helper calls:
1memoFibHelper(n - 1, cache)
2memoFibHelper(n - 2, cache)Both inputs are smaller than n. Their returned values are therefore:
1left = fib(n - 1)
2right = fib(n - 2)Line 9 computes:
Line 10 stores this correct value under key n, preserving the cache invariant. Line 11 returns that value, so the helper returns fib(n).
For every non-base call, recursive calls use n - 1 and n - 2, both smaller than n. Since n is nonnegative, recursive paths eventually reach 0 or 1, which return directly.
Therefore, memoFib(n) terminates and returns the correct Fibonacci value for every nonnegative integer n.
Count distinct subproblems for input n.
The possible Fibonacci inputs are:
10, 1, 2, ..., nThere are:
possible keys.
For each non-base state:
Later requests for the same state are cache hits.
With an array cache, each lookup takes time. With a hash-map cache, lookup takes expected time; a worst-case lookup can take .
Under the array model, or under expected hash-map lookup time, the work is proportional to the number of distinct states:
With worst-case hash-map lookup time, up to lookups can each take , giving:
For memoFib(4), the computed non-base states are:
12, 3, 4The later request for 2 performs a lookup and does not expand into 1 and 0.
The cache can contain results for inputs from 0 through n, so it uses:
space.
The recursive call depth can still reach a chain like:
1memoFib(n)
2memoFib(n - 1)
3memoFib(n - 2)
4...
5memoFib(1)So the call stack can also use:
auxiliary space.
Together:
auxiliary space in total.
Incorrect presence check with numeric storage:
1if cache[n]
2 return cache[n]Smallest exposing input:
1memoFib(0) after caching 0Wrong state:
1cache[0] = 0The condition treats 0 as false, so it acts as though the entry is missing.
Correction: use a separate presence marker, a sentinel that cannot be a Fibonacci result, or a map membership check:
1if cache contains key n
2 return cache[n]Incorrect order:
1left = memoFibHelper(n - 1, cache)
2right = memoFibHelper(n - 2, cache)
3
4if cache contains key n
5 return cache[n]Exposing input:
1memoFib(4), after fib(2) has already been cachedWrong behavior:
1memoFib(2) expands into memoFib(1) and memoFib(0) againThe final numeric answer may still be 3. Repeated child expansion still occurs, so the cache does not prevent repeated work.
Correction: perform the cache lookup before recursive calls.
1if cache contains key n
2 return cache[n]Incorrect store:
1cache[0] = valueExposing sequence:
1memoFib(3)
2memoFib(4)Wrong state after computing memoFib(3):
1cache[0] = 2A later lookup can incorrectly reuse 2 as though it belonged to another Fibonacci input.
Correction: store and retrieve with the subproblem key:
1cache[n] = valueIncorrect base cases:
1if n == 0
2 return 1
3if n == 1
4 return 1Exposing input:
1memoFib(2)Wrong computation:
1memoFib(2) = 1 + 1 = 2But the correct value is:
1fib(2) = fib(1) + fib(0) = 1 + 0 = 1Correction:
1fib(0) = 0
2fib(1) = 1| Input | Expected return | Relevant behavior |
|---|---|---|
memoFib(0) | 0 | Returns the first base value. |
memoFib(1) | 1 | Returns the second base value. |
memoFib(2) | 1 | Computes and stores or consistently recognizes key 2. |
memoFib(4) | 3 | Has a cache hit for fib(2) during the trace. |
Cached fib(0) | 0 | A stored zero must count as present when base values are cached. |
Implement memoFib(n) for a nonnegative integer n with a per-call cache.
The tests verify:
1memoFib(0) == 0
2memoFib(1) == 1
3memoFib(4) == 3
4memoFib(10) == 55Instrumentation also verifies that each non-base key from 2 through 10 is computed at most once.
Your implementation contract must include:
memoFib(n) call,n,fib(0) = 0 and fib(1) = 1,1def memo_fib_helper(n, cache):
2 if n == 0:
3 return 0
4 if n == 1:
5 return 1
6 if n in cache: # membership check, so a stored 0 still counts
7 return cache[n]
8 left = memo_fib_helper(n - 1, cache)
9 right = memo_fib_helper(n - 2, cache)
10 value = left + right
11 cache[n] = value
12 return value
13
14def memo_fib(n):
15 return memo_fib_helper(n, {}) # fresh cache for each top-level call
16
17cache = {}
18result = memo_fib_helper(4, cache)
19print(result, len(cache), memo_fib(10))1import java.util.HashMap;
2import java.util.Map;
3
4public class Main {
5 static int memoFibHelper(int n, Map<Integer, Integer> cache) {
6 if (n == 0) return 0;
7 if (n == 1) return 1;
8 if (cache.containsKey(n)) return cache.get(n); // membership check, so a stored 0 still counts
9 int left = memoFibHelper(n - 1, cache);
10 int right = memoFibHelper(n - 2, cache);
11 int value = left + right;
12 cache.put(n, value);
13 return value;
14 }
15
16 static int memoFib(int n) {
17 return memoFibHelper(n, new HashMap<>()); // fresh cache for each top-level call
18 }
19
20 public static void main(String[] args) {
21 Map<Integer, Integer> cache = new HashMap<>();
22 int result = memoFibHelper(4, cache);
23 System.out.println(result + " " + cache.size() + " " + memoFib(10));
24 }
25}1#include <iostream>
2#include <unordered_map>
3using namespace std;
4
5int memoFibHelper(int n, unordered_map<int, int>& cache) {
6 if (n == 0) return 0;
7 if (n == 1) return 1;
8 if (cache.count(n)) return cache[n]; // membership check, so a stored 0 still counts
9 int left = memoFibHelper(n - 1, cache);
10 int right = memoFibHelper(n - 2, cache);
11 int value = left + right;
12 cache[n] = value;
13 return value;
14}
15
16int memoFib(int n) {
17 unordered_map<int, int> cache; // fresh cache for each top-level call
18 return memoFibHelper(n, cache);
19}
20
21int main() {
22 unordered_map<int, int> cache;
23 int result = memoFibHelper(4, cache);
24 cout << result << " " << cache.size() << " " << memoFib(10) << endl;
25}1function memoFibHelper(n, cache) {
2 if (n === 0) return 0;
3 if (n === 1) return 1;
4 if (cache.has(n)) return cache.get(n); // membership check, so a stored 0 still counts
5 const left = memoFibHelper(n - 1, cache);
6 const right = memoFibHelper(n - 2, cache);
7 const value = left + right;
8 cache.set(n, value);
9 return value;
10}
11
12function memoFib(n) {
13 return memoFibHelper(n, new Map()); // fresh cache for each top-level call
14}
15
16const cache = new Map();
17const result = memoFibHelper(4, cache);
18console.log(`${result} ${cache.size} ${memoFib(10)}`);From "memo": the function writes a note of each result and reads it back later. It is a different word from memorization, which means learning by heart.
It is the top-down style of DP. You keep the recursive solution and add a cache keyed by the subproblem. The fib(2) subproblem from fib(4) is computed once, and the second request is a cache hit.
Memoization starts from the big problem and recurses down, filling the cache on demand. Tabulation fills a table bottom-up from the base cases with a loop. Both visit each distinct subproblem once, but tabulation uses no recursion stack.
Because 0 is a valid stored result and also falsy in many languages. The test treats a cached 0 as missing. Use a membership check, such as n in cache, or a sentinel that cannot be an answer.
A shared cache keeps entries from earlier requests alive and ties results to hidden state. A fresh cache per call is simple and correct. Share one only when the API promises it.