Recursion

Some problems have a smaller copy of themselves inside. The size of a folder is the size of its files plus the sizes of the folders in it, and each of those is a folder too. A word reads the same both ways if its ends match and the part between them reads the same both ways. For problems like these there is a way of writing a function that follows the problem's own shape: the function calls itself. That is recursion. It adds no new Python at all. Everything in this module is a function, an if and a return.

Before this, you can: write a function that returns a value, and trace the calls in progress; keep data in dictionaries and lists, one inside another; slice a string, and test a function with asserts.

By the end you will be able to write a function that calls itself on a smaller input, give it a case that stops, say what each waiting call is holding, write one step and trust the smaller call for the rest, follow data that holds smaller data of the same kind, and tell when a function that calls itself twice is doing far too much work.

Before you read on, decide what this prints:

def count_down(n):
    if n == 0:
        print("go")
        return
    print(n)
    count_down(n - 1)

count_down(3)

3
2
1
go

There is no loop. count_down(3) prints 3 and then calls count_down(2), which prints 2 and calls count_down(1), which prints 1 and calls count_down(0), which prints go and makes no further call. Four calls, each doing one small thing and handing the rest on.

A function that calls itself

Nothing special is needed for a function to call itself. Inside count_down, the name count_down is a function like any other, and calling it starts a new call, with its own n.

What makes it work is that the call inside is given a smaller input: n - 1. Each call is closer to the end than the one that made it. A function that called itself with the same input would be asking the same question for ever.

The case that stops

The other thing that makes it work is the if. When n is 0 the function does its work and does not call itself. That is the case that stops, often called the base case. Every function that calls itself needs one, and every chain of calls must reach it.

Leave it out and the calls never end:

def count_down(n):
    print(n)
    count_down(n - 1)

count_down(3)

  File "your_program.py", line 3
    count_down(n - 1)
RecursionError: maximum recursion depth exceeded

This prints 3, 2, 1, 0, -1, -2 and goes on. Python does not let it go on for ever: once some hundreds of calls are waiting inside one another it stops the program with a RecursionError. When you see that error, look for one of two mistakes. There is no case that stops, or the smaller call is not moving towards it: count_down(n + 1), or a test for n == 0 in a function that is handed 5 and takes away 2 each time.

Calls that wait

When a function calls itself, the first call is not finished. It is waiting, with its own names, for the call it made to return. You saw this in Functions: the boxes of calls in progress, stacked. With recursion the boxes all belong to the same function, each with its own value of n.

def total_to(n):
    if n == 0:
        return 0
    smaller = total_to(n - 1)
    return n + smaller

print(total_to(4))

10

total_to(4) cannot return until it knows total_to(3), which is waiting for total_to(2), and so on down to total_to(0), which answers at once: 0. Then the waiting calls finish in the opposite order. total_to(1) returns 1 + 0. total_to(2) returns 2 + 1. total_to(3) returns 3 + 3. total_to(4) returns 4 + 6.

So there are two halves to every recursion: the way in, as calls pile up, and the way out, as they return. Work written before the call happens on the way in. Work written after it happens on the way out, in the reverse order.

def in_and_out(n):
    if n == 0:
        return
    print("in", n)
    in_and_out(n - 1)
    print("out", n)

in_and_out(3)

in 3
in 2
in 1
out 1
out 2
out 3

Step through this in the lab and watch the boxes: three calls stacked, each with its own n, and each one's second print still to come.

Trust the smaller call

Following every call down and back is how you check a recursion. It is not how you write one. To write one, do this instead.

1. Decide the case that stops, and what its answer is.
2. For any other input, suppose the function already works for a smaller input. Do not look inside that call. Take its answer as given.
3. Write the one step that turns the smaller answer into the answer you want.

Here is the reverse of a string. An empty string is its own reverse: that is the case that stops. For anything longer, suppose reverse already works on a shorter string. Then the reverse of text is its last character, followed by the reverse of everything before it.

def reverse(text):
    if text == "":
        return ""
    return text[-1] + reverse(text[:-1])

print(reverse("stop"))

pots

The function has two lines of thought in it, and neither one traces anything. If the smaller call is right and the one step is right, the whole function is right, because every chain of calls ends at the case that stops, which is right by inspection. Your job is those two things and one more: making sure the input really does get smaller.

Data inside data

Recursion is at its best when the data itself has the same shape inside it. A folder on a computer holds files, and it holds folders, each of which holds files and folders. Here a folder is a dictionary with two keys: "files", a list of file sizes, and "folders", a list of folders.

photos = {"files": [40, 25], "folders": []}
essays = {"files": [3], "folders": []}
school = {"files": [1, 2], "folders": [essays]}
home = {"files": [10], "folders": [photos, school]}

def count_files(folder):
    count = len(folder["files"])
    for inner in folder["folders"]:
        count = count + count_files(inner)
    return count

print(count_files(home))

6

Read count_files with trust. A folder's files are its own, plus the files of each folder in it, and count_files(inner) is supposed to give exactly that for a smaller folder. Nothing in the function says how deep the folders go, and it does not need to.

Where is the case that stops? It has no if. A folder with no folders in it has an empty list, so the loop runs no times and no call is made. The data runs out, and that stops it.

A plain loop cannot do this easily, because a loop goes along one list, and this data branches. The function that calls itself follows each branch to its end and comes back, and the waiting calls remember where it was.

When one call makes two

Each function so far made one smaller call for each piece of data, so the number of calls was in step with the size of the input. That changes when a function calls itself twice on overlapping inputs.

You can climb stairs one step or two steps at a time. In how many ways can you climb n stairs? The last move was either one step, from stair n - 1, or two, from stair n - 2. So the number of ways is the ways to reach n - 1 plus the ways to reach n - 2.

calls = {"count": 0}

def ways(n):
    calls["count"] = calls["count"] + 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(5), calls["count"])
calls["count"] = 0
print(ways(20), calls["count"])

8 15
10946 21891

Five stairs took 15 calls. Twenty took 21,891, and thirty would take more than two and a half million. The function is correct, and it is doing the same work over and over: ways(5) asks for ways(3) twice, for ways(2) three times, and for ways(1) five times. Each extra stair multiplies the calls by about 1.6.

When a function calls itself more than once, ask whether the smaller inputs overlap. In the folders they do not: each folder is inside exactly one other, so each is visited once. On the stairs they do, and the cost explodes. There is a cure, which is to remember each answer the first time it is worked out. That is a module of its own.

In the lab

You will follow a countdown, see what happens with no case that stops, and watch calls wait and return. You will write a power function and a test for a word that reads the same both ways, find the size of a folder of folders, draw squares inside squares, and count the calls of a function that calls itself twice. Four assignments follow: how deep a folder goes, a sum of digits with two mistakes, every file in order, and a number written in binary.