TwiddleLab / Code / Recursion: Functions That Call Themselves
Trees of Calls
What you will learn
- A function that calls itself twice makes a call tree: every circle is one call.
- fib(n) = fib(n - 1) + fib(n - 2) works out the same small calls again and again: repeated work.
- The program walks the tree deep first, left before right. The path from the top to the current call is the stack.
- The number of calls grows about 1.6 times with each step of n: fib(40) makes over 331 million.
How the lesson goes
A tiny function counts rabbits. Month 15 is instant, month 40 takes minutes. Why?
fib(n) = fib(n - 1) + fib(n - 2): this month's rabbit pairs are last month's plus the month before. How many calls does fib(15) make?
Grow the tree of calls for fib(5).
Each circle is a call, the number is its n. fib(0) and fib(1) answer at once.
fib(5) needs fib(4) and fib(3). But fib(4) also needs fib(3). Nobody remembers the first answer, so it's worked out again, and the same happens lower down.
Turn n up. How fast does the tree grow?
Slide to 15 and compare with your bet.
Call tree and repeated work.
When a function calls itself more than once, its calls form a call tree. One circle per call.
fib asks for fib(n - 1) and fib(n - 2), and both of those ask for the same smaller calls. That's repeated work: identical subtrees, worked out from scratch each time.
Repeated work is why the tree, and the time, grow so fast.
Spot the repeats in the tree of fib(6).
Tap every copy of the call it asks for. Fast, and without misses.
In what order does the program make these calls?
Tap the calls of fib(4) one by one, in order.
fib(4) calls fib(3) first and waits. fib(3) calls fib(2), which calls fib(1), then fib(0). Only when a whole left side has answered does the program come back up and make the right call.
How many calls does fib(7) make?
One for fib(7) itself, plus all the calls of fib(6), plus all the calls of fib(5).
calls(7) = 1 + calls(6) + calls(5) = 1 + 25 + 15 = 41. In general calls(n) = 2 x fib(n + 1) - 1.
Plot the calls against n. What shape is it?
Drag each blue point to its number of calls. Use the same rule: 1 + the two before.
Each count is about the sum of the two before, so the ratio settles near 1.6 (the golden ratio). Multiplying by the same factor each step is exponential growth.
Month 40. How many calls does fib(40) make?
Drag the marker on this big scale, then Check. Within 3 times either way counts.
calls(40) = 2 x fib(41) - 1 = 331 160 281. 1973 x 1.6 to the 25th is about 250 million: the right ballpark.
Previous lesson: Trust the Smaller Problem · Next lesson: Remember Answers: Memoization · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
