Tracing Recursion Trees

## What a recursion tree is A recursion tree is a drawing of one particular execution. Each **node** is a single invocation, labelled by the arguments it was called with. Each **edge** points from an invocation to a call it makes. The root is the original call; the leaves are the invocations that return without recursing (the base cases). Nothing about the drawing is metaphorical: the node count is the number of invocations that actually happen, and the height is the length of the longest chain of nested calls. Drawing the tree is the standard way to answer "how expensive is this?" without any algebra. You count nodes; if each node does a constant amount of its own work, the node count *is* the running time. ## The naive Fibonacci tree The naive definition recurses on `n-1` and `n-2` and returns immediately for `n <= 1`. Expanding `fib(6)`: - `fib(6)` calls `fib(5)` and `fib(4)`. - `fib(5)` calls `fib(4)` and `fib(3)`. - `fib(4)` calls `fib(3)` and `fib(2)`. And so on. Count how many times each label appears in the whole tree: | label | times it appears | |---|---| | fib(6) | 1 | | fib(5) | 1 | | fib(4) | 2 | | fib(3) | 3 | | fib(2) | 5 | | fib(1) | 8 | | fib(0) | 5 | That totals **25 invocations** to produce one number. Two things jump out of the drawing. First, the repeats are not incidental — `fib(2)` really is computed five separate times, from scratch, each time. Second, the repeats concentrate near the bottom: the leaves are the most-duplicated labels, and the leaves are the bulk of the tree. ## Depth is not count The left-most spine (`fib(6) -> fib(5) -> fib(4) -> ... -> fib(1)`) has about n links, so the tree's **height** is about n. That is the quantity people reach for when they say "it recurses n times". But the height counts one path; the cost counts every node on every path. In a tree where each node has two children, the number of nodes grows multiplicatively with height, not additively. Saying "it goes six deep, so six calls" silently assumes the tree is a chain — true for a single-call recursion, false the moment a second recursive call appears. ## Why the tree is lopsided This particular tree is not a perfect binary tree, because the two children shrink by different amounts: one branch drops by 1, the other by 2, so the `n-2` side bottoms out sooner and its subtree is smaller. That is why the totals follow the Fibonacci numbers themselves rather than powers of two, and why the growth rate is roughly 1.618 to the n rather than 2 to the n. It is still exponential — but a candidate who asserts "exactly 2^n calls" has drawn a tree that is not this one. ## What the drawing is worth in an interview The drawing answers three questions at once, and you should say all three out loud while you draw: 1. **How does it branch?** Two children per node here, so the width multiplies as you descend. 2. **How fast do arguments shrink?** By 1 and by 2, so the tree is deep — about n levels. (Compare a recursion that halves its argument: only about log n levels, a completely different shape.) 3. **Do labels repeat?** Yes, heavily — circle two nodes carrying the same label and note that their subtrees are byte-for-byte identical work. Those three observations are what an interviewer is listening for. The exponential blow-up is the consequence of the first two; the third is the observation that opens the door to computing each label once instead of many times. ## Common traps - **Counting levels instead of nodes.** Height and work are different quantities. - **Assuming the runtime remembers.** Nothing caches the repeated calls for you; `fib(2)` is recomputed every one of its five appearances. - **Assuming a perfect binary tree.** Levels are not uniformly full when the two branches shrink by different amounts. - **Stopping at "it's slow".** The interviewer wants the shape — branching factor, depth, repetition — not an adjective.