Java Reference
In-Depth Information
Within method call
A
, method calls
B
and
E
are made. The original method call has
not yet completed, so its stack frame remains on the stack. The first method call to be
made from within
A
is method call
B
, so the stack frame for method call
B
is pushed onto
the stack on top of the one for method call
A
. Method call
B
must execute and complete
before method call
E
is made. Within method call
B
, method calls
C
and
D
will be made.
Method call
C
is made first, and its stack frame is pushed onto the stack [part (b) of
Fig. 18.8]. Method call
B
has not yet finished, and its stack frame is still on the method-
call stack. When method call
C
executes, it makes no further method calls, but simply
returns the value
1
. When this method returns, its stack frame is popped off the top of the
stack. The method call at the top of the stack is now
B
, which continues to execute by per-
forming method call
D
. The stack frame for method call
D
is pushed onto the stack [part
(c) of Fig. 18.8]. Method call
D
completes without making any more method calls and
returns the value
0
. The stack frame for this method call is then popped off the stack. Now,
both method calls made from within method call
B
have returned. Method call
B
continues
to execute, returning the value
1
. Method call
B
completes, and its stack frame is popped
off the stack. At this point, the stack frame for method call
A
is at the top of the stack and
the method continues its execution. This method makes method call
E
, whose stack frame
is now pushed onto the stack [part (d) of Fig. 18.8]. Method call
E
completes and returns
the value
1
. The stack frame for this method call is popped off the stack, and once again
method call
A
continues to execute. At this point, method call
A
will not be making any
other method calls and can finish its execution, returning the value
2
to
A
's caller (
fibo-
nacci(3)
=
2
).
A
's stack frame is popped off the stack. The executing method is always the
one whose stack frame is at the top of the stack, and the stack frame for that method con-
tains the values of its local variables.
We've studied methods
factorial
and
fibonacci
, which can easily be implemented ei-
ther recursively or iteratively. In this section, we compare the two approaches and discuss
why you might choose one approach over the other in a particular situation.
Both iteration and recursion are
based on a control statement
: Iteration uses a repetition
statement (e.g.,
for
,
while
or
do
…
while
), whereas recursion uses a selection statement
(e.g.,
if
,
if
…
else
or
switch
). Both iteration and recursion involve
repetition
: Iteration
explicitly uses a repetition statement, whereas recursion achieves repetition through
repeated method calls. Iteration and recursion each involve a
termination test
: Iteration ter-
minates when the loop-continuation condition fails, whereas recursion terminates when a
base case is reached. Iteration with counter-controlled repetition and recursion both
grad-
ually approach termination
: Iteration keeps modifying a counter until the counter assumes
a value that makes the loop-continuation condition fail, whereas recursion keeps pro-
ducing smaller versions of the original problem until the base case is reached. Both itera-
tion and recursion
can occur infinitely
: An infinite loop occurs with iteration if the loop-
continuation test never becomes false, whereas infinite recursion occurs if the recursion
step does not reduce the problem each time in a manner that converges on the base case,
or if the base case is not tested.
To illustrate the differences between iteration and recursion, let's examine an iterative
solution to the factorial problem (Fig. 18.9). A repetition statement is used (lines 12-13)
rather than the selection statement of the recursive solution (lines 9-12 of Fig. 18.3). Both
