Recursion

In the previous two lessons, you learned how to write functions, pass arguments to them and return values from them. So far, your functions have called other functions. But what if a function needs to solve a problem that contains smaller versions of the same problem?

Here is an example of what that means. Imagine a folder on your computer. Inside that folder there are two files: notes.txt, which is 4 kilobytes, and report.pdf, which is 620 kilobytes. But there is also another folder called photos. Inside photos there are two pictures, one of 2,300 kilobytes and one of 1,800 kilobytes. And inside photos there is yet another folder called old, which contains one more picture of 950 kilobytes.

Now the question: what is the total size of the entire folder? Not just the files at the top, but every file inside every subfolder as well.

The folder as a dictionary

You can represent this folder structure with a dictionary. The keys are file or folder names. The values are either file sizes or another dictionary. So a file has a number as its value, and a folder has another dictionary as its value.

folder = {
    "notes.txt": 4,
    "photos": {
        "picture1.jpg": 2300,
        "picture2.jpg": 1800,
        "old": {"picture3.jpg": 950}
    },
    "report.pdf": 620
}

One loop

How would you calculate the total size? Start with a loop. Go through the top-level dictionary and add up every value that is an integer:

size = 0
for name, value in folder.items():
    if type(value) is int:
        size += value
size

624

That gives 624 kilobytes: 4 for notes.txt and 620 for report.pdf. But something is missing. The value for photos is not an integer. It is another dictionary, so this loop does not include any of the files inside it. Only the files at the top level were counted.

Two loops

What if you add another loop? Whenever you find a dictionary, loop through its contents too:

size = 0
for name, value in folder.items():
    if type(value) is int:
        size += value
    else:
        for inner_name, inner_value in value.items():
            if type(inner_value) is int:
                size += inner_value
size

4724

Now the two pictures inside photos are included, and the total becomes 4,724 kilobytes. Better. But the picture inside old is still missing, because it sits one level deeper.

An unknown depth

So what do you do? Add a third loop? And what if old contains another folder? Then you would need a fourth loop, and a fifth, and so on. You can see the problem: you do not know how deeply nested the folders might be, so writing a fixed number of nested loops is not a good solution.

The actual total is 5,674 kilobytes. In this lesson you will write a function that follows the folder structure and includes every file. And here is the interesting part: the function does not need to know the depth in advance. It solves the problem by calling itself. A function that calls itself is using recursionKey termA function calling itself., and such a function is called a recursive function.

This lesson covers how recursive functions work, how Python keeps track of their calls, and when recursion is useful.

Start with the simplest possible example: a countdown. Suppose you want to count down from 3 to 0. You could easily do that with a loop, but this time, write it as a recursive function.

Call it countdown. It takes one parameter, n, and for this example you can assume n is a nonnegative integer. Here is what the function does. If n is zero, it prints Done and returns. Otherwise, it prints n and then calls countdown again, but with n - 1.

def countdown(n):
    if n == 0:
        print("Done")
        return
    print(n)
    countdown(n - 1)

What happened, step by step

When you call countdown(3), Python checks whether n is zero. It is not, so it prints 3. Then it calls countdown again, this time with 2.

That second call checks whether n is zero. Again it is not, so it prints 2 and calls countdown with 1. That call prints 1 and calls countdown with 0.

Now n is zero, so the condition is True. Python prints Done and reaches the return statement, which ends the current call.

Notice something important: that last call does not call countdown again, so the chain of recursive calls stops there. That is the basic idea of recursion.

The base case and the recursive case

Every well-designed recursive function needs a way to stop. In countdown, the stopping condition is:

if n == 0

When that condition is True, the function returns without calling itself again. This is called the base caseKey termThe part of a recursive function that returns without calling the function again: if n <= 1: return 1..

The part where the function calls itself is called the recursive caseKey termThe part of a recursive function that calls the function on a smaller input: return n * factorial(n - 1).. In this example, the recursive case is:

countdown(n - 1)

So a recursive function has two parts. The base case stops the recursion, and the recursive case moves you toward that base case.

Notice that n gets smaller by one on every recursive call. So if you start with a nonnegative integer, you will eventually reach zero, and when you do, the recursion stops.

That matters. If the recursive calls never reach a stopping condition, the function keeps calling itself, and you run into a problem. You will explore that problem shortly. First, use recursion to solve something more interesting.

Imagine a playlist containing five songs. How many different orders could those songs be played in?

Any of the five songs could come first. Once you have chosen the first song, four songs remain, so there are four possibilities for the second position. Then three possibilities for the third, two for the fourth, and one for the last. So the total number of possible orders is five times four times three times two times one:

5 * 4 * 3 * 2 * 1

120

This calculation has a special name. It is called a factorial, and you write five factorial as 5 followed by an exclamation mark: 5!. So 5! is 120.

A smaller version of the same calculation

Look closely at that calculation. 5! is 5 × 4 × 3 × 2 × 1. But 4 × 3 × 2 × 1 is just 4!:

4 * 3 * 2 * 1

24

So you can write 5! = 5 × 4!. Or more generally:

n! = n × (n - 1)!

That is interesting, because factorial is being defined using a smaller version of the same calculation. That makes it a natural fit for recursion.

A factorial function

Write a factorial function. For now, assume n is a nonnegative integer.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Look at the first condition. If n is less than or equal to 1, the function returns 1. That is the base case. Otherwise, it returns n multiplied by factorial(n - 1). That is the recursive case.

Now call it with 5:

factorial(5)

120

You get 120, exactly what you expected. But slow down and look at how Python actually calculates that result. The next section traces factorial(4), because it is shorter to follow.

Call factorial(4). Python checks the base case. 4 is not less than or equal to 1, so it moves to the return statement, which says: return 4 * factorial(3).

But here is the thing. Python cannot finish that multiplication yet, because it does not know the result of factorial(3). So it has to call factorial again.

Now you are inside factorial(3). That call needs 3 * factorial(2), but it does not know factorial(2) yet, so it calls factorial again. Then factorial(2) needs factorial(1), so Python makes another call. And finally, factorial(1) reaches the base case.

Frames on a stack

Each function call has its own frame, sometimes called an execution frame: the record Python keeps of that one call, holding its local variables and where it is up to. Those frames are arranged in what is called the call stackKey termThe frames of every call that has started and not yet returned, the newest on top.. Every new function call adds another frame on top of the stack, and when a function returns, its frame is removed from the stack. The most recent call, on top, is the one currently executing. The earlier calls below it are waiting for it to finish.

The calls return

Now see what happens next. factorial(1) reaches the base case, so it returns 1. That frame finishes, and Python goes back to factorial(2). Now factorial(2) finally has the value it was waiting for, so it calculates 2 × 1 and returns 2.

Then Python goes back to factorial(3), which calculates 3 × 2 and returns 6.

Finally, Python returns to factorial(4), which calculates 4 × 6 and returns 24:

factorial(4)

24

So the calls were made in one direction: 4, 3, 2, 1. But the multiplications were completed as the calls returned: 1, 2, 6, 24.

That is a really important part of understanding recursion. A recursive call can pause the current function while a smaller version of the problem is solved. Then, when that smaller call returns, the original function continues. So recursion is not just about calling a function repeatedly. It is also about how those calls return and complete their unfinished work.

What happens if you get the base case wrong? Go back to factorial, and suppose you change the condition from n <= 1 to n == 1:

def factorial_bad(n):
    if n == 1:
        return 1
    return n * factorial_bad(n - 1)

If you call it with 5, it still works, because the calls eventually reach 1:

factorial_bad(5)

120

RecursionError

Does Python keep doing this forever? No. Python has a recursion limit, and when recursive calls become too deeply nested, Python raises a RecursionError:

factorial_bad(0)

RecursionError: maximum recursion depth exceeded

The full traceback is long, because it lists the repeated calls. Its last line is the message that the maximum recursion depth has been exceeded.

When you see this error, the first thing to check is whether your recursive function is actually moving toward its base case. A missing or unreachable base case is a very common cause of RecursionError.

So here is a useful rule: for every input your function is supposed to support, make sure the recursive calls eventually reach a stopping condition.

You now have everything you need to return to the original problem: the nested folder. You want the total size of every file, including files inside subfolders, and subfolders inside those subfolders. Here is the folder as a dictionary again:

folder = {
    "notes.txt": 4,
    "photos": {
        "picture1.jpg": 2300,
        "picture2.jpg": 1800,
        "old": {"picture3.jpg": 950}
    },
    "report.pdf": 620
}

Telling files from folders

How do you tell whether a value represents a file or a folder? In this example, file sizes are integers and folders are dictionaries. So you can use the built-in function isinstance(), which checks whether a value is of a given type:

isinstance(folder["photos"], dict)

True

It returns True, because photos is a dictionary. Now you can distinguish between files and folders.

The total_size function

Call the function total_size. It takes one parameter, folder. Inside the function, start with a total of zero, then loop through every value in the dictionary. If the value is another dictionary, it is a subfolder, so call total_size again on that subfolder and add the returned size to the total. Otherwise, the value is a file size, so add it directly. After checking everything, return the total.

def total_size(folder):
    total = 0
    for value in folder.values():
        if isinstance(value, dict):
            total += total_size(value)
        else:
            total += value
    return total

Where is the base case?

Notice something interesting. There is no condition that explicitly says "if the folder is empty, stop", or "if we are three levels deep, stop". So where is the base case?

The stopping behavior is built into the structure of the function. If a folder contains only files, the function never makes another recursive call. It simply adds the file sizes and returns the total:

total_size({"picture3.jpg": 950})

950

And if the folder is empty, the loop does not run at all, so it returns zero:

total_size({})

0

Both calls finish without another recursive call. These are cases where the function can finish without recursing. In other words, the function has an implicit base case: one that comes from the shape of the code rather than from an if statement written for the purpose.

Tracing the full example

Now trace the full example, total_size(folder). The function starts with a total of zero. Then it sees notes.txt, a file with a size of 4, so the total becomes 4.

Next, it reaches photos. But photos is a dictionary, so instead of trying to add it as a number, the function calls itself: total_size(photos). Now you are inside a new call, with a new local total starting at zero.

This call sees picture1.jpg and adds 2,300. Then picture2.jpg, and adds 1,800. So the total inside photos is now 4,100.

But then it reaches old, and old is another dictionary, so Python makes another recursive call: total_size(old). Inside old there is just one file, picture3.jpg, with a size of 950 kilobytes. So this call returns 950.

Now you are back inside the photos call. It adds that 950 to its existing total of 4,100, so photos returns 5,050.

Now you are back in the original call. Before entering photos, its total was 4. Adding 5,050 gives 5,054. Then the loop continues and reaches report.pdf. That is another file, with a size of 620, so it is added too, and the final total becomes 5,674 kilobytes:

total_size(folder)

5674

Exactly what you expected.

Another level of nesting

Here is an important question: should you use recursion for everything? Not necessarily. Compare recursion with a regular loop.

Remember the factorial function? You wrote it recursively, but factorial can also be calculated with a loop:

def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

factorial_loop(5)

120

Calling factorial_loop(5) gives 120, exactly the same result. But there is a difference in how Python executes the two versions.

One frame or many

The recursive version makes a new function call for each smaller factorial. So factorial(5) creates a chain of five active factorial calls. The loop version stays inside one function call. It simply updates result on each iteration, so it does not build up a chain of recursive frames on the call stack.

For a straightforward calculation like factorial, the loop is often simpler and more efficient.

Choosing an approach

Here is the bigger lesson. Just because a problem has a recursive definition does not mean a recursive implementation is always the best choice. For a simple sequence or running calculation, a loop may be clearer and more efficient. But for naturally nested structures, like the folder example, recursion can make the code much easier to express.

You started with a folder containing files and subfolders, and saw that a fixed number of nested loops cannot handle an arbitrary depth. Then you learned about recursion, which is when a function calls itself.

With countdown, you learned the two key parts of a recursive function: the base case, where the recursion stops, and the recursive case, where the function calls itself on a smaller problem.

Then you used factorial to understand the call stack. Every recursive call gets its own frame, and those calls remain active until the deeper calls return. The unfinished calculations are then completed as the stack unwinds. You also saw what happens when recursion does not reach its base case: Python raises a RecursionError.

Finally, you returned to the folder problem and wrote a complete recursive function, total_size, that solves it.

Your challenge

Work with the same folder dictionary. It contains five files in total: two at the top level, two inside photos and one inside old.

Write a recursive function called count_files. It should take a folder dictionary as its argument and return the total number of files inside it, including files in every nested subfolder. Count files rather than adding their sizes.

When you call count_files(folder), the result should be 5. When you call count_files(folder["photos"]), the result should be 3.

The next lesson explores how you can pass a function as an argument to another function.