Hardware Reference
In-Depth Information
Peg 1
Peg 2
Peg 3
Figure 5-37.
Initial configuration for the Towers of Hanoi problem for five disks.
to solve the problem of Fig. 5-38 generates three more calls. Specifically, it makes
the calls
towers(2, 1, 2)
towers(1, 1, 3)
towers(2, 2, 3)
The first and third will generate three calls each, for a total of seven.
In order to have recursive procedures, we need a stack to store the parameters
and local variables for each invocation, the same as we had in IJVM. Each time a
procedure is called, a new stack frame is allocated for the procedure on top of the
stack. The frame most recently created is the current frame. In our examples, the
stack grows upward, from low memory addresses to high ones, just like in IJVM.
So the most recent frame has higher addresses than all the others.
In addition to the stack pointer, which points to the top of the stack, it is often
convenient to have a frame pointer,
FP
, which points to a fixed location within the
frame. It could point to the link pointer, as in IJVM, or to the first local variable.
Figure 5-39 shows the stack frame for a machine with a 32-bit word. The original
call to
towers
pushes
n
,
i
, and
j
onto the stack and then executes a
CALL
instruction
that pushes the return address onto the stack, at address 1012. On entry, the called
procedure stores the old value of
FP
on the stack at 1016 and then advances the
stack pointer to allocate storage for the local variables. With only one 32-bit local
variable (
k
),
SP
is incremented by 4 to 1020. The situation, after all these things
have been done, is shown in Fig. 5-39(a).
The first thing a procedure must do when called is save the previous
FP
(so it
can be restored at procedure exit), copy
SP
into
FP
, and possibly increment by one
word, depending on where in the new frame
FP
points. In this example,
FP
points
to the first local variable, but in IJVM,
LV
pointed to the link pointer. Different
