Previous Section
 < Free Open Study > 
Next Section


7.12 Debugging Recursive Routines

Because of their nested calls to themselves, recursive routines can prove confusing to debug. The most serious problem relates to the possibility that the routine recurses forever. A typical symptom of this problem is an error message noting that the system has run out of space in the run-time stack, due to the level of recursive calls. Using the Three-Question Method to verify recursive functions should help us avoid this problem of never finishing. If we can answer yes to the base-case and smaller-caller questions, then we should be able to guarantee that the routine eventually ends-theoretically, at least.

That does not guarantee, however, that the program will not fail due to lack of space. In the previous section, we saw that a function call requires a certain amount of overhead to save the parameters, the return address, and the local data. A call to a recursive function may generate many, many levels of function calls to itself-more than the system can handle.

One error that programmers often make when they first start writing recursive routines is to use a looping structure instead of a branching one. Because they tend to think of the problem in terms of a repetitive action, they inadvertently use a while statement rather than an if statement. The main body of the recursive routine should always break down into base and recursive cases. Hence, we use a branching statement, not a looping statement. It's a good idea to double-check your recursive functions to make sure that you used an if or switch statement to achieve a branching effect.

Recursive routines are good places to put debug output statements during testing. Print out the parameters and local variables, if any, at the beginning and end of the function. Be sure to print out the values of the parameters on the recursive call(s) to verify that each call attempts to solve a problem smaller than the previous one.



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