Lecture: Recursion
Lecture script · about 15–20 minutes spoken · Week 14
Opening
Picture a biology student with a folder of field photos. Inside the folder are some photos and two more folders, and inside those are more photos and more folders. To count every photo, you count the ones in front of you, and then you do the same job on each folder inside. The job holds a smaller copy of itself.
That idea has a name, and it's the subject of this lecture. In Week 7 you learned to write functions, to return values, and to picture each call as a frame with its own local variables. In Week 5 you met the loop that never stops. In Week 13 you met binary search, which keeps cutting a list in half. This week those ideas meet. A function is allowed to call itself, each of those calls gets its own frame, and a call that never stops is the same trouble as a loop that never stops. Next week, in the last module, you'll meet classes and objects.
Here's the plan. We'll meet a function that calls itself, give it two parts, and build factorial. Then we'll watch the frames pile up and unwind, compare recursion with a loop, sum your reading log, and break a recursion on purpose.
1. Meet a function that calls itself
Think of the start of a fun run. The starter calls 3, then 2, then 1, then shouts Go. Nobody hands the starter a list. Each number is followed by the same instruction: count down from one less.
That's recursion: a way of solving a problem in which a function calls itself on a smaller copy of the same problem, again and again, until the problem is small enough to answer at once. A recursive function is a function whose body contains a call to itself.
Here's the pinned example, a function called countdown. If n equals 0, it prints Go and stops. Otherwise it prints n and then calls countdown of n minus 1. That last line is a recursive call: a line inside a function that calls that same function.
Call countdown of 3. It prints 3 and calls countdown of 2. That prints 2 and calls countdown of 1. That prints 1 and calls countdown of 0. And countdown of 0 prints Go. The run displays four lines: 3, 2, 1, Go.
Pause and try this. The line that prints Go sits near the top of the function. So why is Go the last line of the output?
Think about which call reaches that line.
Here's the answer. Only the call with n equal to 0 reaches it, and that call starts last. Each earlier call printed its number first.
Same job, smaller input, and the smallest one says Go.
2. Give it two parts
A set of nesting dolls opens down to one solid doll that doesn't open. That solid doll is what lets you finish. A recursive function needs the same thing.
The base case is the part of a recursive function that answers without calling the function again, such as returning 1 when n equals 0; it is what lets the chain of calls stop. The recursive case is the part that calls the function again on a smaller input that moves toward the base case.
In countdown, the base case is the test for n equal to 0, which prints Go and returns. The recursive case is the part that prints n and calls countdown of n minus 1. Every call moves n one step closer to 0, so the base case is always reached.
Call countdown of 0 directly. The base case runs at once, and the run displays only Go.
People sometimes feel a small input doesn't need a base case, because a countdown from 3 is over so fast. But the computer does exactly what you wrote, not what you meant. Without that test for 0, nothing tells it to stop.
Pause and try this. In countdown, which part is the base case, and which part makes the input smaller?
Look for the line that answers without calling again.
Here's the answer. The base case is the test for n equal to 0, which prints Go. The recursive call, countdown of n minus 1, makes the input smaller.
Base case first; it's the floor the calls land on.
3. Build a value on the way back
Here's a counting puzzle. A playlist of 5 songs can play in many orders. The first slot can hold any of 5 songs, the next any of the 4 left, then 3, then 2, then 1. Multiply them: 5 times 4 times 3 times 2 times 1 is 120.
That product is a factorial: the product of every whole number from 1 up to n, so 5 factorial is 120; 0 factorial is 1 by definition, which makes it a natural base case.
Notice that 5 factorial is 5 times 4 factorial. Every factorial holds a smaller factorial inside it. So the pinned factorial function says: if n equals 0, return 1. Otherwise, return n times factorial of n minus 1.
Factorial of 0 goes straight to the base case and returns 1. Factorial of 5 can't answer at once. It asks for factorial of 4, which asks for factorial of 3, all the way down to factorial of 0. Then the answers come back up, and the run displays 120.
Pause and try this. Why must the base case return 1 and not 0?
Think about what every multiplication above it would become.
Here's the answer. If factorial of 0 returned 0, every product above it would be 0 too. Factorial of 1 must be 1 times factorial of 0, so factorial of 0 must be 1.
The value is built on the way back up, not on the way down.
4. Watch the call stack
Picture the pile of clean trays in a cafeteria. You add a tray on top, and you take one off the top, never from the middle.
Python keeps its unfinished calls the same way. The call stack is the pile of frames Python keeps for the calls that have started and not yet returned, with the newest call on top; a call adds a frame and a return removes it. Each frame has its own n, a local variable, exactly like Week 7. Nothing gets overwritten.
There's a pinned version of factorial that announces every call and every return, indented by depth. Run it on 5 and the first six lines are calls: factorial of 5, of 4, of 3, of 2, of 1, and of 0. That's six calls, each one waiting on the next. Then the returns come back in reverse. Factorial of 0 returns 1. Factorial of 1 returns 1 times 1, which is 1. Then 2 times 1 is 2, 3 times 2 is 6, 4 times 6 is 24, and 5 times 24 is 120. The returns read 1, 1, 2, 6, 24, 120.
If you paste that program into Python Tutor and step through it, you'll watch a new frame appear for every call and disappear for every return. And in countdown of 3, at the deepest moment, four frames are open at once: the calls with 3, 2, 1, and 0.
Pause and try this. How many calls does factorial of 5 make, and which call returns first?
Count from 5 down to the base case.
Here's the answer. Six calls, for n equal to 5, 4, 3, 2, 1, and 0. The call with 0 returns first, because it's on top of the stack.
Frames pile up on each call and come off on each return.
5. Notice what runs after the call
Imagine walking down a staircase and leaving a note on each step. On the way back up, you read the notes in the opposite order. Unwinding is the second half of a recursion, when the deepest call returns first and each waiting frame in turn finishes its remaining lines.
Here's a small change with a big effect. Take countdown and move the print of n below the recursive call. Call the new version countup. Now each call makes its recursive call first, and prints its number only afterward. So nothing prints until the base case prints Go. Then the frames unwind, and the run displays Go, 1, 2, 3. One moved line reversed the order.
There's a second lesson hiding in countdown. It prints, but it never returns a value. The call countdown of 3 runs off the end of its body, and its base case ends with a bare return, and both hand back None, the Week 7 value for "nothing." So if you store the result of countdown of 3 and print it, the run displays 3, 2, 1, Go, and then None. Factorial is different. It returns a number to the call waiting below it, and that's how 120 got built.
Pause and try this. In countup of 3, why does Go come out before the number 1?
Ask when each call prints its own number.
Here's the answer. Each call prints its number after its recursive call returns, so every number waits until the base case has printed Go.
Lines before the call run going down; lines after it run coming back.
6. Solve it both ways
You can climb a staircase by counting steps in a loop, or by saying "one step, then climb the rest." Either way, you reach the top.
Iteration is repeating a block of code with a loop such as for or while, as opposed to repeating work by having a function call itself; a problem solved both ways gives the same answer.
Here's a pinned function called sum to, which adds the whole numbers from 1 to n. The recursive version says: the sum up to 0 is 0, and otherwise it's n plus the sum up to n minus 1. The loop version keeps a running total over a range from 1 to n plus 1, so n itself is included. Both display 15 for 5, because 1 plus 2 plus 3 plus 4 plus 5 is 15. The recursive sum to 100 displays 5050. And a loop version of factorial displays 120, the same as the recursive one.
So recursion and a loop give the same answer, and neither one is always better.
Pause and try this. The recursive sum to 5 and the loop sum to 5 look nothing alike. What do they both display?
Add the numbers from 1 to 5.
Here's the answer. Both display 15. They carry out the same additions, one by calling itself and one by looping.
A loop and a recursion can walk the same road.
7. Sum your reading log
Picture a row of students passing quiz papers forward. Each one says, "count mine and add the count from everyone behind me." The last student, with nobody behind, says zero.
Your reading log does the same this week. Its daily list holds 12, 40, 25, 0, 33, 17, and 27 pages. The function total pages has a base case on the empty list, which returns 0. Otherwise it returns the first day plus the total pages of the rest of the list, using a slice that starts at index 1. The run displays 154, the same total the Week 9 loop found. On the empty list, it displays 0.
Each call hands on a list one item shorter, so the list shrinks toward empty. The slice builds a new list, so the daily list itself is never touched. Put a print at the top and run it on the first three days, 12, 40, and 25. You see four calls, the last one with the empty list. Then the returns add up to 77.
Pause and try this. Total pages on three days makes four calls. Where does the extra call come from?
Think about what the last call receives.
Here's the answer. The fourth call receives the empty list, the base case, which returns 0. Three days plus one empty list makes four calls.
Peel off the first, hand on the rest, and stop at empty.
8. Break it on purpose
A song set to repeat with no stop button keeps playing until someone pulls the plug. A recursion with no way to stop does the same, and Python is the one that pulls the plug.
Here's a pinned function called bad. It returns n plus bad of n minus 1, and it has no base case at all. Call bad of 5, and nothing prints. The calls go to 4, 3, 2, 1, 0, and on below 0, piling up frames until Python stops the program. Read the error from its last line, as you learned in Week 12. It names a RecursionError: the exception Python raises when a chain of recursive calls goes deeper than the interpreter's depth limit, which usually means the base case is missing or never reached.
That depth limit is the cap on how many calls can be open at once. Its exact number depends on the setup, so it's never something to memorize.
There's a quieter version of the bug. A sum to function can have a perfect base case and still fail, if its recursive call passes the same n instead of n minus 1. The input never shrinks, the base case is never reached, and the run stops with RecursionError too.
Pause and try this. A recursive function has a base case for 0, but its recursive call passes n unchanged. What happens when you call it on 5?
Ask whether n ever gets closer to 0.
Here's the answer. It stops with RecursionError. The input stays 5 on every call, so the base case is never reached.
No floor, or no step down, means no stop.
9. Choose recursion when it fits
Think back to the folder of field photos. A folder holds folders that hold folders, so a recursive description reads naturally. Binary search from Week 13 has the same shape: each step searches one half of a sorted list, and searching that half is a smaller copy of the same job.
You can write binary search as a recursive function with two base cases: an empty range returns minus 1, and a found target returns its index. On the sorted page counts from Week 13, it finds 21 at index 4 and reports minus 1 for 22, the same answers as the loop. It isn't faster. It makes the same comparisons, only described differently.
Now a chatbot. Suppose you ask one what countup of 3 prints, and it says the program counts down from 3 and then prints Go. You run it, and the output is Go, 1, 2, 3. The chatbot described the countdown it expected, not the code you gave it. One honest limit of this lecture: functions that call each other in turn, trees, and ways of remembering earlier answers come later, in a second course.
Pause and try this. The chatbot's description sounded reasonable. What settled the question?
Separate what the chatbot said from what the code did.
Here's the answer. The run settled it. Only running countup of 3 shows Go first and then 1, 2, 3.
Trust the run, not the description.
Closing
Let me pull it together. A recursive function calls itself on a smaller input, so countdown of 3 displays 3, 2, 1, Go. Every recursive function needs a base case that answers at once and a recursive case that moves toward it. Factorial of 5 is 120, built on the way back up. The call stack piles up six frames for factorial of 5 and unwinds them in reverse. Lines after a recursive call run on the way back, and a function that only prints returns None. Recursion and a loop give the same 15 and the same 120. Your reading log sums to 154 recursively. A missing base case, or an input that never shrinks, ends in RecursionError. And when a problem holds smaller copies of itself, recursion reads naturally, but the run is always the judge.
Next in this module come the slide deck, the Readings and Resources page, the lecture tutorial, the practice set, the quiz, and the Coding Lab. Then, in Week 15, on object-oriented programming, you'll bundle data and the functions that work on it into one thing.
Built with The Course Maker · samples.thecoursemaker.com