Card 01/ 08
Recursion: A Function That Calls Itself on a Smaller Input
A base case stops the calls, and each recursive case moves closer to it.
A recursive function is a function that calls itself, each time on a smaller input, until it reaches an input small enough to answer directly. This card covers the two parts every recursive function has, and what the computer keeps for each call while that call waits for the one inside it to finish.
The base case is the input the function answers without calling itself. The recursive case is every other input: the function calls itself on a smaller input and uses the answer it gets back. sum_to(n) below adds the whole numbers from 1 to n. Its base case is n = 0, whose sum is 0. Its recursive case says that the sum to n is n plus the sum to n - 1, and n - 1 is one step closer to 0. The listing was run, and it printed the sum to 3.
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(3))6Each call gets its own frame: a small record holding that call's parameters, its local variables and the place in the code to carry on from. The frames sit on the call stack, which is a stack in the usual sense: a call pushes a new frame on top, and returning pops that frame off and hands its result to the frame underneath. That is how four calls to sum_to can be paused at once, each with its own n, without one overwriting another. The steps show the stack, top frame first, as an instrumented copy of the function printed it.
The call stack while sum_to(3) runs, top frame first
Call sum_to(3)
The first call pushes one frame. n is 3, which is not the base case, so the call asks for sum_to(2) and waits.
sum_to(n=3): waiting for sum_to(2)Call sum_to(2)
A second frame goes on top with its own n, 2. The frame for 3 is paused underneath it, and its n is still 3.
sum_to(n=2): waiting for sum_to(1)
sum_to(n=3): waiting for sum_to(2)Call sum_to(1)
A third frame, with n of 1, asks for sum_to(0).
sum_to(n=1): waiting for sum_to(0)
sum_to(n=2): waiting for sum_to(1)
sum_to(n=3): waiting for sum_to(2)Call sum_to(0)
n is 0, the base case, so this call returns 0 without calling again. Four frames are on the stack, the most there will be.
sum_to(n=0): base case, returns 0
sum_to(n=1): waiting for sum_to(0)
sum_to(n=2): waiting for sum_to(1)
sum_to(n=3): waiting for sum_to(2)sum_to(0) returns 0
The top frame is popped, and its 0 goes to the frame for 1, which can now finish its addition.
sum_to(n=1): 1 + 0, returns 1
sum_to(n=2): waiting for sum_to(1)
sum_to(n=3): waiting for sum_to(2)sum_to(1) returns 1
The frame for 2 receives 1 and adds its own n.
sum_to(n=2): 2 + 1, returns 3
sum_to(n=3): waiting for sum_to(2)sum_to(2) returns 3
The first frame adds 3 and 3, and returns 6. Once it returns, the stack is empty.
sum_to(n=3): 3 + 3, returns 6The calls go down to the base case, and the answers come back up in the reverse order, each frame finishing the work it paused. Russian dolls picture the way down well: open each doll to find a smaller one, until the smallest opens to nothing. The picture breaks on the way back up. A doll hands nothing to the doll around it, while every call returns a result to the frame that made it, and that frame still has work to do with the result, here an addition.
Two rules follow. The base case must exist, and every recursive case must move closer to it, or the calls never stop and the call stack runs out of room. And a recursion n calls deep holds n + 1 frames at once, so it uses O(n) extra memory even though sum_to creates no list.
← → move through sections and cards