Summary | 653statement is used in a recursive algorithm, it usually should not contain a re-
cursive call.
3.Use your system’s debugger program (or use debug output statements) to
trace a series of recursive calls. Inspecting the values of parameters and local
variables often helps to locate errors in a recursive algorithm.Summary
A recursive algorithm is expressed in terms of a smaller instance of itself. It must in-
clude a recursive (or general) case, for which the algorithm is expressed in terms of
itself, and a base case, for which the algorithm is expressed in nonrecursive terms.
In many recursive problems, the smaller instance refers to a numeric argument
that is reduced with each call. In other problems, the smaller instance refers to the
size of the data structure being manipulated. In the base case, the size of the
problem (value or structure) reaches a point for which an explicit answer is known.
In the conversion of decimal integers to binary numbers, the size of the problem
is the number to be converted. When it is 0, the conversion is finished. In the Towers
of Hanoi game, the size of the problem is the number of discs to be moved. When
only one is left on the beginning peg, it can be moved to its final destination.
In the example of printing an array using recursion, the size of the problem is the
size of the array being printed. When the array size reaches 1, the solution is known.
In the binary search algorithm, the size of the problem is the size of the search area.
There are two base cases in this algorithm: (1) when the search item is found and (2)
when the search area becomes empty and you know that the search value is not
there.
Quick Check
1.What is the essential ingredient in a recursive definition? (pp. 636–637)
2.What distinguishes the base case from the recursive case in a recursive
algorithm? (pp. 636–637)
3.What is the size of the problem in the recursive power algorithm? (pp. 636–638)
4.What is the base case in the Towers of Hanoi algorithm? (pp. 644–648)