Why does asking for fib(6) — whose answer is just 8 — trigger fifteen separate calls, and where in the call tree does the naive version redo work it already finished?
Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.
You are handed two facts and nothing else: fib(7) is 13 and fib(8) is 21. Working only from the rule fib(n) = fib(n-1) + fib(n-2), walk the sequence forward until you reach fib(10).
The two values you were handed are already assigned for you. Assign the value of fib(10) to fib10. Do not look the sequence up — derive it.
Two base cases and a two-call recursive step
Write down fib(1) = 1, fib(2) = 1 and fib(n) = fib(n-1) + fib(n-2), then the four-line fib_recur whose branches mirror them line for line.
Hand-trace of fib_recur(6)
Draw the call tree for fib_recur(6), marking the order in which fib_recur(5) is fully resolved before fib_recur(4) begins and where each base case hands back 1.
Duplicated branches in the naive call tree
Record that the subtree under the right-hand fib_recur(4) repeats work already finished on the left, and count how many times fib_recur(3) is called in that trace.