Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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

  equation443

However, we can also define factorial recursively as follows

displaymath57228

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.

   program456
Program: Recursive program to compute n!.

 

 

time

statement

n=0 n>0
5 tex2html_wrap_inline57242 tex2html_wrap_inline57242
6 tex2html_wrap_inline57178 --
8 -- tex2html_wrap_inline57248
tex2html_wrap_inline57250
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_inline57252, 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_inline57252, 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

  equation482

where tex2html_wrap_inline57256 and tex2html_wrap_inline57258. 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.