|
|
|
|
|
|
|
Recursion is a powerful technique when used correctly. Improperly used, recursion can cause errors that are difficult to diagnose. The best way to debug a recursive algorithm is to construct it correctly in the first place. To be realistic, however, we give a few hints about where to look if an error occurs. |
|
|
|
|
|
|
|
|
Testing and Debugging Hints |
|
|
|
|
|
|
|
|
1. Be sure there is a base case. If there is no base case, the algorithm continues to issue recursive calls until all of memory has been used. Each time the function is called, either recursively or nonrecursively, stack space is allocated for the parameters and automatic local variables. If there is no base case to end the recursive calls, the run-time stack eventually overflows. An error message such as "STACK OVERFLOW" indicates that the base case is missing. |
|
|
|
|
|
|
|
|
2. Be sure you have not used a While structure. The basic structure in a recursive algorithm is the If-Then-Else. There must be at least two cases: the recursive case and the base case. If the base case does nothing, the else-clause is not present. The selection structure, however, must be there. If a While statement is used in a recursive algorithm, the While statement usually should not contain a recursive call. |
|
|
|
|
|
|
|
|
3. As with nonrecursive functions, do not reference global variables directly within a recursive function unless you have justification for doing so. |
|
|
|
|
|
|
|
|
4. Formal parameters that relate to the size of the problem must be value parameters, not reference parameters. The actual parameters that relate to the size of the problem are usually expressions. Arbitrary expressions can be passed only to value parameters. |
|
|
|
|
|
|
|
|
5. 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. |
|
|
|
|
|
|
|
|
A recursive algorithm is expressed in terms of a smaller instance of itself. It must include a recursive 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 parameter that is being reduced with each call. In other problems, the smaller instance refers to the size of the data structure being manipulated. The base case is the one in which the size of the problem (value or structure) reaches a point where an explicit answer is known. |
|
|
|
|
|