Recursion tree
Overview
A recursion tree is a visual representation of branching recursive calls. The root represents the initial call, and children represent the subproblems spawned by that call.
It allows you to read the time complexity of an algorithm visually. By summing the total work done across all nodes at every level, you can determine if an algorithm is efficient (like merge sort) or explosively slow (like naive Fibonacci).
Why learn this
- It corrects the dangerous misconception that the time cost of recursion is merely its depth.
- It provides an intuitive way to understand divide-and-conquer runtime analysis (predicting runtime).
- Seeing how a leaf-heavy recursion tree explodes in size is exactly what motivates caching results (memoization).
Aha moment
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Prediction: Calculating `fib(5)` seems small, so it should only take a few steps.
Common guess: It makes 5 recursive calls because n=5.
`fib(5)` actually creates 15 total calls. `fib(3)` is computed 2 separate times, and `fib(2)` is computed 3 times. The total work is the sum of ALL nodes in the tree, not just the depth!
Common mistakes
- Assuming time complexity equals depth: Depth only tells you the space complexity (the height of the call stack). The time complexity is the sum of the work done by ALL nodes in the entire recursion tree.
- Ignoring overlapping subproblems: If a recursion tree repeatedly branches into subproblems that have already been solved elsewhere in the tree (like in naive Fibonacci), the tree grows exponentially. Caching these results (memoization) prevents recalculation, turning exponential growth into linear time.
Recall questions
- In a recursion tree, what determines the total time complexity?
- Why is the time complexity of a naive recursive Fibonacci O(2^n)?
- What is the purpose of memoization when applied to a recursion tree?
Understanding checks
Merge sort divides an array in two halves and takes O(n) time to combine them. Naive Fibonacci spawns two smaller calls and takes O(1) time to add them. Why is merge sort O(n log n) but Fibonacci O(2^n)?
Merge sort's tree is balanced: every level does O(n) total work, and there are log(n) levels. Fibonacci's tree is leaf-heavy: the number of nodes explodes exponentially because each node spawns two children but the input size only decrements by 1 or 2, creating massive overlapping subproblems.
A tree where the problem size is halved at each step stays shallow (log n depth) and balanced. A tree where the problem size is only decremented stays deep (n depth), causing exponential node explosion.
When writing a program to parse nested structures like HTML or mathematical formulas, multiple recursive functions call each other (e.g., `parseExpression` calls `parseTerm`, which might call `parseExpression` again). What does the resulting recursion tree represent?
The recursion tree implicitly builds the hierarchical structure of the parsed text.
This is a real-world engineering application known as mutual recursion. The shape of the call stack's recursion tree exactly mirrors the nested structure of the data being parsed.
Practice tasks
Draw the tree and count nodes
Sketch the recursion tree for the naive recursive function `fib(4)`, where `fib(n) = fib(n-1) + fib(n-2)`. How many times is `fib(2)` computed in total? What does this tell you about its time complexity?
Continue learning
Previous: The call stack