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.
Sum [3, 1, 4, 1, 5, 9, 2, 6] by divide and conquer: a range of one element is its own sum, anything longer splits in the middle, sums both halves recursively and adds them. Each node is a range lo-hi of indices; the tree is balanced, so its depth is about log n.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
Range 0-7, 8 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 0-3, 4 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 0-1, 2 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 0-0, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 1-1, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 2-3, 2 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 2-2, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 3-3, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 4-7, 4 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 4-5, 2 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 4-4, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 5-5, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 6-7, 2 elements. What happens?
Answer: Split in the middle. Divide and conquer always splits until the base case.
Range 6-6, 1 element. What happens?
Answer: Return the element. One element is the base case.
Range 7-7, 1 element. What happens?
Answer: Return the element. One element is the base case.
How it runs, step by step
Sum [3, 1, 4, 1, 5, 9, 2, 6] by divide and conquer: a range of one element is its own sum, anything longer splits in the middle, sums both halves recursively and adds them. Each node is a range lo-hi of indices; the tree is balanced, so its depth is about log n.
Divide and conquer range sum over 8 values.
Range 0-7 has 8 elements. Split at 3: recurse on 0-3, then on 4-7, and combine afterwards. Depth 0.
Split 0 to 7 at 3.
Range 0-3 has 4 elements. Split at 1: recurse on 0-1, then on 2-3, and combine afterwards. Depth 1.
Split 0 to 3 at 1.
Range 0-1 has 2 elements. Split at 0: recurse on 0-0, then on 1-1, and combine afterwards. Depth 2.
Split 0 to 1 at 0.
Range 0-0 holds one element, 3: nothing to split, so it is the answer.
Leaf 0.
Leaf 0 returns 3.
Range 0 to 0 returns 3.
Range 1-1 holds one element, 1: nothing to split, so it is the answer.
Leaf 1.
Leaf 1 returns 1.
Range 1 to 1 returns 1.
Combine: 0-0 gave 3 and 1-1 gave 1, so 0-1 returns 4.
Range 0 to 1 returns 4.
Range 2-3 has 2 elements. Split at 2: recurse on 2-2, then on 3-3, and combine afterwards. Depth 2.
Split 2 to 3 at 2.
Range 2-2 holds one element, 4: nothing to split, so it is the answer.
Leaf 2.
Leaf 2 returns 4.
Range 2 to 2 returns 4.
Range 3-3 holds one element, 1: nothing to split, so it is the answer.
Leaf 3.
Leaf 3 returns 1.
Range 3 to 3 returns 1.
Combine: 2-2 gave 4 and 3-3 gave 1, so 2-3 returns 5.
Range 2 to 3 returns 5.
Combine: 0-1 gave 4 and 2-3 gave 5, so 0-3 returns 9.
Range 0 to 3 returns 9.
Range 4-7 has 4 elements. Split at 5: recurse on 4-5, then on 6-7, and combine afterwards. Depth 1.
Split 4 to 7 at 5.
Range 4-5 has 2 elements. Split at 4: recurse on 4-4, then on 5-5, and combine afterwards. Depth 2.
Split 4 to 5 at 4.
Range 4-4 holds one element, 5: nothing to split, so it is the answer.
Leaf 4.
Leaf 4 returns 5.
Range 4 to 4 returns 5.
Range 5-5 holds one element, 9: nothing to split, so it is the answer.
Leaf 5.
Leaf 5 returns 9.
Range 5 to 5 returns 9.
Combine: 4-4 gave 5 and 5-5 gave 9, so 4-5 returns 14.
Range 4 to 5 returns 14.
Range 6-7 has 2 elements. Split at 6: recurse on 6-6, then on 7-7, and combine afterwards. Depth 2.
Split 6 to 7 at 6.
Range 6-6 holds one element, 2: nothing to split, so it is the answer.
Leaf 6.
Leaf 6 returns 2.
Range 6 to 6 returns 2.
Range 7-7 holds one element, 6: nothing to split, so it is the answer.
Leaf 7.
Leaf 7 returns 6.
Range 7 to 7 returns 6.
Combine: 6-6 gave 2 and 7-7 gave 6, so 6-7 returns 8.
Range 6 to 7 returns 8.
Combine: 4-5 gave 14 and 6-7 gave 8, so 4-7 returns 22.
Range 4 to 7 returns 22.
Combine: 0-3 gave 9 and 4-7 gave 22, so 0-7 returns 31.
Range 0 to 7 returns 31.
Sum 31 from 15 calls, one per node. The recurrence is T(n) = 2 T(n / 2) + O(1): each level of the tree does constant work per node and there are about 2n nodes in all, so the sum costs O(n). With O(n) combine work per level, as in merge sort, the same tree gives O(n log n).
Sum 31 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