(See related pages)
|
|
|
| The purpose of this chapter was to familiarize you with the basic idea of recursion
so you will be able to understand the recursive methods in subsequent chapters and
to design your own recursive methods when the need arises.
A method is recursive if it can be called while it is active—an active method is
one that either is being executed or has called an active method.
If an iterative method to solve a problem can readily be developed, then that
should be done. Otherwise, recursion should be considered if the problem has the
following characteristics:
1. Complex cases of the problem can be reduced to simpler cases of the same
form as the original problem. 2. The simplest case(s) can be solved directly. For such problems, it is often straightforward to develop a recursive method. Whenever any method (recursive or not) is called, a new activation record is created to provide a frame of reference for the execution of the method. Each activation record contains ■ The return address, that is, the address of the statement that will be executed when the call has been completed. ■ The value of each actual parameter: a copy of the corresponding actual parameter is made (if the type of the argument is reference-to-object, the reference is copied). ■ The values of the method’s other local variables. Activation records make recursion possible because they hold information that might otherwise be destroyed if the method called itself. When the execution of the current method has been completed, a return is made to the address specified in the current activation record. The previous activation record is then used as the frame of reference for that method’s execution. Any problem that can be solved with recursive methods can also be solved iteratively, that is, with a loop. Typically, iterative methods are slightly more efficient than their recursive counterparts because far fewer activation records are created and maintained. But the elegance and coding simplicity of recursion more than compensates for this slight disadvantage. A backtracking strategy advances step-by-step toward a goal. At each step, a choice is made, but when a dead end is reached, the steps are retraced in reverse order; that is, the most recent choice is discarded and a new choice is made. Backtracking was deployed for the maze-search application above, and can be used in Programming Projects 4.2 (eight queens) and 4.3 (knight’s tour). |