Up: Recursion. Prev: Program trace. Next: How long it takes.

What is a recurrence?

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... The first two numbers of the sequence are both 1, while each succeeding number is the sum of the two numbers before it. (We arrived at 55 as the tenth number, since it is the sum of 21 and 34, the eighth and ninth 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:

F(0) = 1
F(1) = 1 Now we consider the other numbers. To get the (n+1)th Fibonacci, we just add the nth Fibonacci and the (n-1)th Fibonacci. F(n) = F(n - 1) + F(n - 2) This function F is called a recurrence, since it is defined in terms of itself evaluated at other values.

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.