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.