Recursion trees

Recursion trees

factorial makes one self-call, so its picture is a straight line of frames. The interesting and dangerous shape appears when a function calls itself twice, as with the Fibonacci numbers.

• fib(0) = 0 and fib(1) = 1 are the base cases.
• fib(n) = fib(n−1) + fib(n−2) is the recursive case.

Drawing every call gives a recursion tree. fib(5) calls fib(4) and fib(3), fib(4) calls fib(3) and fib(2), and so on down to the base cases.

Notice that fib(3) already appears twice, and each copy recomputes its entire subtree from scratch, knowing nothing about the other.

The tree roughly doubles in size per level, so naive fib is about O(2ⁿ) calls. The depth is only n, so the memory stays small, and it is the width that ruins it.

Sketching the recursion tree is how you see an exponential blow-up before running anything, which is a habit worth building now.

Counting the calls

The counter tallies every invocation.

calls = 0

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

print(fib(10), calls)
calls = 0
print(fib(20), calls)

Output

55 177
6765 21891

Computing fib(10) took 177 calls to produce a single number, which is already about 3 calls per unit of the answer.

Going from n = 10 to n = 20 made the answer 123 times bigger, and it made the call count 123 times bigger too, from 177 to 21,891. The work tracks the value of the answer rather than the size of the input.

That is the signature of exponential growth. Ten more steps of n multiply the cost by more than a hundred, so fib(40) is around 300 million calls and fib(60) is beyond reach.

calls is reset between the two runs, since the counter is a module-level variable and would otherwise carry the first total into the second.

The global calls line is only there for the measurement. It is not part of the algorithm, and needing it is a hint that this kind of instrumentation belongs outside the function in real code.

Because Python caches nothing between separate calls, and different branches of the tree independently reach the same argument.

fib(4)'s left branch reaches fib(2) through fib(3), and its right branch calls fib(2) directly. Neither call knows the other exists.

So both recompute the full subtree beneath fib(2), and the same thing happens at every level below. The duplication compounds rather than merely repeating.

The count makes it concrete. In the tree for fib(20), fib(2) is evaluated thousands of times, always returning 1.

Overlapping subproblems plus no memory equals exponential time, and both halves of that statement matter. The subproblems overlapping is a property of the problem, and having no memory is a property of the implementation.

Fixing the second half is the next lesson, and it is the doorway to dynamic programming.

power

Exponentiation by repeated multiplication, for exp ≥ 0.

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))
print(power(5, 3))
print(power(7, 0))

Output

1024
125
1

The base case is exp == 0 returning 1, since anything raised to the zero is 1, and 1 is the identity for multiplication in the same way 0 was for addition in total.

There is one self-call, so this tree is a straight line like factorial rather than a branching tree, which makes it O(exp) calls and O(exp) stack depth.

power(7, 0) hits the base case immediately and returns 1 without ever multiplying, which is the case that catches a base case written as exp == 1.

power(2, 10) gives 1024, which is 2¹⁰, and it took ten multiplications plus the base case.

There is a much better version worth knowing. Squaring power(base, exp // 2) and adjusting for an odd exponent halves the problem each time, which gives O(log exp) calls, so 2¹⁰⁰⁰ costs about 10 calls rather than 1,000.