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.

You are at the back of a queue and want to know how many people are in it. You cannot see the front. So you ask the person ahead of you, how many people are in front of you? They do not know either, so they ask the person ahead of them, and so on. The very first person in the queue answers at once: zero. Then the answers come back down the line, each person adding one for themselves, until the answer reaches you.

• -The first person, who can answer directly, is the base case.
• -Everyone else asking the person in front and adding one is the recursive case.
• -Each person waiting for an answer is a pending call on the call stack.
• -The answers coming back down the line are the calls returning in reverse order.

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.

When you meet a new problem, three questions turn it into a recursive function:

• -What is the smallest version I can answer directly? That is the base case.
• -How do I make the problem a bit smaller? Remove one item, halve the number, step down one level.
• -If I trust the answer to the smaller problem, how do I build the answer to mine? That is the recursive case, and trusting it is the 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.

Reading a trace is useful, but watching one is better. Step through the call stack in the demo below, and notice how the stack grows by one frame for every call that is waiting, then shrinks as each call returns.

The three questions work on anything. To add up a list, the smallest version is an empty list, which sums to 0. To make it smaller, drop the first item. And the answer is the first item plus the sum of the rest:

• -sum_list([1, 2, 3]) is 1 + sum_list([2, 3]).
• -sum_list([2, 3]) is 2 + sum_list([3]), and sum_list([3]) is 3 + sum_list([]).
• -sum_list([]) hits the base case and returns 0, so the answers unwind: 3 + 0 = 3, then 2 + 3 = 5, then 1 + 5 = 6.

One practical note: items[1:] makes a copy of the rest of the list on every call, so this version does O(n squared) work in total. It is a clean way to learn recursion, not the fastest way to sum a list.

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.