Recursion Trees
Draw every call a recursive function makes as a node, with the calls it makes as its children, and the running time is simply the size of the drawing. Fibonacci makes two calls per node, so the tree doubles with n and the same small arguments show up over and over: that repetition is what makes the plain version exponential. Memoization writes each answer down the first time, so a repeated argument becomes a leaf and the tree collapses to one expansion per distinct argument. Divide and conquer draws a different tree, balanced and only log n deep, because each call splits its input in half instead of shrinking it by one.
fib(5) calls fib(4) and fib(3), and each of those calls two more, until the base cases fib(1) and fib(0). Every call becomes a node here. Watch how often the same argument comes back: that repetition is the whole cost.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
Call fib(5). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(4). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(3). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(2). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(1). What does this node do?
Answer: Base case, returns 1. n <= 1 is answered directly.
Call fib(0). What does this node do?
Answer: Base case, returns 0. n <= 1 is answered directly.
Call fib(1). What does this node do?
Answer: Base case, returns 1. n <= 1 is answered directly.
Call fib(2). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(1). What does this node do?
Answer: Base case, returns 1. n <= 1 is answered directly.
Call fib(0). What does this node do?
Answer: Base case, returns 0. n <= 1 is answered directly.
Call fib(3). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(2). What does this node do?
Answer: Expands into two calls. Anything above 1 needs both smaller values first.
Call fib(1). What does this node do?
Answer: Base case, returns 1. n <= 1 is answered directly.
Call fib(0). What does this node do?
Answer: Base case, returns 0. n <= 1 is answered directly.
Call fib(1). What does this node do?
Answer: Base case, returns 1. n <= 1 is answered directly.
How it runs, step by step
fib(5) calls fib(4) and fib(3), and each of those calls two more, until the base cases fib(1) and fib(0). Every call becomes a node here. Watch how often the same argument comes back: that repetition is the whole cost.
Recursion tree of Fibonacci of 5.
fib(5) is not a base case, so it calls fib(4) first and fib(3) after that.
Call fib(5), which expands into two calls.
fib(4) is not a base case, so it calls fib(3) first and fib(2) after that.
Call fib(4), which expands into two calls.
fib(3) is not a base case, so it calls fib(2) first and fib(1) after that.
Call fib(3), which expands into two calls.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
Both children are back: fib(3) = fib(2) + fib(1) = 2.
fib(3) returns 2.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
Both children are back: fib(4) = fib(3) + fib(2) = 3.
fib(4) returns 3.
fib(3) is not a base case, so it calls fib(2) first and fib(1) after that.
Call fib(3), which expands into two calls.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
Both children are back: fib(3) = fib(2) + fib(1) = 2.
fib(3) returns 2.
Both children are back: fib(5) = fib(4) + fib(3) = 5.
fib(5) returns 5.
fib(5) = 5 after 15 calls. The tree roughly doubles with every extra n, so the time is exponential, about 1.6 to the power n, even though only 6 distinct arguments ever appear. Every repeated subtree is wasted work.
Result 5 after 15 calls.
Remember
- Count the nodes: the size of the recursion tree is the number of calls, which is the running time.
- Overlapping subproblems show up as identical subtrees; memoization turns each repeat into a leaf.
- Divide and conquer halves the input, so its tree is balanced with about log n levels.
Topics covered
What the words mean
- Recursion Tree
- Every call is a node, every recursive call a child; the size of the tree is the running time.
- Memoized Recursion
- Cache results by argument; a repeated call becomes a leaf that returns at once.
- Tree Recursion
- A function that makes more than one recursive call, so its calls form a tree that doubles with n.
- Recurrence Relations
- T(n) = a T(n / b) + f(n), the cost equation of a recursive algorithm, read off its recursion tree.
Where this is used
SecurityCatastrophic regex backtracking
A backtracking regex engine walks a tree of choices, one branch per way an optional or repeated group could match. When two quantifiers can cover the same text, the engine re-explores the same position through enormously many different paths, which is a recursion tree with overlapping subproblems and no memo, and it goes exponential in the input length. One such pattern in a WAF rule took Cloudflare's network down for 27 minutes on 2 July 2019; engines like RE2 avoid it entirely by tracking the set of states reachable at each position instead of backtracking.
DatabasesJoin order planning
Picking the order to join n tables is a search whose naive tree has factorial many leaves, because every permutation is its own path. PostgreSQL's planner keeps the cheapest plan found for each set of relations joined so far, so all the orderings that arrive at the same set collapse into a single node, exactly the trick memoization plays on fib. The collapsed search is still exponential in the number of tables, which is why at geqo_threshold FROM items or more, 12 by default, PostgreSQL gives up on exhaustive search and hands the problem to a genetic algorithm.
GamesTransposition tables in chess engines
A search expands a tree of moves, but different move orders reach identical boards: 1.d4 Nf6 2.c4 and 1.c4 Nf6 2.d4 are the same position. Stockfish hashes each position with a Zobrist key and stores the score and the depth it was searched to, so a transposition costs one table probe instead of an entire re-searched subtree. This is overlapping subproblems in a game tree, and the stored depth is what makes it safe: an entry searched shallower than the current call needs cannot be trusted as a score, only reused as a hint about which move to try first.
ConcurrencyFork-join parallelism
In a divide and conquer tree, sibling subtrees touch disjoint data, so they can run on separate cores with no locking, and the depth of the tree is the floor on how fast the job can finish no matter how many cores you add. Java's ForkJoinPool is shaped around exactly this: a task splits, forks its halves, joins their results, and idle workers steal the oldest queued subtask from another worker, which is the largest unclaimed chunk. Arrays.parallelSort stops splitting once a slice is under its granularity, which is the array length over four times the parallelism but never less than 8192 elements in the JDK, because below that the cost of making a task is more than the work inside it.
Why it works this way
Why is plain fib about 1.6 to the n, and not 2 to the n?
The tree is not a full binary tree. The fib(n - 2) child bottoms out a level sooner than the fib(n - 1) child, so the right side of every node is stunted and the lower levels are only partly filled. Counted exactly, fib(n) makes 2 * fib(n + 1) - 1 calls, which grows like 1.618 to the n, the golden ratio rather than 2. fib(5) draws 15 nodes here; a full binary tree of the same height would have 31.
Counting nodes only works when every node does the same work
fib does a constant amount of work per call, so the node count is the running time. Merge sort does not: a call on a slice of length k spends k steps merging, and its tree has only 2n - 1 nodes, which would wrongly suggest O(n). The general move is to add up the work level by level instead of node by node. Every level of merge sort touches n elements in total and there are about log n levels, which is where n log n comes from.
Memoization only pays when the same argument comes back
Caching rangeSum or merge sort buys nothing: every call there gets a slice no other call gets, so no node in the tree is ever a repeat and the cache only adds lookups. The test is whether the number of distinct arguments is far smaller than the number of calls, which for fib(30) is 31 against 2,692,537. The key must also cover every argument the result depends on; drop one and you silently hand back a different subproblem's answer.
Size is time, depth is space, and they are nothing like each other
The whole tree never exists at once. Only the path from the root down to the call currently running is live, so plain fib(40) runs 331 million calls while never holding more than about 40 stack frames. That is why an exponential recursion normally hangs rather than crashing, and why a merely linear recursion over a million-element list crashes the stack without being slow at all.
Read more
- Master theorem (analysis of algorithms)Wikipedia
- MemoizationWikipedia
- Regular expression matching can be simple and fastRuss Cox · swtch.com
- Details of the Cloudflare outage on July 2, 2019Cloudflare
- Genetic query optimization in PostgreSQLPostgreSQL docs · postgresql.org