Recursion - Multimedia Introduction to Programming Using Java - page 418

Thus, we see that sorting an array of size 2 n requires at most n frames at any
one time. As an example, to sort an array of size 2 15 = 32768 , at most 15 frames
are needed. We have indeed achieved a significant reduction in space require-
ments —if tail-recursive calls are implemented efficiently.

15.4.6 Removing quicksort's tail recursion

In Sec. 15.3.3, we showed how to remove tail-recursive procedure calls. We use
this technique to remove the tail-recursive calls of procedure quicksort in Fig.
15.10, showing the result in Fig. 15.11. Figure 15.11, then, is our final version of
quicksort . For an array segment of size n , it takes space proportional to log n .
Its worst case time is proportional to n 2 , but its expected time is proportional to
n log n .

Activity
15-4.5

15.5 Object recursion

In a class C , we may create and store another instance of C , and, in that instance
we may create and store another instance of C , and so on. This is a form of recur-
sion, called object recursion . Of course, this process must stop at some point, or
else an unending number of instances of C will be created. A folder of class C that
contains a non- null field of class C is a recursive case of object recursion; a fold-
er of class C that does not contain a non- null field of class C is a base case .
We illustrate object recursion using a class that enumerates the permutations
of a String . The permutations of a String like "xyz" is the set of all its arrange-
ments, e.g.:

See lesson page
15.1 to get the
class for gener-
ating permuta-
tions from the
CD.

"xyz" , "xzy" , "yxz" , "yzx" , "zxy" , "zyx"
The only permutation of the empty String "" is itself, "" , and the only permu-
tation of a String of one element, like "x" , is itself.
We write a class PermutationGenerator with the following methods:
1. A constructor with a String parameter w .
2. A function nextElement ; which returns the “next” permutation of w .
3. A function hasMoreElements , which indicates whether nextElement
has been called enough times to produce all the permutations of w .
Suppose we execute:

PermutationGenerator e = new PermutationGenerator("xyz");
Then, six calls of the form e.nextElement() will produce the six permuta-
tions of "xyz" . Since we may not know how many permutations there are, we
should always call function e.hasMoreElements() before calling e.nextElem-
ent() , to make sure another permutation exists.
Class PermutationGenerator implements interface Enumeration (see
Sec. 12.3), but you do not have to understand interfaces to understand class