The Fibonacci numbers start 0, 1, and each one after that is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, … Call the n-th one fib(n), counting from fib(0) = 0. So fib(6) = 8.
The rule says it directly: fib(6) is fib(5) + fib(4). And fib(5) needs fib(4) and fib(3), and fib(4) needs fib(3) and fib(2). Each call asks for two more. Watch what that does to the calls.
A function that calls itself twice
The calls of fib(6), drawn as a tree
int fib(int n){ calls++; if (n < 2) return n; int a = fib(n - 1); int b = fib(n - 2); return a + b;} int main(void){ int f = fib(N); printf("fib(%d) = %d in %ld calls\n", N, f, calls); return 0;}main calls fib(6).
- calls
- 0
- stack depth
- 0
- deepest
- 0
Output
Describe this picture
Lines 9 to 24 of fib.c, the function fib and main, with the line about to run marked, beside a picture in two parts. On the left, under the words “One circle per call fib(n); its value under it”, is a tree of circles: one circle for each call of fib, with n written in it. The first call, fib(6), is at the top, and each call’s two calls hang under it, fib(n − 1) on the left and fib(n − 2) on the right. The tree appears one circle at a time, in the order the calls are made: down the left side first, 6, 5, 4, 3, 2, 1, then 0, then back up and down again. The running call has a ring round it; the calls still waiting for an answer, the path from the top down to the ring, are edged in the accent colour; a finished call dims and shows the value it returned under its circle. On the right, under “Call stack”, is main’s card with its f, then one card per call of fib that has not returned yet, such as fib(4), with boxes for its a and b, a ”?” until written. A card shows the value it hands back as it returns, and that value flies into the a or b of the card above. The cards of fib are always the same calls as the edged path in the tree, never more. Under the picture are one sentence on the current step and three readouts: “calls” (circles drawn so far), “stack depth” (cards of fib now) and “deepest” (the most cards of fib so far). Then a slider, “n, the argument of fib”, from 1 to 10, set to 6, and the program’s output. The clip plays fib(6) once, about 33 seconds: the calls reach 25, the stack depth goes up and down and its deepest is 6, and the output reads fib(6) = 8 in 25 calls. Moving the slider shows the run for the new n already finished, with its whole tree; press play to watch it grow. At n = 10 the tree has 177 calls, drawn as small dots without numbers, and the deepest is 10. The transport plays and pauses, steps back or forward, and scrubs; n and a paused step are kept in the page address as fib-tree.n and fib-tree.step.
A tree of calls
Here is fib in C. As in Recursion (4.1), each result goes into its own variable on its own line, a and b, before they are added:
int fib(int n)
{
calls++;
if (n < 2)
return n;
int a = fib(n - 1);
int b = fib(n - 2);
return a + b;
}The base cases are n = 0 and n = 1, which return n itself. Any other call makes two recursive calls, and that changes the shape of the work. In 4.1 each call made one more call, so the calls formed a line. Here each call makes two, so they form a tree: the call tree. Each circle is a call, and the circles under it are the calls it made.
The two calls do not run at the same time. fib(6) calls fib(5) and waits until fib(5) has finished completely, with its whole subtree, before it even starts fib(4). That is why the tree in the clip grows down its left side first: 6, 5, 4, 3, 2, 1. Only when fib(1) returns 1 does fib(2) make its second call, fib(0).
Now look at the stack on the right while the tree grows. The stack never holds the tree. It holds only the calls still waiting: the path from the top of the tree down to the running call. When a call finishes, its card goes, and its circle stays in the tree only as a record. So the stack is at most as deep as the tree is tall. For fib(6) that is 6 cards, fib(6) down to fib(1).
Key idea
A function that calls itself twice makes a tree of calls, visited depth first, one call at a time. The stack holds only the path from the first call to the running one.
The code and its cost
Counting the calls
The program counts its calls in calls, a variable outside any function, marked static so that only this file can use it. Every call adds 1 to it on its first line. fib(6) makes 25 calls.
Count them another way. Write C(n) for the calls that fib(n) makes, including itself. fib(0) and fib(1) make one call each, themselves. Any other fib(n) makes itself plus all the calls of fib(n − 1) and of fib(n − 2):
So the counts go 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177 for n = 0 to 10. Each is the sum of the two before it, plus one. That is the Fibonacci rule again, and in fact C(n) = 2 fib(n + 1) − 1. For n = 6: 2 × fib(7) − 1 = 2 × 13 − 1 = 25.
Drag n in the instrument and read the “calls” readout. Each step of n multiplies the calls by about 1.6: 109 to 177 is × 1.62, and the ratio settles at 1.618…, the golden ratio. A count that is multiplied by a fixed number at each step grows exponentially.
The depth of the stack
The deepest path in the tree goes down the left side, taking 1 off n each time, from n to 1. So the stack holds at most n cards of fib (for n of 1 or more), plus main’s. The “deepest” readout shows it: 6 for fib(6), 10 for fib(10).
Time against space
Time counts the calls, and they grow exponentially. Space counts the frames on the stack at once, and they grow only with n, linearly. At n = 10 that is 177 calls but at most 10 frames.
fib is slow because it repeats work, not because recursion is slow. Look at the finished tree of fib(6): the subtree of fib(4) appears twice, fib(3) three times. Each copy is computed from scratch. Memoisation (4.7) keeps each answer the first time and turns the tree into a line.
Running it yourself
The program takes n from a macro, N, set to 6 unless you set it when you build:
gcc -std=c11 -Wall -Wextra -pedantic fib.c -o fib
./fib
gcc -std=c11 -Wall -Wextra -pedantic -DN=30 fib.c -o fib30
./fib30The first prints fib(6) = 8 in 25 calls.
Worked example
fib(5) by hand. Draw the tree: fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); and so on down to the 0s and 1s. Then count how often each call appears:
| Call | fib(5) | fib(4) | fib(3) | fib(2) | fib(1) | fib(0) | Total |
|---|---|---|---|---|---|---|---|
| Times made | 1 | 1 | 2 | 3 | 5 | 3 | 15 |
The total is 15 = 2 × fib(6) − 1 = 2 × 8 − 1. The leaves, the calls with n below 2, are the 5 calls of fib(1) and 3 of fib(0): 8 leaves, and the answer is the number of leaves that return 1, which is 5 = fib(5).
fib(30). Built with -DN=30, the program prints fib(30) = 832040 in 2692537 calls. Check it with the formula: 2 × fib(31) − 1 = 2 × 1,346,269 − 1 = 2,692,537. Almost 2.7 million calls, and yet the stack is never more than 30 frames of fib deep.
fib(50). By the formula it would take 2 × fib(51) − 1 = 2 × 20,365,011,074 − 1 = 40,730,022,147 calls. At a billion calls a second, a fast guess for one call, that is about 41 seconds, for a stack only 50 deep. (fib(50) = 12,586,269,025 is too large for an int, too, so the program would need a long long.)
Where it’s used
Searching through choices. A program that must try two choices at every step, such as taking an item or leaving it, has the same shape: a tree of calls with two branches each time. Searching this way is called backtracking, and Permutations (6.4) uses it.
Divide and conquer. Merge sort (17.5) and quicksort (17.6) also call themselves twice, once on each half of an array. Their halves never overlap, so no work is repeated and the tree stays small.
Measuring an algorithm. Drawing the call tree is a quick way to see the cost of any recursive function: count the circles for the time, and measure the height for the stack.
Reference card
| Idea | In this lesson |
|---|---|
| tree recursion | each call makes two recursive calls; the calls form a tree |
| order of the calls | depth first: the whole left subtree before the right call starts |
| what the stack holds | the path from the first call to the running one |
| calls of fib(n) | C(n) = C(n − 1) + C(n − 2) + 1, C(0) = C(1) = 1, so 2 fib(n + 1) − 1 |
| examples | fib(6): 25 calls; fib(10): 177; fib(30): 2,692,537 |
| growth | about × 1.618 per step of n: exponential time |
| stack depth | at most n frames of fib: linear space |
| why fib is slow | it repeats work: fib(4) twice, fib(3) three times inside fib(6) |
Platform: C11, gcc on x86-64 Linux, int 4 bytes. The cards in the picture show names and values only.