< Free Open Study > |
The questions used for verifying recursive functions can also serve as a guide for writing recursive functions. You can use the following approach to write any recursive routine:
Get an exact definition of the problem to be solved. (This, of course, is the first step in solving any programming problem.)
Determine the size of the problem to be solved on this call to the function. On the initial call to the function, the size of the whole problem is expressed in the value(s) of the parameter(s).
Identify and solve the base case(s) in which the problem can be expressed nonrecursively. This ensures a yes answer to the base-case question.
Identify and solve the general case(s) correctly in terms of a smaller case of the same problem-a recursive call. This ensures yes answers to the smaller-caller and general-case questions.
In the case of Factorial, the definition of the problem is summarized in the definition of the factorial function. The size of the problem is the number of values to be multiplied: N. The base case occurs when N = 0, in which case we take the nonrecursive path. Finally, the general case occurs when N > 0, resulting in a recursive call to Factorial for a smaller case: Factorial (N - 1).
Let's apply this approach to writing a Boolean function, ValueInList, that searches for a value in a list of integers and returns true or false to indicate whether the value is found. The list is declared as follows and is passed as a parameter to ValueInList:
The recursive solution to this problem is as follows:
Return (value is in the first position?) OR (value is in the rest of the list?)
We can answer the first question just by comparing the value to list.info[0]. But how do we know whether the value is in the rest of the list? If only we had a function that would search the rest of the list. But we do have one! The function ValueInList searches for a value in a list. We simply need to start searching at the first position, instead of the zeroth position (a smaller case). To do so, we need to pass the search-starting place to ValueInList as a parameter. We know that the end of the list is at position list.length - 1, so we can stop searching if the value isn't there. Thus we use the following function specification:
To search the whole list, we would invoke the function with the statement
if (ValueInList(list, value, 0))
The general case of this algorithm is the part that searches the rest of the list. This case involves a recursive call to ValueInList, specifying a smaller part of the array to be searched:
return ValueInList(list, value, startIndex + 1)
By using the expression startIndex + 1 as the parameter, we have effectively diminished the size of the problem to be solved by the recursive call. That is, searching the list from startIndex + 1 to list.length - 1 is a smaller task than searching from startIndex to list.length - 1. Figure 7.1 shows the function ValueInList frozen in midexecution.
Finally, we need to know when to stop searching. This problem involves two base cases: (1) the value is found (return true), and (2) we reach the end of the list without finding the value (return false). In either case, we can stop making recursive calls to ValueInList.
Let's summarize what we have discussed and then write the function ValueInList.
The code for function ValueInList follows:
bool ValueInList(ListType list, int value, int startIndex) { if (list.info[startIndex] == value) return true; // Base case 1 else if (startIndex == list.length-1) return false; // Base case 2 else return ValueInList(list, value, startIndex+1); }
The parameter startIndex acts as an index through the array; it is initialized in the original invocation of ValueInList and incremented on each recursive call. The equivalent iterative solution would use a local counter, initialized inside the function above the loop and incremented inside the loop.
Let's use the Three-Question Method to verify this function.
The Base-Case Question: One base case occurs when this call finds the value and the function is exited without any further calls to itself. A second base case occurs when we reach the end of the list without the value being found and the function is exited without any further recursive calls. The answer is yes.
The Smaller-Caller Question: The recursive call in the general case increments the value of Startlndex, making the part of the list left to be searched smaller. The answer is yes.
The General-Case Question: Let's assume that the recursive call in the general case correctly tells us whether the value is found in the second through last elements in the list. Then Base Case 1 gives us the correct answer (true) if the value is found in the first element in the list, and Base Case 2 gives us the correct answer (false) if the value is not in the first element and the first element is the only element in the list. The only other possible case is that the value exists somewhere in the rest of the list. Assuming that the general case works correctly, the entire function works, so the answer to this question is also yes.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |