Understanding the Recursion Tree Method
Learn how to draw and analyze Recursion Trees to calculate the time complexity of multi-branch recursive algorithms visually.
Visualizing Recursive Branching
When a recursive function calls itself exactly once, you get a straight line of execution (O(N)). But what happens when a function calls itself twice?
This creates a Recursion Tree, and analyzing it is a mandatory skill for dynamic programming.
The Fibonacci Example
Look at the naive recursive Fibonacci algorithm:
int fib(int n) {
if (n <= 1) return n;
// Double branching!
return fib(n - 1) + fib(n - 2);
}
Drawing the Tree
If you call fib(4), it splits into two calls: fib(3) and fib(2).
fib(3)splits intofib(2)andfib(1).fib(2)splits intofib(1)andfib(0).
This forms a visual tree.
- Level 1 has 1 node.
- Level 2 has 2 nodes.
- Level 3 has 4 nodes.
- Level 4 has 8 nodes.
Calculating the Complexity
Notice the pattern: the number of nodes (function calls) doubles at every level. The number of nodes at level L is 2^L.
Since the tree has a depth of roughly N, the total number of function calls is approximately 2^N.
The time complexity is a disastrous O(2^N) Exponential Time.
The Takeaway
Whenever you see a function making multiple recursive calls within its block, grab a piece of paper and draw the first three levels of the tree. The growth rate of the nodes at each level will immediately reveal whether your algorithm is polynomial or exponential.
A Recursion Tree is a visual diagram where each node represents a function call, and the branches represent the subsequent recursive calls made from that function.
You sum up the amount of non-recursive work done across all nodes at every level of the tree.
Because every function call spawns exactly two more function calls, causing the total number of operations to double at every level of depth.
You use Dynamic Programming (Memoization). By caching the result of a node, you prevent the tree from recalculating overlapping branches, collapsing O(2^N) into O(N).
The branching factor becomes 3. The tree grows by powers of 3, resulting in a time complexity of O(3^N).