Java Reference
In-Depth Information
As usual,
2
is copied to a temporary location, and this location is passed to
fact
where
it becomes the value of
n
. If
fact
were a different function, there would be no problem.
But since it's the
same
function, what happens to the first value of
n
? It has to be saved
somewhere and reinstated when
this
call to fact finishes.
3.
4.
The value is saved on something called the
run-time stack
. Each time a function calls itself,
its arguments (and local variables, if any) are stored on the stack before the new arguments
take effect. Also, for each call, new local variables are created. Thus, each call has its own
copy of arguments and local variables.
5.
When
n
is
2
, execution reaches the last statement and
fact
attempts to return
2 * fact(1)
.
However,
fact(1)
must be calculated before the return value is known. Think of this as
just a call to a function
fact
with argument
1
.
6.
This call reaches the last statement and
fact
attempts to return
1 * fact(0)
. However,
fact(0)
must be calculated before the return value is known. Think of this as just a call to
a function
fact
with argument
0
.
7.
At this time, the run-time stack contains the arguments
3
,
2
, and
1
, with
1
at the top. The
call
fact(0)
reaches the second statement and returns a value of
1
.
8.
The calculation
1 * fact(0)
can now be completed, returning
1
as the value of
fact(1)
.
9.
The calculation
2 * fact(1)
can now be completed, returning
2
as the value of
fact(2)
.
10.
The calculation
3 * fact(2)
can now be completed, returning
6
as the value of
fact(3)
.
We should emphasize that this recursive version of
fact
is merely for illustrative purposes. It is not an efficient
way to calculate a factorial—think of all the function calls and the stacking and unstacking of arguments just to
multiply the numbers from
1
to
n
. A more efficient function is the following:
public static int fact(int n) {
int f = 1;
while (n > 0) {
f = f * n;
--n;
}
return f;
}
Another example of a function that can be defined recursively is the Highest Common Factor (HCF) of two
positive integers,
m
and
n
.
hcf(m, n) is
(1) m, if n is 0
(2) hcf(n, m % n), if n > 0
If
m
=
70
and
n
=
42
, we have this:
hcf(70, 42) = hcf(42, 70 % 42) = hcf(42, 28) = hcf(28, 42 % 28)
= hcf(28, 14) = hcf(14, 28 % 14) = hcf(14, 0) = 14
Search WWH ::
Custom Search