Recursion Trees (Modeling Runtime Work)

Recursion tree diagrams nodes = calls, children = subcalls—visualize work duplication and depth to estimate time O(branching^depth).

Why this shows up in the real world

Algorithm analysis classes use recursion trees for unbalanced divide (e.g., quicksort random pivot expectation).

Core idea (explained for students)

Sum work per level for uniform cost per node; for Fibonacci naive tree, exponential nodes show need for memo.

Try this in Python

def fib_tree_cost(n: int) -> int:
    """Count calls in naive fib — illustrates blow-up."""
    if n <= 1:
        return 1
    return 1 + fib_tree_cost(n - 1) + fib_tree_cost(n - 2)


print(fib_tree_cost(6))

Common mistakes

• Drawing tree too large—annotate only generic level pattern.
• Ignoring different costs per node (uneven work).

Key takeaways

• Compare recursion tree to DAG of states after memoization.
• Use depth counter in debugger to spot blow-up.