Algorithms from zero
The complexity of recursion
From the last lesson, you know that factorial(n) uses O(n) stack space: each recursive call pushes a frame, and the deepest recursion goes n levels. But what about time? Does a recursive function that calls itself twice per level take twice as long? What if it calls itself twice per call? We are about to learn a tool called the recursion tree that answers this. And we will discover something shocking: a small change in how many times a function calls itself can turn a practical algorithm into one that takes longer than the universe’s age.
After this lesson you can draw a recursion tree for a recursive function and use it to find the Big-O time complexity. You understand how the number of recursive calls per level (branching factor) and the depth of recursion combine to determine whether the time is linear, polynomial, or exponential. You know why naive recursive Fibonacci is catastrophically slow, and you recognize the pattern: a function that solves the same subproblem many times explodes in cost.
What is a recursion tree?
A recursion tree is a picture of all the function calls a recursive function makes. Each node represents one function call. The children of a node are the calls that node makes. The edges between parent and child show the call chain.
For example, the tree for factorial(4) is a straight line: factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1). There is one node per level, so 4 nodes total. Each node does O(1) work (one multiplication). Total: 4 nodes × O(1) = O(4) = O(n).
Branching factor and depth
The key to reading a recursion tree is two numbers:
- Branching factor — how many recursive calls does one function call make? For
factorial, it is 1 (one call per level). Forfibonacci(n) = fibonacci(n-1) + fibonacci(n-2), it is 2 (two calls). - Depth — how many levels does the tree go down before hitting the base case? For
factorial(n), it is n. Forfibonacci(n), it is also n.
The number of nodes in the tree is roughly branching_factor ^ depth (ignoring lower-order terms and constant factors).
The time complexity is the number of nodes times the work done per node. If each node does O(1) work, the time is O(branching_factor ^ depth).
Example 1: factorial(n)
factorial(n) = n × factorial(n - 1) calls itself once. Branching factor = 1. Depth = n. Tree structure:
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0) [base case]Number of nodes = 5 (for factorial(4)). Each node does O(1) work (one multiplication). Time complexity = 5 = O(n).
Example 2: Fibonacci (naive recursive)
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) calls itself twice per call (except base cases). Branching factor = 2. Depth = n.
Tree for fibonacci(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ...
/ \
fib(1) fib(0)At level 0: 1 node (the root, fib(5)).
At level 1: 2 nodes (fib(4), fib(3)).
At level 2: 4 nodes.
At level 3: 8 nodes.
…
At level n: 2^n nodes.
Total nodes ≈ 1 + 2 + 4 + 8 + … + 2^n ≈ 2^(n+1) - 1 ≈ O(2^n).
Each node does O(1) work. Time complexity = O(2^n). This is exponential time.
From the math track Linear vs exponential growthWhy is exponential bad?
Linear (O(n)): factorial(100) needs ~100 calls. Instant.
Exponential (O(2^n)): fibonacci(100) needs ~2^100 ≈ 10^30 calls. The universe’s age is ~10^10 seconds. Not in your lifetime.
Stack space is different from time
Recursion tree measures time. But remember: stack space is determined by depth, not the number of nodes. fibonacci(n) has:
- Time: O(2^n) (exponential — catastrophic)
- Stack space: O(n) (linear — fine, up to reasonable depths)
The time is the bottleneck, not the stack.
General formula: O(b^d)
For a recursive function:
- b = branching factor (calls per level)
- d = depth (levels until base case)
- Time = O(b^d) × work per node
If work per node is O(1), then time is O(b^d). If work per node is O(n), then time is O(n × b^d). And so on.
When b > 1 and d grows with input size, the time is exponential — and exponential is bad.
Let us write and test two recursive functions and see the difference in the number of calls.
Example 1: Factorial (linear, b=1)
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120Calls: factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) [base]. Total: 5 calls.
Example 2: Naive Fibonacci (exponential, b=2)
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)); // 5Calls: Much more. fibonacci(5) calls fibonacci(4) AND fibonacci(3). Then fibonacci(4) calls fibonacci(3) AND fibonacci(2). The same subproblem (like fibonacci(3)) gets solved many, many times.
Try both:
Let us visualize the recursion tree for fibonacci(5) by showing the call structure level by level.
1
function fibonacci(n) {
2
if (n <= 1) return n;
3
return fibonacci(n-1) + fibonacci(n-2);
4
}
Factorial: O(n) time, O(n) space
- Branching factor = 1 (one recursive call per level).
- Depth = n.
- Number of nodes = n.
- Work per node = O(1) (one multiplication).
- Time = O(n) × O(1) = O(n).
- Space (call stack) = O(n) (depth of tree).
Practical: factorial(100) is instant. factorial(10,000) might hit the stack limit, but time is never an issue.
Fibonacci (naive): O(2^n) time, O(n) space
- Branching factor = 2 (two recursive calls per level).
- Depth = n.
- Number of nodes ≈ 2^n.
- Work per node = O(1) (one addition).
- Time = O(2^n) × O(1) = O(2^n).
- Space (call stack) = O(n) (depth of tree).
Practical: fibonacci(20) makes ~20,000 calls. fibonacci(40) makes ~10^12 calls. Not practical without optimization (like memoization — more on that in the dynamic programming unit).
Why exponential time is catastrophic
With O(n): if you double the input, the work roughly doubles. With O(2^n): if you double the input (say from 20 to 40), the work roughly quadruples… no wait, it goes from ~10^6 to ~10^12 — a factor of a million. Exponential growth is brutal.
The power of branching factor
- b = 1: linear time O(n).
- b = 2: exponential time O(2^n).
- The change from 1 to 2 is the difference between “instant” and “impossible.”
This is why the naive recursive Fibonacci is a classic example of “do not write this code.”
How many calls does factorial(6) make? (Count each function call, including the base case.)
How many calls does fibonacci(4) make? (Hint: draw the tree or trace it.)
What is the branching factor of this function? function mystery(n) { if (n <= 1) return 1; return mystery(n-2) + mystery(n-2) + mystery(n-1); }
Approximately how many nodes are in the recursion tree of fibonacci(10)?
If you call fibonacci(20), roughly how many times is the base case reached?
Common mistake
Mistake: Thinking O(2ⁿ) is just “slow.” You write a recursive function that calls itself twice, test it on small inputs (n=10), and it runs instantly. So you ship it. Then a user passes n=30. The function does not crash; it just hangs forever. Your server timeout gets triggered. Users complain.
Exponential time is not just slow — it is catastrophic. A small input like 20 is fine. An input like 40 is literally not computable in human time scales. This is why it is so important to analyze the recursion tree before coding.
Edge cases
The same subproblem solved many times. The killer insight in the naive Fibonacci tree is that fibonacci(3) is computed twice, fibonacci(2) is computed three times, and so on. Each time we compute fibonacci(3), we also recompute fibonacci(2) inside it. This is massive waste.
Later, we will learn memoization and dynamic programming (next unit) to fix this: store the answers so each subproblem is solved only once. With memoization, fibonacci(n) drops from O(2^n) to O(n). The same code, just with memory. This is why learning to spot exponential recursion now is critical.
You write a recursive function that calls itself three times per level, with a depth of 10. Approximately how many total function calls does your program make?
Recursion tree: A picture of all the calls a recursive function makes. Each node is a call; children are the calls that node makes.
Branching factor (b): How many recursive calls does one function invocation make?
Depth (d): How many levels of recursion before hitting the base case?
Number of nodes ≈ b^d: This is the total number of function calls. Multiply by the work per node to get time complexity.
Examples:
factorial(n): b=1 (one call), d=n (n levels). Time = O(1^n) = O(n).- Naive
fibonacci(n): b=2 (two calls), d=n (n levels). Time = O(2^n) (exponential).
Why exponential is bad: With O(n), doubling the input doubles the time. With O(2^n), adding 10 to the input multiplies the time by 2^10 ≈ 1,000. Exponential grows so fast that it becomes impractical for any reasonably large input.
Key insight: A recursive function that re-solves the same subproblem many times (like Fibonacci) wastes a huge amount of work. Later techniques like memoization fix this by remembering answers.