Java Reference
In-Depth 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 proce-
dure. 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. Since
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 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 informa-
tion 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 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 compu-
tation without producing any more recursive calls. When that 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 compu-
tation 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 defi-
nition 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 that is exactly what is
needed to keep track of recursive calls. Each suspended version is waiting for the comple-
tion of the version directly above it on the stack.
Of course, computers do not have stacks of paper. This is just an analogy. The com-
puter 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
last-in/
first-out
recursion
stack frame
Search WWH ::




Custom Search