Java Reference
In-Depth Information
3
5
5
5
3
3
3
pop
push 3
push 5
FIGURE 14.4:
Example of a stack.
pop
, we will get the number 5. If we execute the command
pop
again, we will get the number
3 and the stack will become empty.
During a program execution, Java creates a stack that is used to store system informa-
tion.
Every time a method is called (recursive or not), the value of all local variables
and the return address are stored in a frame and pushed on top of the stack. When
a method executes a
return
statement, the program pops the top frame of the stack.
It transitions to the return address and it loads the value for all the local variables of
the method from the frame.
Note that the same method can be executing multiple times at any given point, and for
every execution the value of the local variables can be different. Therefore, when we return
to a method, we need to know the value of all the local variables. We also need to know the
return point in the program when the
return
statement is reached. This is the information
thatissavedinthestack.
Let us consider the following recursive method that computes the factorial of a number.
public static int
f(
int
n)
{
if
(n == 0)
{
return
1;
return
f(n
−
1)
∗
n;
}
Consider Figure 14.5 (for simplicity, the return address is not shown in the figure). The
method first checks the base case. We know that 0! = 1. It then uses the recursive formula
n
!=(
n
n
to create the general case. In other words, the problem is reduced to a
smaller version of itself. Suppose the method is called with
n
= 2. Then the return value
will be
f(1)*2
.Beforethe
f
method can be called again, the value of
n
and the return point
are saved on the stack. Next, the method is called with
n
=1.Since1
−
1)!
∗
= 0, the method is
called again with
n
= 0. However, before this call can be made, the current value of
n
,which
is 1, together with the return point are stored on the stack. Now the method is executed
with
n
= 0 and the value 1 is returned. The
return
statement pops a frame from the stack.
The value of 1 is loaded into the variable
n
and the program jumps to the return address
that is stored on the stack. Now the method will return 1
1=1.The
return
statement
forces another frame to be popped from the stack. This time the value of 2 is loaded into
∗
