Recursion - Multimedia Introduction to Programming Using Java - page 419

PermutationGenerator . Just know that by “enumerating” the permutations of
w we mean returning them, one by one, as the result of calls to function next-
Element . Also, the rule must be followed that nextElement is called only if it is
guaranteed that another permutation of w exists to be enumerated.
Class PermutationGenerator is in Figs. 15.12. and 15.13.
Our basic idea for enumerating the permutations of a String like "xyz" is
first to enumerate the permutations that begin with x , then to enumerate the per-
mutations that begin with "y" , and then to enumerate the permutations that begin
with "z" . We will do this using the following fields.
Variable word contains the word whose permutations are being enumerated,
and hasAnother indicates whether all its permutations have been enumerated.
Variable pos contains the index of a character in word , and permutations
beginning with character word[pos] are being enumerated. Variable subWord
then contains the characters of word but with character word[pos] removed.
Thus, we are in the process of constructing and enumerating:

word[pos] + first permutation of subWord
word[pos] + second permutation of subWord
…
word[pos] + last permutation of subWord
How do we construct these permutations of subWord ? We use an instance of
PermutationGenerator , whose name is stored in field subEnum . This is the
recursively constructed object.
At this point, turn to the beginning of Fig. 15.12 and read carefully the class
invariant, which describes the relation among the fields of the class.
Now, one can look at the constructor and see that it truthifies the represen-
tation invariant. Also, function hasMoreElements is easily seen to be correct.
Function nextElement is more complicated. First, if word is the empty
string, it sets hasAnother to indicate that there are no more permutations and
returns the empty string. If word is not the empty string, it first stores the next
permutation in variable next —the permutation is the character word[pos] cate-
nated with the next permutation of subWord . It then calls a private procedure
getReadyForNext , which appears in Fig. 15.13. This procedure does what has
to be done to make the class invariant true after permutation next is returned.
Then, permutation next is returned. And that is it.
Generating permutations would be much harder if we did not use recursive
objects. With them, the task turns out to be relatively simple.

15.6 Key concepts

• Recursive definitions. Recursive definitions play an important role in mathe-
matics and fields that use mathematics.

• Recursion methods and recursive objects. In programming, recursion comes