Recurrence Relations¶
1. Recurrence Relations¶
The running time for a recursive algorithm is most easily expressed by a recursive expression because the total time for the recursive algorithm includes the time to run the recursive call(s). A recurrence relation defines a function by means of an expression that includes one or more (smaller) instances of itself. A classic example is the recursive definition for the factorial function:
Another standard example of a recurrence is the Fibonacci sequence:
Fib(n)=Fib(n−1)+Fib(n−2) for n>2;Fib(1)=Fib(2)=1.
From this definition, the first seven numbers of the Fibonacci sequence are
Notice that this definition contains two parts: the general definition for Fib(n) and the base cases for Fib(1) and Fib(2). Likewise, the definition for factorial contains a recursive part and base cases.
Recurrence relations are often used to model the cost of recursive
functions.
For example, the number of multiplications required by a recursive
version of the factorial function for an input of size
n will be zero when n=0 or n=1 (the base
cases), and it will be one plus the cost of calling fact
on a
value of n−1.
This can be defined using the following recurrence:
As with summations, we typically wish to replace the recurrence relation with a closed-form solution. One approach is to expand the recurrence by replacing any occurrences of T on the right-hand side with its definition.
A slightly more complicated recurrence is
Again, we will use expansion to help us find a closed form solution.