Recursion trees

When a function makes more than one recursive call, the calls form a tree. Drawing the tree shows how many calls there are, and often shows that the same small problem is being solved again and again.

Drawing the calls

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, …: each one is the sum of the two before it. Written straight from that rule:

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

Each call with n of 2 or more makes two calls. Draw each call as a box, with the calls it makes below it. That picture is the recursion tree. Python visits it from left to right, going all the way down each branch first.

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

Counting the calls

Let C(n) be the number of calls fib(n) makes. Then C(n) = 1 + C(n − 1) + C(n − 2), which grows at least as fast as the Fibonacci numbers themselves. Those grow by a factor of about 1.618 each step. So fib(n) takes about 1.6ⁿ calls (n copies of 1.6 multiplied together): exponential. fib(30) makes about 2.7 million calls, and fib(50) would take hours.

The tree also shows why: fib(3) is worked out twice inside fib(5), and fib(2) three times. The number of different problems is only n + 1: fib(0) to fib(n). All the rest is repeated work.

Remember answers: memoisation

Memoisation means storing each answer the first time it is worked out, and looking it up after that. Step through the second version of the figure.

memo = {}
def fib(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

Now each of the n + 1 problems is solved once. Every other call is a dictionary lookup. That is O(n) calls instead of about 1.6ⁿ. Python can add the memo for you:

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Common tree shapes

• A chain (one call, shrinking by 1): n calls. A recursive sum.
• A halving chain (one call on half): log n calls. Fast power, binary search.
• A balanced binary tree (two calls on halves): about 2n calls in all, in log n levels. Merge sort.
• A full binary tree of depth n (two calls shrinking by 1): 2ⁿ calls, n twos multiplied together. Subsets, in lesson 4.

BIGO-5 turns these trees into exact costs. Now try RECR-P2, Steps on the footbridge.