Java Reference
In-Depth Information
(These stack frames do not contain a complete copy of the method definition, but
merely reference a single copy of the method definition. However, a stack frame
contains enough information to allow the computer to act as if the stack frame contains
a complete copy of the method definition.)
Stack
A stack is a last-in/first-out memory structure. The first item referenced or removed from a
stack is always the last item entered into the stack. Stacks are used by computers to keep
track of recursion (and for other purposes).
VideoNote
Recursion and
the Stack
PITFALL: Stack Overflow
There is always some limit to the size of the stack. If there is a long chain in which a
method makes a recursive call to itself, and that call results in another recursive call,
and that call produces yet another recursive call, and so forth, then each recursive call
in this chain will cause another suspended computation to be placed on the stack. If
this chain is too long, then the stack will attempt to grow beyond its limit. This is
an error condition known as a stack overflow . If you receive an error message that
says stack overflow , it is likely that some method call has produced an excessively long
chain of recursive calls. One common cause of stack overflow is infinite recursion. If
a method is recursing infinitely, then it will eventually try to make the stack exceed
any stack size limit.
Recursion versus Iteration
Recursion is not absolutely necessary. In fact, some programming languages do not
allow it. Any task that can be accomplished using recursion can also be done in some
other way without using recursion. For example, Display 11.2 contains a nonrecursive
version of the method given in Display 11.1. The nonrecursive version of a method
typically uses a loop (or loops) of some sort in place of recursion. For this reason, the
nonrecursive version is usually referred to as an iterative version . If the definition of
the method writeVertical given in Display 11.1 is replaced by the version given
in Display 11.2, then the output will be the same. As is true in this case, a recursive
version of a method can sometimes be much simpler than an iterative version. The full
program with the iterative version of the method is given in the file IterativeDemo1
on the accompanying website.
A recursively written method will usually run slower and use more storage than
an equivalent iterative version. The computer must do extra work manipulating the
stack to keep track of the recursion. However, because the system does all this for you
automatically, using recursion can sometimes make your job as a programmer easier,
and can sometimes produce code that is easier to understand. Additionally, there are
some cases in which the compiler or JVM can convert a recursive algorithm into an
iterative version for you.
iterative
version
extra code on
website
 
Search WWH ::




Custom Search