System, but they may not be reproduced for publication

factorial of a number N is the product of all the whole numbers between 1 and N. For
example, 3 factorial is 1 × 2 × 3, or 6. The following program shows a recursive way to
compute the factorial of a number. For comparison purposes, a nonrecursive equivalent
is also included.

---

The output from this program is shown here:

---

The operation of the nonrecursive method factI( ) should be clear. It uses a loop
starting at 1 and progressively multiplies each number by the moving product.
The operation of the recursive factR( ) is a bit more complex. When factR( ) is called
with an argument of 1, the method returns 1; otherwise, it returns the product of
factR(n–1)*n. To evaluate this expression, factR( ) is called with n–1. This process
repeats until n equals 1 and the calls to the method begin returning. For example, when
the factorial of 2 is calculated, the first call to factR( ) will cause a second call to be
made with an argument of 1. This call will return 1, which is then multiplied by 2 (the
original value of n). The answer is then 2. You might find it interesting to insert
println( ) statements into factR( ) that show at what level each call is, and what the
intermediate results are.
When a method calls itself, new local variables and parameters are allocated storage on
the stack, and the method code is executed with these new variables from the start. A
recursive call does not make a new copy of the method. Only the arguments are new. As
each recursive call returns, the old local variables and parameters are removed from the
stack, and execution resumes at the point of the call inside the method. Recursive
methods could be said to “telescope” out and back.
Recursive versions of many routines may execute a bit more slowly than their iterative
equivalents because of the added overhead of the additional method calls. Too many
recursive calls to a method could cause a stack overrun. Because storage for parameters
and local variables is on the stack and each new call creates a new copy of these
variables, it is possible that the stack could be exhausted. If this occurs, the Java run­
time system will cause an exception. However, you probably will not encounter this
unless a recursive routine runs wild. The main advantage to recursion is that some
types of algorithms can be implemented more clearly and simply recursively than they
can be iteratively. For example, the Quicksort sorting algorithm is quite difficult to
implement in an iterative way. Also, some problems, especially AI­related ones, seem to
lend themselves to recursive solutions. When writing recursive methods, you must have
a conditional statement, such as an if, somewhere to force the method to return
without the recursive call being executed. If you don’t do this, once you call the method,
it will never return. This type of error is very common when working with recursion.
Use println( ) statements liberally so that you can watch what is going on and abort
execution if you see that you have made a mistake.
UNDERSTANDING STATIC

---

There will be times when you will want to define a class member that will be used
independently of any object of that class. Normally a class member must be accessed
through an object of its class, but it is possible to create a member that can be used by
itself, without reference to a specific instance. To create such a member, precede its
declaration with the keyword static. When a member is declared static, it can be
accessed before any objects of its class are created, and without reference to any object.
You can declare both methods and variables to be static. The most common example of
a static member is main( ). main( ) is declared as static because it must be called by
the JVM when your program begins. Outside the class, to use a static member, you
need only specify the name of its class followed by the dot operator. No object needs to
be created. For example, if you want to assign the value 10 to a static variable called
count that is part of the Timer class, use this line:
This format is similar to that used to access normal instance variables through an
object, except that the class name is used. A static method can be called in the same
way—by use of the dot operator on the name of the class.
Variables declared as static are, essentially, global variables. When an object is
declared, no copy of a static variable is made. Instead, all instances of the class share
the same static variable. Here is an example that shows the differences between a
static variable and an instance variable:

---

The output from the program is shown here:

---

As you can see, the static variable y is shared by both ob1 and ob2. Changing it affects
the entire class, not just an instance.
The difference between a static method and a normal method is that the static
method is called through its class name, without any object of that class being created.
You have seen an example of this already: the sqrt( ) method, which is a static method
within Java’s standard Math class. Here is an example that creates a static method:

---

The output is shown here:
Methods declared as static have several restrictions:
●
They can directly call only other static methods in their class.
●
They can directly access only static variables in their class.
●
They do not have a this reference.
For example, in the following class, the static method valDivDenom( ) is illegal:
Here, denom is a normal instance variable that cannot be accessed within a static
method.
Static Blocks
Sometimes a class will require some type of initialization before it is ready to create
objects. For example, it might need to establish a connection to a remote site. It also
might need to initialize certain static variables before any of the class’ static methods
are used. To handle these types of situations, Java allows you to declare a static block.
A static block is executed when the class is first loaded. Thus, it is executed before the
class can be used for any other purpose. Here is an example of a static block:

---

The output is shown here:
As you can see, the static block is executed before any objects are constructed.
Try This 6­3
The Quicksort
In 
Chapter 5
you were shown a simple sorting method called the Bubble sort. It was
mentioned at the time that substantially better sorts exist. Here you will develop a
version of one of the best: the Quicksort. The Quicksort, invented and named by C.A.R.
Hoare, is arguably the best general­purpose sorting algorithm currently available. The
reason it could not be shown in 
Chapter 5
is that the best implementations of the
Quicksort rely on recursion. The version we will develop sorts a character array, but the
logic can be adapted to sort any type of object you like.

---

The Quicksort is built on the idea of partitions. The general procedure is to select a
value, called the comparand, and then to partition the array into two sections. All
elements greater than or equal to the partition value are put on one side, and those less
than the value are put on the other. This process is then repeated for each remaining
section until the array is sorted. For example, given the array fedacb and using the
value d as the comparand, the first pass of the Quicksort would rearrange the array as
follows:
This process is then repeated for each section—that is, bca and def. As you can see, the
process is essentially recursive in nature, and indeed, the cleanest implementation of
Quicksort is recursive.
Assuming that you have no information about the distribution of the data to be sorted,
there are a number of ways you can select the comparand. Here are two. You can
choose a value at random from within the data, or you can select it by averaging a small
set of values taken from the data. For optimal sorting, you want a value that is precisely
in the middle of the range of values. However, this is often not practical. In the worst
case, the value chosen is at one extremity. Even in this case, however, Quicksort still
performs correctly. The version of Quicksort that we will develop selects the middle
element of the array as the comparand.
1. Create a file called QSDemo.java.
2. First, create the Quicksort class shown here:

---

To keep the interface to the Quicksort simple, the Quicksort class provides the qsort(
) method, which sets up a call to the actual Quicksort method, qs( ). This enables the
Quicksort to be called with just the name of the array to be sorted, without having to
provide an initial partition. Since qs( ) is only used internally, it is specified as
private.
3. To use the Quicksort, simply call Quicksort.qsort( ). Since qsort( ) is specified
as static, it can be called through its class rather than on an object. Thus, there is no
need to create a Quicksort object. After the call returns, the array will be sorted.
Remember, this version works only for character arrays, but you can adapt the logic to
sort any type of arrays you want.

---

4. Here is a program that demonstrates Quicksort:

---

INTRODUCING NESTED AND INNER CLASSES
In Java, you can define a nested class. This is a class that is declared within another
class. Frankly, the nested class is a somewhat advanced topic. In fact, nested classes
were not even allowed in the first version of Java. It was not until Java 1.1 that they
were added. However, it is important that you know what they are and the mechanics of
how they are used because they play an important role in many real­world programs.
A nested class does not exist independently of its enclosing class. Thus, the scope of a
nested class is bounded by its outer class. A nested class that is declared directly within
its enclosing class scope is a member of its enclosing class. It is also possible to declare
a nested class that is local to a block.
There are two general types of nested classes: those that are preceded by the static
modifier and those that are not. The only type that we are concerned about in this book
is the non­static variety. This type of nested class is also called an inner class. It has
access to all of the variables and methods of its outer class and may refer to them
directly in the same way that other non­static members of the outer class do.
Sometimes an inner class is used to provide a set of services that is used only by its

---

enclosing class. Here is an example that uses an inner class to compute various values
for its enclosing class:

---

The output from the program is shown here:
In this example, the inner class Inner computes various values from the array nums,
which is a member of Outer. As explained, an inner class has access to the members of
its enclosing class, so it is perfectly acceptable for Inner to access the nums array
directly. Of course, the opposite is not true. For example, it would not be possible for
analyze( ) to invoke the min( ) method directly, without creating an Inner object.
As mentioned, it is possible to nest a class within a block scope. Doing so simply creates
a localized class that is not known outside its block. The following example adapts the
ShowBits class developed in 
Try This 5­3
for use as a local class.

---

The output from this version of the program is shown here:

---

In this example, the ShowBits class is not known outside of main( ), and any attempt
to access it by any method other than main( ) will result in an error.
One last point: You can create an inner class that does not have a name. This is called
an anonymous inner class. An object of an anonymous inner class is instantiated when
the class is declared, using new. Anonymous inner classes are discussed further in
Chapter 16
.
VARARGS: VARIABLE-LENGTH ARGUMENTS
Sometimes you will want to create a method that takes a variable number of arguments,
based on its precise usage. For example, a method that opens an Internet connection
might take a user name, password, file name, protocol, and so on, but supply defaults if
some of this information is not provided. In this situation, it would be convenient to
pass only the arguments to which the defaults did not apply. To create such a method
implies that there must be some way to create a list of arguments that is variable in
length, rather than fixed.
Ask the Expert
Q
: What makes a static nested class different from a non­static one?
A
: A static nested class is one that has the static modifier applied. Because it is
static, it can access only other static members of the enclosing class directly. It
must access other members of its outer class through an object reference.
In the past, methods that required a variable­length argument list could be handled two
ways, neither of which was particularly pleasing. First, if the maximum number of
arguments was small and known, then you could create overloaded versions of the
method, one for each 221way the method could be called. Although this works and is
suitable for some situations, it applies to only a narrow class of situations. In cases
where the maximum number of potential arguments is larger, or unknowable, a second
approach was used in which the arguments were put into an array, and then the array
was passed to the method. Frankly, both of these approaches often resulted in clumsy
solutions, and it was widely acknowledged that a better approach was needed.
Beginning with JDK 5, this need was addressed by the inclusion of a feature that

---

simplified the creation of methods that require a variable number of arguments. This
feature is called varargs, which is short for variable­length arguments. A method that
takes a variable number of arguments is called a variable­arity method, or simply a