Java Reference

In-Depth Information

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

Search WWH ::

Custom Search