Recursion Trees and Exponential Recursion

Drawing the calls

A recursion tree draws each call as a node, labelled with the work done in that call outside its recursive calls. The total running time is the sum over all nodes. For merge sort, the root does n work, the two children do n/2 each (n total), the four grandchildren n/4 each (n total), and so on for log₂ n levels: n per level × log n levels = O(n log n). For naive Fibonacci, fib(n) calls fib(n-1) and fib(n-2); the tree branches twice at almost every node, so the number of calls grows exponentially. It is bounded above by O(2ⁿ), and more precisely grows like φⁿ, where φ ≈ 1.618 is the golden ratio. Even fib(50) needs tens of billions of calls. The same subproblems are computed again and again, which is exactly what memoisation and dynamic programming fix: storing each fib(k) once makes the algorithm O(n) time. Recursion trees make such repeated work visible.

Naive and memoised Fibonacci

The memoised version computes each value once.

def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# T(n) = T(n-1) + T(n-2) + O(1)  ->  exponential, about 1.618^n calls

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
# each of fib(0..n) computed once -> O(n) time, O(n) space for cache and call stack

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
# O(n) time, O(1) extra space

A family tree of phone calls

Naive Fibonacci is like a rumour where every person phones two others, who each phone two more: the number of calls explodes, and most people hear the same news many times. Memoisation is a notice board where each piece of news is posted once.

Quick check: Why is naive recursive Fibonacci exponential?

• It uses a loop inside the recursion
• It recomputes the same subproblems many times, with the call tree branching twice at each level
• Python recursion is slow
• It stores every result in memory