Lecture notes · Programming in Python · Lecture 15

Recursion

MIT 6.100L Intro to CS and Programming using Python, lecture 15, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces recursion, a way to solve a problem by breaking it into a smaller version of the same problem, and compares it with the loop-based way of multiplying two numbers.

Key ideas

Recursion is a programming technique and a way to solve problems. It asks you to think about problems in a different way than loops do, so it takes some practice. 0:16
An iterative algorithm is code that uses a for loop or a while loop to repeat a task. Variables track the state of the computation, which means they change each time through the loop and hold the current result. 1:45
Multiplication can be built from addition: multiplying a by b means adding a to itself b times. The lecture shows this with a for loop and with a countdown while loop. 4:13
The recursive pattern is that 5 times 4 equals 5 plus 5 times 3. You keep pulling out one 5 and making the problem smaller until you reach 5 times 1, which you already know is 5. 8:58
In recursion you have to trust that the smaller problem will be solved correctly, even before you work out its answer. If you break the smaller problem down the same way, it gets solved too. 9:20

Words to know

recursion: A way of solving a problem by breaking it into a smaller problem of the same kind, and solving that smaller one the same way.
iterative algorithm: A method that solves a problem by repeating steps again and again inside a loop.
loop: A part of code that repeats the same steps over and over, such as a for loop or a while loop.
state of the computation: The current values of the variables that keep track of progress, which change each time through a loop.

Example

Imagine you need to count 4 bags with 5 apples in each bag. You could count 5 apples four times, which is like the loop, or you could say 5 apples plus the answer for 3 bags, and then repeat that until you reach 1 bag, which is just 5 apples. This is the same idea as breaking 5 times 4 into 5 plus 5 times 3.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part shows how a function can solve a problem by calling itself on a smaller version of the same problem, and how it builds the answer back up.

Key ideas

Recursion means solving a problem by spotting that it is the same kind of problem as a smaller one. You keep breaking it into smaller pieces until you reach a piece you can solve directly. 10:00
A recursive step is where the function uses the same operation again on a smaller input. For multiplication, a times b is a plus a times (b minus 1). Without a stopping point, though, this would repeat forever. 13:09
A base case is the simple case the function can answer right away. For multiplication, when b is 1, the answer is just a. The base case is what stops the calls from going on forever. 13:31
In the Python code, the function checks for the base case first. If b is 1, it returns a. Otherwise, it returns a plus a call to itself with b minus 1. 15:16
Each function call waits for the call below it to return a value. Once the simplest call returns its answer, each waiting call finishes its own addition and passes the result back up the chain. 19:23

Words to know

recursion: Solving a problem by having a function call itself on a smaller version of the same problem.
base case: The simple case that can be answered directly, which tells the function when to stop calling itself. For multiplication, it is when b is 1.
recursive step: The part of the function where it calls itself on a smaller input, such as b minus 1, moving closer to the base case.
infinite recursion: A function that keeps calling itself and never reaches a stopping point, so it never finishes.

Example

Think of a line of people where each person can only answer a question by asking the person in front of them, until the first person knows the answer. Once that first person answers, each person in line passes the answer back down the line, adding their own piece as they go. The first person is the base case, and the passing back is how the answer is built up.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains recursion, where a function calls itself on a smaller version of the problem until it reaches a simple stopping point, then builds the answer back up.

Key ideas

When a function calls itself, each call waits for the call it made to return a value. Once the answer comes back, each waiting call adds its own piece and passes the total up one level. 20:17
In an iterative approach, one caller keeps going back to each person and keeps track of the running total itself. In a recursive approach, the student asks only one person and waits for the final answer. 22:50
Recursion has two steps. First, the problem keeps getting broken into smaller versions until it reaches a base case. Then the answer is built back up from that point. 23:13
A recursive function calls itself with slightly changed inputs, not the exact same ones. If it used the same inputs, it would never stop, which is called infinite recursion. 27:15
To write a power function recursively, you return 1 when the power is 0, return n when the power is 1, and otherwise return n times the function called again with the power reduced by 1. 28:24

Words to know

recursion: A way of solving a problem where a function calls itself on a smaller version of the same problem.
base case: The simple situation where the function stops calling itself and gives a direct answer, such as when the power is 0.
iteration: Repeating the same steps over and over, usually with a loop, rather than having a function call itself.
infinite recursion: A function that keeps calling itself forever and never reaches a stopping point.

Example

Imagine you ask a line of people to add up a list of numbers. Each person asks the next one to add their part, until the last person answers. Then each person adds their number to the answer they got back and passes the total back along the line.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how a function that calls itself, called recursion, works step by step using factorial as the example.

Key ideas

Factorial of n is n times factorial of n minus 1. The simplest case, base case, is 0! or 1!, which equals 1, and the function stops there. 30:42
Every function call gets its own separate environment, which is a private space that holds its own values. Even when the names are all factorial, each call keeps its own n and does its own job. 34:40
Each call that cannot finish yet waits and calls another copy of itself. The base case is the call that can finish right away, and it gets things started. 36:48
Once a call has its answer, it sends the value back to the call that asked for it, then disappears. The waiting calls finish one by one, from the last one back to the first. 37:09
The chain for factorial of 4 makes 4 calls, and the final answer of 24 is printed. Each call only sends its answer back to the one that called it. 39:22

Words to know

Base case: The simplest case that the function already knows the answer to, so it can stop calling itself.
Recursive step: The part of the function where it calls itself on a smaller version of the problem.
Environment: A private space for one function call that holds its own variables, like its own n value.
Return value: The answer a function sends back to whoever called it.

Example

Imagine a line of people where each person must ask the next person a question, and the last person in line knows the answer right away. That last person passes the answer back, and each person in turn passes it back down the line until the first person has it. Each person keeps their own copy of the question, just like each function call has its own environment.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–45:06

This part explains how recursion works step by step, and when a recursive solution is easier to write than a loop.

Key ideas

When a function calls itself, each new call waits. Once the deepest call has an answer, it hands the value back to whoever called it, and this repeats until the original call gets its result. 40:19
Each function call has its own environment, which is a private set of variables. The calls do not mix their variables together, and each call only needs to know which function it calls next and who it must return its value to. 40:41
You can always write the same job as a loop instead of a recursive function. The loop version uses a loop counter and a state variable to keep track of the running answer. 41:25
Recursion is often harder to grasp at first because a function is written in terms of itself. It is most useful when you do not know ahead of time how many repeats you will need, such as searching folders nested at unknown depths. 42:11
A recursive solution repeats its calls until it reaches a base case, which is the point where the calls stop. The lecture gives nested file folders and nested parentheses in math expressions as examples where this is handy. 43:19

Words to know

recursion: A way of solving a problem where a function calls itself to handle a smaller version of the same problem.
base case: The stopping point in a recursive function, where the function stops calling itself and starts giving answers back.
environment: The private set of variables that belongs to one specific function call, so it does not get mixed up with other calls.
iteration: Repeating a task over and over using a loop, such as a for loop or a while loop, instead of calling a function again.

Example

Think of looking for a file in a set of nested folders. You check the current folder, and if the file is not there, you repeat the same search inside each subfolder, and so on until you find it. You do not need to know in advance how deep the file is buried, which is why this kind of search suits recursion.

3 checked practice questions for this part are in the app.

← Lecture 14: Dictionaries · Lecture 17: Python Classes →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York