Recursion Fundamentals

Opening scenario

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1; each later number is the sum of the previous two. Write a recursive function that returns F(n) for a non-negative integer n. For fib(5), draw one node for each function call and connect it to the calls it makes. Which values does the function compute more than once?

Then try Towers of Hanoi: n disks are stacked on peg A, largest at the bottom. Move the stack to peg C using peg B as a spare, moving only one top disk at a time and never placing a larger disk on a smaller one. Return the sequence of moves. Can solving the same task for n-1 disks help?

These examples introduce two reasons a recursive program can take a long time: repeating the same calculation, and producing a long sequence of required moves. Start by tracing the calls; then consider which work can be avoided.