Java Reference
In-Depth Information
information in the stack, a clean sheet of paper is taken, the information is written on
it, and this new sheet of paper is placed on top of the stack. In this straightforward way,
more and more information may be placed on the stack.
Getting information out of the stack is also accomplished by a very simple procedure.
The top sheet of paper can be read, and when it is no longer needed, it is thrown away.
There is one complication: Only the top sheet of paper is accessible. In order to read,
say, the third sheet from the top, the top two sheets must be thrown away. Because the
last sheet that is put on the stack is the first sheet taken off the stack, a stack is often
called a
last-in/first-out
memory structure, abbreviated as
LIFO
.
Using a stack, the computer can easily keep track of recursion. Whenever a method
is called, a new sheet of paper is taken. The method definition is copied onto this
sheet of paper, and the arguments are plugged for the method parameters. Then the
computer starts to execute the body of the method definition. When it encounters a
recursive call, it stops the computation it is doing on that sheet in order to compute
the value returned by the recursive call. But, before computing the recursive call, it
saves enough information so that, when it does finally determine the value returned
by the recursive call, it can continue the stopped computation. This saved information
is written on a sheet of paper and placed on the stack. A new sheet of paper is used for
the recursive call. The computer writes a second copy of the method definition on this
new sheet of paper, plugs in the arguments for the method parameters, and starts to
execute the recursive call. When it gets to a recursive call within the recursively called
copy, it repeats the process of saving information on the stack and using a new sheet
of paper for the new recursive call. This process is illustrated in the earlier subsection
entitled “Tracing a Recursive Call.” Even though we did not call it a stack at the time,
the illustrations of computations placed one on top of the other illustrate the actions
of the stack.
This process continues until some recursive call to the method completes its
computation without producing any more recursive calls. When this happens, the
computer turns its attention to the top sheet of paper on the stack. This sheet contains
the partially completed computation that is waiting for the recursive computation that
just ended. So, it is possible to proceed with that suspended computation. When that
suspended computation ends, the computer discards that sheet of paper and the
suspended computation that is below it on the stack becomes the computation on
top of the stack. The computer turns its attention to the suspended computation
that is now on the top of the stack, and so forth. The process continues until the
computation on the bottom sheet is completed. Depending on how many recursive
calls are made and how the method definition is written, the stack may grow and
shrink in any fashion. Notice that the sheets in the stack can only be accessed in a
last-in/first-out fashion—but, this is exactly what is needed to keep track of recursive
calls. Each suspended version is waiting for the completion of the version directly
above it on the stack.
Of course, computers do not have stacks of paper. This is just an analogy. The
computer uses portions of memory rather than pieces of paper. The contents of one
of these portions of memory (“sheets of paper”) is called a
stack frame
or
activation
record
. These stack frames are handled in the last-in/first-out manner we just discussed.
last-in/
first-out
stack frame
activation
record
