Fibonacci: when recursion repeats itself
Work out Fibonacci numbers with a function that calls itself twice. Count the calls as n grows, watch the same small calls happen over and over on the call stack, and see why remembering answers is so much faster.
Core concept
fib(n) = fib(n − 1) + fib(n − 2) with fib(0) = 0 and fib(1) = 1; because each call makes two more, the number of calls grows very fast, and the same answers are worked out many times
Topic: Functions and recursion
The Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8, 13: each is the sum of the two before it. That rule turns straight into a recursive function: fib(n) returns fib(n − 1) + fib(n − 2), with the base cases fib(0) = 0 and fib(1) = 1. It is short and correct, but it has a hidden cost. Every call that is not a base case makes two more calls, and those make two more each. fib(5) asks for fib(4) and fib(3), but fib(4) also asks for fib(3), so fib(3) is worked out twice, fib(2) three times, and so on. The number of calls grows almost as fast as the answers themselves. Remembering each answer once it is known, as the staircase lab does, avoids all that repeated work.
What you will learn
- Write the Fibonacci rule as a recursive function with two base cases.
- Trace the two calls each fib(n) makes on the call stack.
- Count how quickly the number of calls grows with n.
- Explain why remembering answers makes it faster.
Before you start
- Know how a recursive function and its base case work (the factorial lab).
Materials
- A notebook to draw the tree of calls
Equipment
- None
Procedure
- Step through fib(4) and watch the call stack.
- Run it for n = 1, then for n = 6, and compare the calls.
- Answer the practice challenges.