Recursive Thinking & the Call Stack

Recursion already appeared as a language feature in Phase 1. It is worth revisiting deliberately here as a full problem-solving strategy, because it underlies memoization later in this chapter, and reappears throughout the rest of this course.

Every correct recursive function needs exactly two pieces: a base case simple enough to answer directly, with no further recursion, and a recursive case that reduces the problem to a smaller version of itself, trusting the recursive call to solve that smaller version correctly - sometimes called the recursive leap of faith.

It helps to picture exactly what happens in memory: a call to factorial(n) cannot finish until factorial(n - 1) returns, so the interpreter must remember every in-progress call - stacked, quite literally, on the same call stack introduced conceptually back in the stacks module. Calling factorial(4) pushes factorial(4), which calls factorial(3), which calls factorial(2), which calls factorial(1), which hits the base case and returns 1 immediately. From there, each pending call resumes and multiplies, popping back off the stack in reverse order: factorial(2) returns 2 * 1 = 2, factorial(3) returns 3 * 2 = 6, and factorial(4) returns 4 * 6 = 24.

• -factorial(4) calls factorial(3) calls factorial(2) calls factorial(1), which returns 1 immediately.
• -factorial(2) resumes and returns 2 * 1 = 2.
• -factorial(3) resumes and returns 3 * 2 = 6.
• -factorial(4) resumes and returns 4 * 6 = 24.

Unlike factorial, which makes one recursive call per level, fib branches into TWO recursive calls per level, and each of those branches into two more. Computing fib(5) calls fib(4) and fib(3); fib(4) in turn calls fib(3) and fib(2) - notice fib(3) has already been computed once as part of fib(5)'s own branch, and now gets recomputed completely from scratch as part of fib(4)'s branch. It only gets worse deeper in the tree: fib(2) gets recomputed many times over, and fib(1) and fib(0) even more. The total number of calls roughly doubles with every increase in n, giving O(2^n) time overall - technically closer to the golden ratio raised to the n, but the same exponential shape either way.