What Changes When Recursion Makes Two Calls?
Two recursive calls create a branching call tree. Correct indexing establishes the base values; overlapping branches explain exponential recomputation.
One recursive call usually forms a chain. Two calls form a tree. Fibonacci is the smallest example: each non-base state asks for the two preceding states.
State and indexing convention
This version is one-based: fib(1) = 1 and fib(2) = 1. That differs from a zero-based API where fib(0) = 0. State the convention before copying a recurrence.
Press Run to execute this example. Use console.log to print a value.
The correctness recurrence is F(n) = F(n - 1) + F(n - 2), with both bases equal to 1. The termination measure is n: every branch lowers it and eventually reaches a base.
Branching cost and a second combine rule
The running-time recurrence is T(n) = T(n - 1) + T(n - 2) + O(1), which is exponential. The maximum live stack is only O(n), because depth—not the total number of calls—controls stack space.
Nested depth has a different combine rule: a number returns 0; an array returns 1 + max(child depths); and an empty array returns 1. Two siblings cause two calls but do not add their depths. The parent keeps the larger branch.
Worked example and edges
fib(5) returns 5, but it computes fib(3) in both major branches. That repetition is the signal for memoisation. For nesting, [1, [2, [3]]] has depth 3, while [[], [1]] has depth 2.
- A base case must be correct and reachable on every branch.
- Addition combines Fibonacci counts; maximum combines alternative nesting branches.
- JavaScript engines do not guarantee tail-call optimisation, and two-call Fibonacci is not tail recursive.
- Do not “fix” exponential work by changing the recurrence; cache states without changing their meaning.
Optional enrichment
fibMemo is that exercise. Keep fib(1) = fib(2) = 1, store each completed n before the two calls return, and check the cache with !== undefined. n = 40 is the hidden time limit. The zero-based fib(0) = 0 form in the memoisation article is a different base case.