Recursion trees

Why this matters

When a recursive function is slow, the first question is how many times it calls itself. The code does not show the answer directly. The answer sits in the shape of the calls, and a call tree shows that shape. If you can draw the tree for a small input, you can count the calls for a large one. The drawing also shows which work the function repeats. The next lesson uses that observation to stop the repeats.

This lesson assumes you can trace one recursive call by hand, as taught in the base case and call stack lesson before it.

Every call is one box

Each call of a function creates a frame on the call stack. For this lesson, draw each call as one box. A box is called a node. When a call makes another call, draw the new call as a box below it, joined by a line. The boxes a call makes directly are its children. A box with no children is a leaf. The first call, at the top, is the root.

The depth of a box is the number of lines you cross to reach it from the root. The root has depth 0. Its children have depth 1, their children have depth 2, and so on. The depth of the deepest box tells you how far the recursion goes down, and that is what fills the call stack at its peak.

The shape of the tree decides the count, so start with two small shapes.

The first function calls itself once per call. It counts down from n to 0.

Its tree is a straight line. countdown(3) has one child, countdown(2). That call has one child, countdown(1), and so on down to countdown(0), which is the leaf. The tree has four boxes, one under the other. The output is 3, 2, 1, 0.

The second function calls itself twice per call. This is the shape that makes recursion expensive.

The depth parameter only controls the indentation, so the tree is visible in the output. The variable calls counts every call, including the leaves. The output is:

visit(2)
    visit(1)
        visit(0)
        visit(0)
    visit(1)
        visit(0)
        visit(0)
calls = 7
visit(3)
    visit(2)
        visit(1)
            visit(0)
            visit(0)
        visit(1)
            visit(0)
            visit(0)
    visit(2)
        visit(1)
            visit(0)
            visit(0)
        visit(1)
            visit(0)
            visit(0)
calls = 15

Look at the level counts for visit(2). One box at depth 0, two at depth 1, and four at depth 2. That is 1 + 2 + 4 = 7 calls. For visit(3) the levels hold 1, 2, 4 and 8 boxes, which add to 15. Each extra level doubles the number of boxes on the new bottom row. So a function that calls itself twice on every level makes about 2 to the power of (n + 1), minus 1, calls. For n = 2 that is 7, and for n = 3 it is 15.

Worked example 1: naive Fibonacci

The Fibonacci numbers start with 0 and 1. Each later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, and so on. We write fib(0) for the first number, fib(1) for the second, and so on. The definition has three rules.

• fib(0) is 0.
• fib(1) is 1.
• fib(n) is fib(n - 1) + fib(n - 2), for any n of 2 or more.

The word naive here means we copy the rules straight into code, with no extra tricks. Naive Fibonacci is the classic example of a recursion tree that grows much faster than the answer it gives. The program below prints the tree for fib(4). The depth parameter only controls indentation, as in the last example.

The output is:

fib(4)
    fib(3)
        fib(2)
            fib(1)
            fib(0)
        fib(1)
    fib(2)
        fib(1)
        fib(0)
fib(4) = 3, calls = 9

You can draw this tree by hand before you run anything. Follow the rules.

1. Write fib(4) at the top. It is not a base case, because 4 is not below 2. So it has two children, fib(3) and fib(2).
2. fib(3) is not a base case either. Its children are fib(2) and fib(1).
3. fib(2) is not a base case. Its children are fib(1) and fib(0).
4. fib(1) and fib(0) are base cases. They have no children, so they are leaves.
5. Repeat step 2 to 4 for the right-hand side of the tree.

When you finish, the drawing has nine boxes. The program's output shows the same nine lines in the same order. The left side of each split is the call with n - 1, and the right side is the call with n - 2.

Counting the calls in the tree

The program's counter says 9. You can check that by counting the boxes for each value. The table below lists each value and how many boxes show it.

The counts add to 1 + 1 + 2 + 3 + 2 = 9. Two things stand out. The tree computes fib(2) twice and fib(1) three times, even though each of those answers never changes. The leaves are the boxes with no children, and there are five of them, the three fib(1) and the two fib(0). The other four boxes, fib(4), fib(3), and the two fib(2), each make two calls.

You do not need to draw a tree to count it. Write down a rule instead. Let calls(n) be the number of calls made by fib(n), counting the call itself and every call below it. A call counts itself as 1, and then adds the counts of its children.

• calls(0) = 1, because fib(0) is a leaf.
• calls(1) = 1, because fib(1) is a leaf.
• calls(n) = 1 + calls(n - 1) + calls(n - 2), for n of 2 or more.

Check the rule against the tree. calls(2) = 1 + 1 + 1 = 3. calls(3) = 1 + 3 + 1 = 5. calls(4) = 1 + 5 + 3 = 9. The rule matches the drawing and the program.

How fast the count grows

Run the same counting for bigger inputs. The table uses the counter from the program with the same rules, and the fib(n) column shows the answer for each input.

The answer for fib(35) is about 9 million, but the naive function makes about 30 million calls to get it. The count grows by about 1.6 times each time n goes up by one. There is also an exact formula that fits every row of the table. The number of calls for fib(n) is 2 * fib(n + 1) - 1. For n = 35 that is 2 * 14930352 - 1 = 29860703, which matches the table.

The tree also shows how deep the recursion goes. Follow the leftmost path from fib(4): fib(4), fib(3), fib(2), fib(1). That path has three lines between the root and the leaf, which is n - 1. The longest path for any fib(n) is n - 1 lines, so the call stack reaches about n frames at its peak. The total number of calls grows much faster than the depth. For fib(35) there are about 30 million calls, but the deepest point is only 34 lines below the root.

Worked example 2: a tree with three branches

Now a problem with a different shape. You stand at the bottom of a staircase. On each move you climb 1, 2 or 3 steps. How many different sequences of moves reach the top? Call that number ways(n), where n is the number of steps left.

• ways(0) is 1. You are already at the top, and the one way is to take no more steps.
• ways(n) for a negative n is 0. You jumped past the top, which is a dead end.
• Otherwise, the first move can be 1, 2 or 3 steps. So ways(n) is ways(n - 1) + ways(n - 2) + ways(n - 3).

Check the rule for 3 steps. The sequences are 1 then 1 then 1, 1 then 2, 2 then 1, and a single 3. That is four ways, and the rule gives ways(3) = 4. The program below prints the tree for 3 steps, then counts the calls for bigger staircases. Its show flag turns the printing off for the big runs, so the output stays short.

The output is:

ways(3)
    ways(2)
        ways(1)
            ways(0)
            ways(-1)
            ways(-2)
        ways(0)
        ways(-1)
    ways(1)
        ways(0)
        ways(-1)
        ways(-2)
    ways(0)
ways(3) = 4, calls = 13
ways(4) = 7, calls = 25
ways(6) = 24, calls = 85
ways(8) = 81, calls = 289
ways(10) = 274, calls = 979
ways(20) = 121415, calls = 433993

This tree has a different shape from the Fibonacci tree. Each box has up to three children instead of two. Some boxes are dead ends, such as ways(-1) and ways(-2). A dead end is a call that returns 0 at once, with no children. The leaf ways(0) appears four times. The calls ways(1), ways(2) and ways(3) each make one, and ways(1) shows up twice in the tree.

The count uses the same method as before. Let calls(n) count the call and everything below it. A negative n or n equal to 0 is a leaf, so calls is 1 there. For n of 1 or more, calls(n) = 1 + calls(n - 1) + calls(n - 2) + calls(n - 3). Then calls(1) = 1 + 1 + 1 + 1 = 4, and calls(2) = 1 + 4 + 1 + 1 = 7. Also calls(3) = 1 + 7 + 4 + 1 = 13, which matches the program.

The counts grow by about 1.8 times for each extra step. The count for 20 steps is 433993, and the number of ways is 121415. The number of ways and the number of calls are different things. The ways number is the answer. The calls number is the cost of the naive method.

Worked example 3: a balanced tree

The last example is harder because the tree is not lopsided. The function below splits a range of size n into two halves, and stops when the size is 1. It does not return an answer, so the work is only the calls themselves.

The output is:

split(8)
    split(4)
        split(2)
            split(1)
            split(1)
        split(2)
            split(1)
            split(1)
    split(4)
        split(2)
            split(1)
            split(1)
        split(2)
            split(1)
            split(1)
calls for 8 = 15
n = 1  calls = 1
n = 2  calls = 3
n = 4  calls = 7
n = 8  calls = 15
n = 16  calls = 31
n = 1024  calls = 2047

Look at the counts. For each power of two, the number of calls is 2 * n - 1. For 8 that is 15, and for 1024 it is 2047.

The reason is in the leaves and the inner boxes. The leaves are the calls with n equal to 1, and there are exactly n of them, because the range is cut in half until each piece has size 1. The inner boxes are the calls with n above 1, and each one has exactly two children. Every time you split the tree into two branches, the number of leaves is one more than the number of inner boxes. So the inner boxes number n - 1, and the total is n + (n - 1) = 2 * n - 1. For n = 8 the tree has 8 leaves and 7 inner boxes, which gives 15 calls.

This tree is wide and shallow. The Fibonacci tree for fib(35) had about 30 million calls and a depth of 34. The split tree for 1024 has about 2000 calls and a depth of only 10. Halving a range repeatedly needs only about log base 2 of n levels. The same shape appears in merge sort, which the divide and conquer module covers later.

Counting without drawing

You can count the calls of most recursive functions in three steps.

1. Find the base cases. Each leaf counts as 1 call.
2. Write the count for the input as 1 plus the counts of its children. The function body shows how many children each call makes and what their inputs are.
3. Solve the rule from the smallest input upward, the same way the tables above were built. Stop when you have the count you need.

For naive Fibonacci the rule is calls(n) = 1 + calls(n - 1) + calls(n - 2). For the staircase it has three terms. For the split it is calls(n) = 1 + 2 * calls(n / 2), with calls(1) = 1. Check the split rule for n = 8. calls(8) = 1 + 2 * calls(4) = 1 + 2 * 7 = 15, and calls(4) = 1 + 2 * calls(2) = 1 + 2 * 3 = 7.

The count is only half the cost. Each call also does work, such as printing, copying a vector or looking up a map. The total work is the number of calls times the work per call. If the work per call is the same everywhere, the count tells you the cost. If it differs, add up the work for each box.

Common mistakes

Counting only the boxes that make calls

A common error is to count the boxes that have children and forget the leaves. For fib(4) there are four boxes that make calls: fib(4), fib(3), and the two fib(2). If you stop there, you get 4. The real count is 9, because the five leaves are also calls. Each leaf is a call that runs the first if, returns, and still costs a stack frame.

Forgetting the base case

If the base case is missing or wrong, the tree never has leaves, and the recursion goes on for ever. Here is a function with the base case in the wrong place.

The compiler gives a warning when it can see the problem. With -Wall it prints:

infinite.cpp: In function ‘long long int broken(long long int)’:
infinite.cpp:3:11: warning: infinite recursion detected [-Winfinite-recursion]
    3 | long long broken(long long n) {
      |           ^~~~~~
infinite.cpp:4:18: note: recursive call
    4 |     return broken(n + 1) + 1;
      |            ~~~~~~^~~~~~~

The warning is a clue, not proof. The compiler does not always see the problem. When you run this program, the calls never stop, the call stack grows until the system limit, and the operating system stops the program. The exit code is 139. That number is 128 plus 11, and 11 is the signal for a segmentation fault, which is the error for using memory the program does not own. In practice, a tree that never ends shows up as a crash, not as a message from your code.

The fix is the same as in the base case lesson. Every call must move the input toward a base case. Here the input grows, so it moves away from 0.

Thinking depth and call count are the same

Depth and count measure different things. Depth is how many frames sit on the stack at the same time. Count is the total number of calls over the whole run. For fib(35) the depth is 34, but the count is about 30 million. A tree can have a small depth and a huge count, as the Fibonacci tree does, or a moderate depth and a small count, as the split tree does. When you worry about the call stack, check the depth. When you worry about speed, check the count.

Practice

Exercise 1. Draw the call tree for visit(2) from the second example, without running the code. Count how many boxes are at each depth, and give the total.

Show the answer

There is one box at depth 0, two at depth 1, and four at depth 2. The total is 1 + 2 + 4 = 7. The program prints calls = 7.

Exercise 2. The naive Fibonacci function is called on n = 6 and n = 7. Use the formula 2 * fib(n + 1) - 1 to predict the number of calls for each. Check your answers by counting with the calls rule.

Show the answer

For n = 6 the answer is 2 * fib(7) - 1 = 2 * 13 - 1 = 25. For n = 7 the answer is 2 * fib(8) - 1 = 2 * 21 - 1 = 41. A program that prints these counts gives n = 6 fib = 8 calls = 25 and n = 7 fib = 13 calls = 41.

Exercise 3. Use the staircase rule to count the calls for ways(2). Draw the tree first, then check it with the rule calls(n) = 1 + calls(n - 1) + calls(n - 2) + calls(n - 3), with calls(0) = 1 and calls of any negative number equal to 1.

Show the answer

The tree has seven boxes: ways(2), ways(1), ways(0), ways(-1), and ways(-2) under ways(1), then ways(0) and ways(-1) under ways(2). The rule gives calls(1) = 1 + 1 + 1 + 1 = 4 and calls(2) = 1 + 4 + 1 + 1 = 7. The program prints ways(2) = 2, calls = 7.

Exercise 4. Use the split function from the third example to predict the number of calls for n = 32. Then say how many levels the tree has, counting the root as level 1.

Show the answer

Each power of two gives 2 * n - 1 calls, so n = 32 makes 2 * 32 - 1 = 63 calls. The program prints calls for 32 = 63. The root splits in half five times to reach size 1, so the tree has 5 + 1 = 6 levels when the root counts as level 1.

Exercise 5. The function below is meant to count the calls from n down to 0, but it is wrong. Find the mistake and say what happens when you call countup(3).

int countup(int n) {
    if (n == 0) {
        return 0;
    }
    return countup(n + 1) + 1;
}

Show the answer

The recursive call uses n + 1, so the input moves away from the base case at 0. Every call makes another call, and the chain never reaches 0. The fix is to make the input shrink, so the call should be countup(n - 1). With the input from countup(3), the chain would be 3, 4, 5, and so on, until the call stack runs out of space.

Summary

• A call tree draws each call as a node, with the calls it makes as children. A node with no children is a leaf.
• The number of calls equals the number of nodes, leaves included. Leaves are easy to forget.
• For naive Fibonacci, the number of calls is 2 * fib(n + 1) - 1, so the count grows by about 1.6 times for each step up in n.
• A tree that splits in half at each call has about 2 * n - 1 calls, and its depth grows only with the number of halvings.
• Depth controls the call stack, and count controls the running time. Check both.