Recursion - Multimedia Introduction to Programming Using Java - page 421

in two forms: recursive methods (methods that call themselves) and recursive
objects (objects of a class that contain an instance of the same class).

• Base cases and recursive cases. With regard to methods, a base case is a set
of parameter values for which no recursive call is necessary; these cases are in
some sense the “smallest” cases. A recursive case is a case in which a recursive
call is made on a smaller problem of the same kind.

• Model of execution. The model of execution of method calls that was present-
ed in Sec. 2.7 works even if there are recursive calls. A new frame is created
whenever the method is called, so several frames for different calls to the same
method may be in memory at the same time.

• Depth of recursion. The depth of recursion is the number of frames for calls
to the same method that have not yet completed. There should be a maximum
depth of recursion, or else there is infinite recursion.

• Two perspectives on recursion. There are two perspectives on recursive
method calls. To understand a body with a recursive call in it, understand that call
in terms of the spec of the method. To understand how recursion works in gen-
eral, look at how recursive calls are executed, using the model of memory.

• Tail recursion. A recursive call is tail recursive if nothing is done in the method
body once the call is completed. Tail-recursive calls can be implemented without
creating another frame. However, if the system does not do that, you can remove
tail-recursive calls yourself.

/** Variable word is not "" . If subEnum has no more enumerations, then add 1 to pos ,
keeping the definition of all fields true */
private void getReadyForNext() {
if (subEnum.hasMoreElements())
{ return ; }
pos= pos + 1;
if (pos == word.length()) {
hasAnother= false ;
return ;

}
// Store in subWord the word but without character word[pos]
// and create an enumeration subEnum for it
subWord= word.substring(0,pos) + word.substring(pos + 1);
subEnum= new PermutationGenerator(subWord);

}

}
Figure 15.13: Class PermutationGenerator (continued)