Java Reference
In-Depth Information
Let's rewrite the definition using programming notation; we call it
fact
.
fact(0) = 1
fact(n) = n * fact(n - 1), n > 0
The recursive definition of a function consists of two parts.
•
The base case, which gives the value of the function for a specific argument. This is also called
the
anchor
,
end case
, or
terminating case
, and it allows the recursion to terminate eventually.
•
The recursive (or general) case where the function is defined in terms of itself.
Shortly, we will write
fact
as a Java function. Before we do, we give a nonmathematical example of a recursive
definition. Consider how you might define
ancestor
. Loosely, we can say that an ancestor is one's parent, grandparent,
great-grandparent, and so on. But we can state this more precisely as follows:
a
is an ancestor of
b
if
(1)
a
is a parent of
b
, or
(2)
a
is an ancestor of
c
and
c
is a parent of
b
(1)
is the base case and
(2)
is the general, recursive case where
ancestor
is defined in terms of itself.
A less serious example is the meaning of the acronym LAME. It stands for LAME, Another MP3 Encoder.
Expanding LAME, we get LAME, Another MP3 Encoder, Another MP3 Encoder, and so on. We can say that LAME is a
recursive acronym. It's not a true recursive definition, though, since it has no base case.
5.2 Writing Recursive Functions in Java
We have seen many examples of functions that call other functions. What we have not seen is a function that calls
itself—a
recursive function
. We start off with
fact
.
public static int fact(int n) {
if (n < 0) return 0;
if (n == 0) return 1;
return n * fact(n - 1);
}
In the last statement of the function, we have a call to the function
fact
, the function we are writing. The function
calls itself.
Consider the following:
int n = fact(3);
It is executed as follows:
1.
3
is copied to a temporary location and this location is passed to
fact
where it becomes
the value of
n
.
2.
Execution reaches the last statement and
fact
attempts to return
3 * fact(2)
. However,
fact(2)
must be calculated before the return value is known. Think of this as just a call
to a function
fact
with argument
2
.
Search WWH ::
Custom Search