fibMemo(6) makes the same two calls as fib, but writes every answer into a cache first. A call whose argument is already cached is a leaf: it returns the stored value without growing the tree. Cached values appear in the label as they arrive.
Recursion tree of memoized Fibonacci of 6.
fib(6) is not a base case and not cached, so it calls fib(5) first and fib(4) after that.
Call fib(6), which expands into two calls.
fib(5) is not a base case and not cached, so it calls fib(4) first and fib(3) after that.
Call fib(5), which expands into two calls.
fib(4) is not a base case and not cached, so it calls fib(3) first and fib(2) after that.
Call fib(4), which expands into two calls.
fib(3) is not a base case and not cached, so it calls fib(2) first and fib(1) after that.
Call fib(3), which expands into two calls.
fib(2) is not a base case and not cached, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1, stored in the cache before returning.
fib(2) returns 1.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
Both children are back: fib(3) = fib(2) + fib(1) = 2, stored in the cache before returning.
fib(3) returns 2.
fib(2) is in the cache already, 1. It returns at once: no subtree is built here.
Cache hit for fib(2).
The cached fib(2) = 1 goes straight back up.
fib(2) returns 1.
Both children are back: fib(4) = fib(3) + fib(2) = 3, stored in the cache before returning.
fib(4) returns 3.
fib(3) is in the cache already, 2. It returns at once: no subtree is built here.
Cache hit for fib(3).
The cached fib(3) = 2 goes straight back up.
fib(3) returns 2.
Both children are back: fib(5) = fib(4) + fib(3) = 5, stored in the cache before returning.
fib(5) returns 5.
fib(4) is in the cache already, 3. It returns at once: no subtree is built here.
Cache hit for fib(4).
The cached fib(4) = 3 goes straight back up.
fib(4) returns 3.
Both children are back: fib(6) = fib(5) + fib(4) = 8, stored in the cache before returning.
fib(6) returns 8.
fib(6) = 8 with 11 calls, 3 of them cache hits that stopped a subtree. Only 7 distinct arguments exist, so the tree has one expansion each: O(n) calls instead of the exponential tree of the plain version.
Result 8 after 11 calls.