Previous Section
 < Free Open Study > 
Next Section


7.4 Verifying Recursive Functions

The kind of walk-through we did in the previous section, to check the validity of a recursive function, is time-consuming, tedious, and often confusing. Furthermore, simulating the execution of Factorial (4) tells us that the function works when number = 4, but it doesn't tell us whether the function is valid for all nonnegative values of number. It would be useful to have a technique that would help us determine inductively whether a recursive algorithm works.

The Three-Question Method

We use the Three-Question Method to verify recursive functions. To confirm that a recursive solution works, you must be able to answer yes to all three of the following questions:

  1. The Base-Case Question: Is there a nonrecursive way out of the function, and does the routine work correctly for this base case?

  2. The Smaller-Caller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case?

  3. The General-Case Question: Assuming that the recursive call(s) works correctly, does the entire function work correctly?

Let's apply these three questions to the function Factorial. (We use the mathematical N here rather than the variable number.)

  1. The Base-Case Question: The base case occurs when N = 0. Factorial is then assigned the value of 1, which is the correct value of 0!, and no further (recursive) calls to Factorial are made. The answer is yes.

  2. The Smaller-Caller Question: To answer this question, we must look at the parameters passed in the recursive call. In the function Factorial, the recursive call passes N - 1. Each subsequent recursive call sends a decremented value of the parameter, until the value sent is finally 0. At this point, as we verified with the base-case question, we have reached the smallest case, and no further recursive calls are made. The answer is yes.

  3. The General-Case Question: In the case of a function like Factorial, we need to verify that the formula we are using actually results in the correct solution. Assuming that the recursive call Factorial(N - 1) gives us the correct value of (n - 1)!, the return statement computes N * (N - 1)!. This is the definition of a factorial, so we know that the function works for all positive integers. In answering the first question, we have already ascertained that the function works for N = 0. (The function is defined only for nonnegative integers.) Thus the answer is yes.

Those of you who are familiar with inductive proofs should recognize what we have done. Having made the assumption that the function works for some base case (n - 1), we can now show that applying the function to the next value, (n - 1) + 1, or n, results in the correct formula for calculating n!.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)