Up: Recursion. Prev: Program trace. Next: How long it takes.
A recurrence is a well-defined mathematical function written in terms of itself; it's a mathematical function defined recursively.
Take the Fibonacci sequence as an example. The Fibonacci sequence is the sequence of numbers
Let's define a function F(n) that returns the (n+1)th Fibonacci number. (Don't let the use of n+1 rather than n confuse you; it's just more convenient later if we begin numbering our sequence at 0.) First, we knock off the base cases:
Now we're going to use a recurrence to find how many times the monks will move a disk if they follow our MoveTower program. Before you read on, see if you can do this yourself.
Next: How long it takes.