Java Reference
In-Depth Information
To better understand the concept of recursion, let's look at an example that's quite
familiar to computer users—the recursive definition of a file system directory on a com-
puter. A computer normally stores related files in a directory. A directory can be empty,
can contain files and/or can contain other directories (usually referred to as subdirectories).
Each of these subdirectories, in turn, may also contain both files and directories. If we
want to list each file in a directory (including all the files in the directory's subdirectories),
we need to create a method that first lists the initial directory's files, then makes recursive
calls to list the files in each of that directory's subdirectories. The base case occurs when a
directory is reached that does not contain any subdirectories. At this point, all the files in
the original directory have been listed and no further recursion is necessary.
Let's write a recursive program to perform a popular mathematical calculation. Consider
the
factorial
of a positive integer
n
, written
n
! (pronounced “
n
factorial”), which is the
product
n
· (
n
- 1) · (
n
- 2) · … · 1
with 1! equal to 1 and 0! defined to be 1. For example, 5! is the product 5 · 4 · 3 · 2 · 1,
which is equal to 120.
The factorial of integer
number
(where
number
≥
0) can be calculated
iteratively
(non-
recursively) using a
for
statement as follows:
factorial =
1
;
for
(
int
counter = number; counter >=
1
; counter--)
factorial *= counter;
A recursive declaration of the factorial calculation for integers greater than 1 is arrived
at by observing the following relationship:
n
! =
n
· (
n
- 1)!
For example, 5! is clearly equal to 5 · 4!, as shown by the following equations:
5! = 5 · 4 · 3 · 2 · 1
5! = 5 · (4 · 3 · 2 · 1)
5! = 5 · (4!)
The evaluation of 5! would proceed as shown in Fig. 18.2. Figure 18.2(a) shows how
the succession of recursive calls proceeds until 1! (the base case) is evaluated to be 1, which
terminates the recursion. Figure 18.2(b) shows the values returned from each recursive call
to its caller until the final value is calculated and returned.
Figure 18.3 uses recursion to calculate and print the factorials of the integers 0
through 21. The recursive method
factorial
(lines 7-13) first tests to determine whether
a
terminating
condition
(line 9) is
true
. If
number
is less than or equal to
1
(the base case),
factorial
returns
1
, no further recursion is necessary and the method returns. (A precon-
dition of calling method
factorial
in this example is that its argument must be non-neg-
ative.) If
number
is greater than
1
, line 12 expresses the problem as the product of
number
and a recursive call to
factorial
evaluating the factorial of
number - 1
, which is a slightly
smaller problem than the original calculation,
factorial(number)
.