Recursion - Data Structures and Problem Solving Using Java - page 303

counter. You better write down on a piece of paper that you put the home
phone down (and where you left the phone!). While you are on the cell phone,
someone knocks on the door. You want to tell your cell phone partner to wait
while you deal with the door. So you put the cell phone down, and you better
write down another note on a piece of paper that you put the cell phone down
(and also where you left the cell phone!). At this point, you have made three
notes to yourself, with the cell phone note being the most recent. When you
open the door, the burglar alarm goes off because you forgot to deactivate it.
So you have to tell the person at the door to wait. You make another note to
yourself, while you deactivate the burglar alarm. Although you are over-
whelmed, you can now finish handling all the tasks that were started in
reverse order: the person at the door, the cell phone conversation, the home
phone conversation, and the file edit. You just have to go back through your
stack of notes that you made to yourself. Note the important phrasing: you are
maintaining a “stack.”
Java, like other languages such as C++, implements methods by using an
internal stack of activation records. An activation record contains relevant
information about the method, including, for instance, the values of the
parameters and local variables. The actual contents of the activation record is
system dependent.

The bookkeeping in
a procedural or
object-oriented lan-
guage is done by
using a stack of
activation records .
Recursion is a
natural by-product.

The stack of activation records is used because methods return in reverse
order of their invocation. Recall that stacks are great for reversing the order of
things. In the most popular scenario, the top of the stack stores the activation
record for the currently active method. When method G is called, an activa-
tion record for G is pushed onto the stack, which makes G the currently active
method. When a method returns, the stack is popped and the activation record
that is the new top of the stack contains the restored values.
As an example, Figure 7.5 shows a stack of activation records that occurs
in the course of evaluating s(4) . At this point, we have the calls to main , s(4) ,
and s(3) pending and we are actively processing s(2) .
The space overhead is the memory used to store an activation record for
each currently active method. Thus, in our earlier example where s(8883)
crashes, the system has room for roughly 8,883 activation records. (Note that
main generates an activation record itself.) The pushing and popping of the
internal stack also represents the overhead of executing a method call.

Method calling and
method return
sequences are
stack operations.

figure 7.5
A stack of activation
records

TOP:

s (2)
s (3)
s (4)
main ( )