The Fibonacci numbers start 0, 1, and each one after that is the sum of the two before it. Written as a recursive function the rule takes one line, and it is exponentially slow. This page counts every call it makes, then cuts the work to a straight line with a memo table, and to a handful of steps with fast doubling.
The definition F(n) = F(n−1) + F(n−2) turns straight into code. Every call that isn't F(0) or F(1) makes two more calls, and nothing remembers what was already worked out. The tree grows depth-first, one stack frame at a time. Nodes of the same color ask the same question again.
How to read this: Each circle is one call to fib, with its input inside. Each row is one level deeper. The number under a finished circle is what it returned. In Color by input, colors match the chips above; hover or tap a chip to pick out every call with that input.
Try this: Press Reset, then Step a few times and watch the amber path grow down the left side. Then switch to Color by state to see the red repeats.
The call count obeys the same recurrence as F itself, plus one for the call in hand. So the work grows as fast as the answer does, by a factor of about 1.618 per step, the ratio from 001 · Golden ratio.
Times assume a machine that makes one billion calls per second. Red marks anything over one second.
Keep a table, the memo, of every F(k) already computed. Before doing any work, a call looks up its input. On a hit it returns at once, so its whole subtree never happens. Flip between the two versions on the same n and compare the trees.
How to read this: Each circle is one call. A small dashed circle is a call answered straight from the memo, so nothing grows below it. In the memo row, the small number on top is k and the big number is the saved F(k).
Try this: Set n to 8 and flip Naive and Memoized; count how much of the tree disappears.
The first child of each call walks straight down the left edge, filling the memo from memo[0] and memo[1] upward. By the time a call asks for its second child, fib(n−2), the answer is already stored. That gives n + 1 computed calls, one for each input from 0 to n, plus n − 2 hits.
Time drops from exponential to O(n). The price is O(n) memory for the table, and the recursion still goes n frames deep. This is top-down 004 · Dynamic programming.
Two more methods race here, one step per tick. Iteration builds from the bottom and only ever keeps the last two numbers. Fast doubling reads the bits of n from the top and jumps from F(k) to F(2k) or F(2k+1) each step, so it needs about log₂ n steps. Numbers are exact BigInts.
How to read this: The top bar fills one step per tick. The boxes below are n written in binary; the doubling method reads one box per tick, so it finishes after only a few ticks. O(n) and O(log n) say the work grows with n, or only with the number of binary digits of n. Dim table rows are steps still to come.
Try this: Press 1000 and watch the bottom track finish in 10 ticks while the top bar barely moves.
Both identities come from squaring the matrix [[1,1],[1,0]], whose n-th power holds F(n+1), F(n) and F(n−1). Each bit of n doubles k, and a 1 bit adds one more.
The step counts flatter doubling a little. F(n) has about 0.209·n digits, so late multiplications are on long numbers and cost more than early ones. It still wins by a wide margin for large n.