Recursion trees in Python

Why this matters

The first lesson in this module showed a function that calls itself and stops at a base case. Some recursive functions call themselves only once on each step. Others call themselves two or three times. The second kind can make far more calls than you expect. A function that calls itself twice on each step makes about 2.7 million calls for an input of only 30.

Before you decide whether a recursive function is fast enough, you need a way to count its calls. The picture you use for that is a recursion tree. This lesson teaches you to draw one, count it, and read the cost from it. The next lesson, Memoised recursion, uses the same tree to find work that is done again and again.

The idea from the first principle

A call is one run of a function from its first line to its return. When your program starts fib(4), that is one call. If that call starts fib(3), that is a second call, and it is inside the first one.

A call tree is a drawing of those calls. Each call is a box. If a call starts another call, you draw a line from the first box down to the second box. The box at the top is the first call, and it is called the root. A box with no lines going down is a leaf. The number of lines you pass through to get from the root to a box is that box's depth.

Start with the simplest shape. Here is a function that counts down:

def countdown(n: int) -> None:
    print(n)
    if n == 0:
        return
    countdown(n - 1)

Call countdown(3). It prints 3, then calls countdown(2), which prints 2, and so on down to 0. The tree is a straight line of four boxes. Every call starts exactly one other call, so there is no branching. A straight line tree is the easiest kind to count, because the number of calls equals the number of values printed.

Branching is what makes trees interesting. A function branches when one call starts two or more calls. The classic example in this course is the Fibonacci sequence. It is a list of numbers where each number is the sum of the two before it. The list starts 0, 1, 1, 2, 3, 5, 8, 13, and so on. You write the Fibonacci number at position n as fib(n). Its definition gives you a function directly:

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

The base case is n <= 1. For fib(0) the answer is 0, and for fib(1) the answer is 1, so the function returns n itself. For any larger n, the function asks for the two smaller Fibonacci numbers and adds them. Programmers call this the naive version, which means the simplest one that follows the definition. It is correct. It is also slow, and the rest of this lesson shows why.

Worked example: drawing fib(4) by hand

Start with fib(4) and write down every call it makes, in the order they start. The root is fib(4). Because 4 is not a base case, it starts fib(3) and fib(2). Then fib(3) starts fib(2) and fib(1). Then the first fib(2) starts fib(1) and fib(0). The second fib(2) starts fib(1) and fib(0) as well.

Here is the finished tree. Read it from the top. Each line is one call, and the indentation shows which call started it:

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1)
│   │   └── fib(0)
│   └── fib(1)
└── fib(2)
    ├── fib(1)
    └── fib(0)

Count the boxes. There are 9 calls. There are 4 boxes that start other calls, and 5 leaves. Each leaf is a call that hits the base case and returns right away. The leaves are fib(1), fib(0), fib(1), fib(1), and fib(0).

Now a program that prints the same tree. It passes a depth number down with each call, and each call prints itself indented by its depth. Two spaces are added per level with " " * depth, which repeats the text two spaces, depth times:

Press Run. You should see:

fib(4)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)
  fib(2)
    fib(1)
    fib(0)
result = 3

The printed lines match the drawing. The program prints the calls in the order they start. The function takes a second argument here only so that the indentation can show the depth. The Fibonacci logic is the same as before.

The result is 3. You can check this from the tree. The leaves hold the values 1, 0, 1, 1, and 0, and their sum is 3. Each box that is not a leaf returns the sum of its two children, so the final answer is always the sum of the leaf values. You do not need this fact to count calls, but it is a useful way to check your own work when a tree gets large.

The drawing also shows the waste. The call fib(2) appears twice. The call fib(1) appears three times. Each of those repeats does exactly the same work again. The next lesson uses this observation to avoid the repeats.

Counting the calls with a counter

Drawing a tree is clear for fib(4), but it is slow for fib(30). A better method is to count the calls with a counter. A counter is a variable that goes up by one each time something happens. Here you add one to a variable at the start of every call. The variable lives outside the function, so the function must say global calls before it changes it. Without that line, Python would create a new local variable with the same name, and the outer counter would never move.

The line calls = 0 before each call resets the counter. Without it, the numbers would add up across the loop. Press Run. You should see:

fib(0) = 0, calls = 1
fib(1) = 1, calls = 1
fib(2) = 1, calls = 3
fib(3) = 2, calls = 5
fib(4) = 3, calls = 9
fib(5) = 5, calls = 15
fib(6) = 8, calls = 25
fib(7) = 13, calls = 41
fib(8) = 21, calls = 67
fib(9) = 34, calls = 109
fib(10) = 55, calls = 177
fib(30) = 832040, calls = 2692537

The count for fib(4) is 9, which matches the tree you drew by hand. Look at the pattern of the counts. Each number is about 1.6 times the one before it. For fib(30) the program makes 2692537 calls, which is about 2.7 million, to compute one number. Run time depends on your machine, but the call count does not change.

There is a formula behind these counts, and it helps when you want an answer without running the program. For fib(n) the number of calls is 2 * fib(n + 1) - 1. You can check it with the table. For n = 4, fib(5) is 5, so the count is 2 * 5 - 1, which is 9. For n = 10, fib(11) is 89, so the count is 2 * 89 - 1, which is 177. Both match the output.

The reason is simple once you see the tree. Every call that is not a leaf starts exactly two calls, so the tree is "full" in the sense that each branch splits in two. The leaves all return 0 or 1, and the number of leaves is fib(n + 1). In a full tree with two children per branch, the total number of boxes is always twice the number of leaves, minus one. You can see this on the drawing of fib(4): it has 5 leaves and 4 branch boxes, which is one fewer than the leaves.

The formula also shows how fast the cost grows. Compare fib(30) with fib(40). Ten more steps in n multiply the number of calls by about 123. The count for fib(40) is 2 * fib(41) - 1, which is 2 * 165580141 - 1, or 331160281 calls. That is about 331 million calls for one answer. Every call takes some time, so the count is the reason this method slows down.

Second example: climbing stairs

The first example asked you to compute a number from a rule. This second example comes from a real question. A staircase has n steps. You can climb one step or two steps at a time. How many different ways are there to reach the top?

Think about the last move. If you finished with a one-step move, you were on step n - 1 just before it. If you finished with a two-step move, you were on step n - 2 just before it. So the number of ways to reach step n is the number of ways to reach n - 1 plus the number of ways to reach n - 2.

For the base cases, there is exactly one way to reach step 0, which is to do nothing. There is also exactly one way to reach step 1, which is one single step. Here is the function and its counter:

Press Run. You should see:

ways(0) = 1, calls = 1
ways(1) = 1, calls = 1
ways(2) = 2, calls = 3
ways(3) = 3, calls = 5
ways(4) = 5, calls = 9
ways(5) = 8, calls = 15

Look at the call counts. They are 1, 1, 3, 5, 9, 15. The counts for fib(n) in the first example were 1, 1, 3, 5, 9, 15 as well, for the same n. The two functions make the same tree of calls. Only the values at the leaves differ. fib returns 0 for n = 0, but ways returns 1, so the sums at the top come out differently. This is a useful point. The shape of the tree decides how many calls you make. The leaf values decide the answer.

You can draw ways(4) to see the same shape:

ways(4)
├── ways(3)
│   ├── ways(2)
│   │   ├── ways(1)
│   │   └── ways(0)
│   └── ways(1)
└── ways(2)
    ├── ways(1)
    └── ways(0)

The leaves are five boxes that each return 1. Their sum is 5, which matches the answer for four steps.

Python has a shortcut for the counter. The functools module, which is part of the standard library, has a decorator called cache. You met it in the second lesson. It stores answers, so the function does not repeat work. For this lesson the plain counter is better, because the point is to see the repeated calls, not to hide them.

Third example: three branches at each call

The third example widens the tree. Suppose each move can climb one, two, or three steps. Now each call starts three calls instead of two. A call with n makes calls for n - 1, n - 2, and n - 3. Negative numbers are possible in this version, because n - 2 or n - 3 can be below zero when n is 1 or 2. The function needs a rule for that case. A position below zero is not a real way to finish, so the function returns 0 for it:

Press Run. You should see:

ways3(3) = 4, calls = 13
ways3(6) = 24, calls = 85
ways3(9) = 149, calls = 532
ways3(12) = 927, calls = 3313
ways3(15) = 5768, calls = 20617

The count for n = 3 is 13 calls, and it is worth checking by hand. Here is the tree for ways3(3):

ways3(3)
├── ways3(2)
│   ├── ways3(1)
│   │   ├── ways3(0)
│   │   ├── ways3(-1)
│   │   └── ways3(-2)
│   ├── ways3(0)
│   └── ways3(-1)
├── ways3(1)
│   ├── ways3(0)
│   ├── ways3(-1)
│   └── ways3(-2)
└── ways3(0)

Count the boxes. The top has 1 box. The subtree under ways3(2) has 7 boxes. The subtree under ways3(1) has 4 boxes. The last box under the root is ways3(0). The total is 1 + 7 + 4 + 1, which is 13.

The negative calls are easy to forget when you count by hand. They are real calls, and they cost time. The counter includes them, which is why the number is 13 and not 9.

Compare the growth with the Fibonacci tree. From n = 6 to n = 12 the call count goes from 85 to 3313. The tree is wider, so each extra step multiplies the work by more than it did for two branches. The function is still correct, but the cost grows very quickly.

Common mistakes

Beginners make the same few mistakes when they first draw recursion trees. Each mistake below shows what the message or the output looks like, so you can spot it quickly.

Mistake 1: no base case

If a function has no base case, the calls never stop. Each call starts another call, and Python runs out of the room it allows for waiting calls. Here is a version of fib with the base case removed:

def fib(n: int) -> int:
    return fib(n - 1) + fib(n - 2)
 
 
print(fib(5))

Running this program prints an error that starts like this. The real output is much longer, because it repeats the same lines about a thousand times, and the exact count depends on your Python version:

Traceback (most recent call last):
  File "no_base.py", line 5, in <module>
    print(fib(5))
          ~~~^^^
  File "no_base.py", line 2, in fib
    return fib(n - 1) + fib(n - 2)
           ~~~^^^^^^^
  File "no_base.py", line 2, in fib
    return fib(n - 1) + fib(n - 2)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

A RecursionError means the chain of waiting calls went past Python's limit, which is 1000 by default. Each new call adds a frame to the call stack, which is the list of calls that are still running, and a frame is removed when its call returns. With no base case, the list only grows. The last line names the problem. The repeated lines point at the function and its line number, which is line 2 here.

Mistake 2: a base case the input never reaches

A base case has to be reachable from every input. Suppose you write a countdown that stops at zero, but you call it with a negative number. The call goes from -1 to -2 to -3 and never reaches zero. The result is the same RecursionError as in mistake 1. Here is the countdown from earlier, called with -1, with its output cut short:

def count_down(n: int) -> None:
    print(n)
    if n == 0:
        return
    count_down(n - 1)
 
 
count_down(-1)

The output starts with -1, -2, -3, and it keeps going until the limit stops it. The fix is to check for the case you expect, or to handle negative input directly. The ways3 example above does this by returning 0 for any negative n. Changing the test to if n <= 0: also works for this countdown, because it stops at any value at or below zero.

Mistake 3: mixing up the answer and the call count

The answer of fib(4) is 3. The number of calls is 9. The two numbers measure different things. The answer is what the function returns. The count is how much work it does. Students often print one and expect the other. If your program prints calls where it should print the answer, the output will look like a valid number but it will be wrong.

Mistake 4: forgetting to reset the counter

The counter in the examples is a global variable. It keeps its value until something changes it. If you call the function in a loop without calls = 0 before each call, the count for the second call includes the first call. The second line of the output will then be too large. This is a silent error. The program does not crash, and the answer looks reasonable, so you need to read the numbers carefully.

Mistake 5: counting only the leaves

When you draw the tree, the leaves are easy to see, and the boxes that start calls are easy to forget. Count every box, including the root and every box that has children. The root is the first call, and it counts. In the fib(4) drawing there are 9 boxes in total, and 5 of them are leaves. Counting only the leaves gives 5, which is the number of values added up, and not the number of calls.

Practice

Exercise 1

Without running the program, work out how many calls fib(12) makes. Use the formula 2 * fib(n + 1) - 1, and recall that fib(13) is 233.

Show the answer

The count is 2 * 233 - 1, which is 465. The formula says that fib(12) makes 465 calls. You can check the formula with the table from earlier: fib(10) makes 177 calls, and fib(11) is 89, so 2 * 89 - 1 is 177 as well.

Exercise 2

The stairs function ways makes 15 calls for n = 5. Use the pattern of the counts to predict the number of calls for n = 6. The count for n is one more than the count for n - 1 plus the count for n - 2.

Show the answer

The count for n = 6 is the count for n = 5 plus the count for n = 4, plus one for the root. That is 15 + 9 + 1, which is 25. You can run ways(6) with the counter from the second example to check it.

Exercise 3

Draw the call tree for sum_digits(4721) and count its calls. The function below adds the digits of a number. It adds the last digit n % 10 to the sum of the other digits, which it gets from n // 10:

def sum_digits(n: int) -> int:
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

Show the answer

Each call starts only one other call, so the tree is a straight line. The calls are sum_digits(4721), sum_digits(472), sum_digits(47), and sum_digits(4). That is 4 calls. The last call hits the base case, because 4 is less than 10. The answer is 4 + 7 + 2 + 1, which is 14. The number of calls equals the number of digits, which is 4. The // operator is floor division, which drops the remainder, so 4721 // 10 is 472.

Exercise 4

The function below is meant to count down from n to 0. Explain what happens when you call count_down(-1), and describe one change that fixes it.

def count_down(n: int) -> None:
    print(n)
    if n == 0:
        return
    count_down(n - 1)

Show the answer

With n = -1, the base case n == 0 is never true. The calls go to -2, -3, and so on, and the function never returns. The program prints a long run of negative numbers, then stops with RecursionError. One fix is to change the test to if n <= 0:, which stops for any value at or below zero. Another fix is to check the input before the recursion starts and raise an error when n is negative.

Exercise 5

Using the output of the ways3 program, compare the number of calls for n = 6 and n = 12. Say in one sentence what the comparison shows about how the cost grows.

Show the answer

For n = 6 the count is 85 calls, and for n = 12 it is 3313 calls. Doubling n from 6 to 12 multiplies the calls by about 39. The cost grows much faster than the input, because each call makes three calls and the tree gets wider at every level.

Summary

• A recursion tree shows each call as a box, with lines from a call down to the calls it starts.
• The number of boxes in the tree is the number of calls, and counting it with a global counter checks your drawing.
• Naive fib(n) makes 2 * fib(n + 1) - 1 calls, so fib(30) makes about 2.7 million calls.
• Two functions can have the same tree shape and still return different answers, because the leaf values differ.
• A missing base case, or a base case the input never reaches, causes a RecursionError.
• The repeated boxes in the tree, such as fib(2) appearing twice in fib(4), are the work that the next lesson removes.