Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Analyzing Recursive Methods

In this section we analyze the performance of a recursive algorithm  which computes the factorial  of a number. Recall that the factorial of a non-negative integer n, written n!, is defined as

  equation449

However, we can also define factorial recursively as follows

displaymath57509

It is this latter definition which leads to the algorithm given in Program gif to compute the factorial of n. Table gif gives the running times of each of the executable statements in Program gif.

   program462
Program: Recursive program to compute n!.

 

 

time

statement

n=0 n>0
5 tex2html_wrap_inline57523 tex2html_wrap_inline57523
6 tex2html_wrap_inline57459 --
8 -- tex2html_wrap_inline57529
tex2html_wrap_inline57531
Table: Computing the running time of Program gif.

Notice that we had to analyze the running time of the two possible outcomes of the conditional test on line 5 separately. Clearly, the running time of the program depends on the result of this test.

Furthermore, the method Factorial calls itself recursively on line 8. Therefore, in order to write down the running time of line 8, we need to know the running time, tex2html_wrap_inline57533, of Factorial. But this is precisely what we are trying to determine in the first place! We escape from this catch-22 by assuming that we already know what is the function tex2html_wrap_inline57533, and that we can make use of that function to determine the running time of line 8.

By summing the columns in Table gif we get that the running time of Program gif is

  equation488

where tex2html_wrap_inline57537 and tex2html_wrap_inline57539. This kind of equation is called a recurrence relation  because the function is defined in terms of itself recursively.




next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.