A function that calls itself is not a trick. It is a way of describing a problem by what remains after you take one step.
Before reading on, revisit the loop chapter and make sure
you can trace fib(5) by hand. Every recursive definition has two parts: the
case you can answer immediately, and the case that gets you closer to it.
function fib(n) {
if (n < 2) return n
return fib(n - 1) + fib(n - 2)
}
| Call | Returns | Depth |
|---|---|---|
fib(0) | 0 | 1 |
fib(3) | 2 | 3 |
fib(5) | 5 | 5 |
The lab is due Thursday.
Most recursion bugs are stopping bugs. Write the case you can answer without help, then describe one step toward it.
- Name the smallest input the function must handle.
- Say what the function returns for that input.
- Only then write the call that shrinks the problem.
A recursive definition is a promise: if the smaller case works, this one does too.
- Write the call at the top of a page.
- Under it, write every call it makes.
- Resolve from the bottom up, filling in return values.
Show a worked example
fib(3) expands to fib(2) + fib(1). The base cases stop both branches.
Start the lab · Review the table
Tab through the links and disclosure to see keyboard focus. Open the example, then compare the same content in Focus and Slides using Player.