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

∗