Processing math: 100%
Close
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.32. Summations   ::   Contents   ::   0.34. Mathematical Proof Techniques  »

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:

n!=(n1)!n for n>1;1!=0!=1.

Another standard example of a recurrence is the Fibonacci sequence:

Fib(n)=Fib(n1)+Fib(n2) for n>2;Fib(1)=Fib(2)=1.

From this definition, the first seven numbers of the Fibonacci sequence are

1,1,2,3,5,8, and 13.

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 n1. This can be defined using the following recurrence:

T(n)=T(n1)+1 for n>1;T(0)=T(1)=0.

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.

1 / 8 Settings
<<<>>>

We will use expansion to guess the closed form solution for the recurrence $\mathbf{T}(n) = \mathbf{T}(n-1) + 1$ for $n > 1$; $\mathbf{T}(0) = \mathbf{T}(1) = 0$.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

A slightly more complicated recurrence is

T(n)=T(n1)+n;T(1)=1.

Again, we will use expansion to help us find a closed form solution.

1 / 8 Settings
<<<>>>

We will use expansion to guess the closed form solution for the recurrence $\mathbf{T}(n) = \mathbf{T}(n-1) + n\ \mbox{for}\ n > 1; \mathbf{T}(1) = 1$.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

   «  0.32. Summations   ::   Contents   ::   0.34. Mathematical Proof Techniques  »

nsf
Close Window