How many calls does naive recursive Fibonacci make, and why isn't it linear in n?

## What the code does The naive definition computes `fib(n)` as `fib(n-1) + fib(n-2)`, with `fib(0)` and `fib(1)` returning immediately. Two recursive calls per invocation, depth up to n. It is the canonical example of a recursion whose *shape* is small and whose *cost* is enormous, and interviewers ask about it precisely because two plausible wrong answers are so easy to reach for. ## The two wrong answers **"It's O(n), because there are only n+1 possible arguments."** True premise, wrong conclusion. There are indeed only n+1 distinct arguments, 0 through n — but the naive function has no memory. Nothing stops it from computing `fib(7)` fifty separate times, once per path in the tree that reaches it. The number of distinct arguments bounds how many *different* subproblems exist; it says nothing about how many *times* each is solved. Keeping those two counts apart is the whole lesson of the question. **"It's O(n) because the recursion is only n deep."** Depth bounds the live stack, not the work. A tree of depth n with branching can hold an exponential number of nodes while never having more than n+1 frames alive at once. ## Counting exactly Let C(n) be the total number of calls made to evaluate `fib(n)`, counting the initial call and every base case. Then: - C(0) = C(1) = 1 - C(n) = 1 + C(n-1) + C(n-2) Unrolling: C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15, C(6) = 25. Those are exactly `2·F(n+1) - 1`, where F is the Fibonacci sequence itself (F(0)=0, F(1)=1). Check n=5: F(6)=8, and 2·8−1 = 15. So **the cost of computing the nth Fibonacci number naively is itself proportional to the nth Fibonacci number** — a pleasingly self-referential fact, and one worth being able to state. Since F(n) ≈ φ^n / √5 with φ = (1+√5)/2 ≈ 1.618, the call count is Θ(φ^n). Every added n multiplies the work by about 1.618, so ten more inputs is roughly a 120× slowdown. ## Why 2^n is loose A complete binary tree of depth n has 2^n leaves, so 2^n is a valid upper bound — big-O is a ceiling, and quoting `O(2^n)` is not *wrong*. But the tree here is not complete. Following `n-1` repeatedly reaches a base case after about n steps; following `n-2` repeatedly reaches one after about n/2 steps. The right-hand subtrees are systematically shallower, so the tree is missing most of its right-hand mass. That squeezes the count between 2^(n/2) ≈ 1.414^n and 2^n, and the truth, 1.618^n, sits between them. In an interview, saying "exponential, base φ ≈ 1.618, and 2^n is a loose upper bound because the n-2 branch bottoms out sooner" is a distinctly stronger answer than "2^n". ## Additions, leaves and the arithmetic view There is a second exact count that makes the waste visceral. Every base case contributes a fixed value and every interior node performs exactly one addition. In a binary tree where every interior node has two children, leaves = interior + 1, so from C(n) = 2·F(n+1) − 1 the tree has F(n+1) leaves and F(n+1) − 1 additions. In other words, the algorithm reconstructs F(n) by adding up F(n) ones, one leaf at a time. It is not computing a number so much as counting to it. ## Time versus space The distinction is worth drilling because it is asked as a follow-up constantly. Time is Θ(φ^n): calls made over the whole run. Auxiliary space is Θ(n): only the current root-to-leaf path is live, so at most n+1 frames coexist. A tree with billions of nodes can run in a stack a few dozen frames deep. Recursion depth *is* part of space complexity — but it is the depth, not the node count, that lands there. ## Where the exponent actually comes from Generalising: the recurrence C(n) = C(n-1) + C(n-2) + O(1) reduces the argument by a *constant* each level while branching twice. Any recursion of the form "subtract a constant, branch b ways" costs roughly b^(n/c) — exponential in n. Contrast a recursion that *divides* the argument, where two branches over halved inputs give only a linear-times-log total. Subtracting versus dividing is the single structural feature that decides whether two-way branching is cheap or ruinous, and reading it off the call arguments takes a second once you know to look.