Hardware Reference
In-Depth Information
have been designed to do most of the procedure prolog and epilog work efficiently.
Of course, they have a particular model of how the frame pointer should be man-
aged, and if the compiler has a different model, they cannot be used.
Now let us get back to the Towers of Hanoi problem. Each procedure call adds
a new frame to the stack and each procedure return removes a frame from the
stack. In order to illustrate the use of a stack in implementing recursive proce-
dures, we will trace the calls starting with
towers(3, 1, 3)
Figure 5-40(a) shows the stack just after this call has been made. The procedure
first tests to see if
n
=
1, and on discovering that
n
=
3, fills in
k
and makes the call
towers(2, 1, 2)
After this call is completed the stack is as shown in Fig. 5-40(b), and the procedure
starts again at the beginning (a called procedure always starts at the beginning).
This time the test for
n
=
1 fails again, so it fills in
k
again and makes the call
towers(1, 1, 3)
The stack then is as shown in Fig. 5-40(c) and the program counter points to the
start of the procedure. This time the test succeeds and a line is printed. Next, the
procedure returns by removing one stack frame, resetting
FP
and
SP
to
Fig. 5-40(d). It then continues executing at the return address, which is the second
call:
towers(1, 1, 2)
This adds a new frame to the stack as shown in Fig. 5-40(e). Another line is
printed; after the return a frame is removed from the stack. The procedure calls
continue in this way until the original call completes execution and the frame of
Fig. 5-40(a) is removed from the stack. To best understand how recursion works, it
is recommended that you simulate the complete execution of
towers(3, 1, 3)
using pencil and paper.
In the usual calling sequence, there is a clear distinction between the calling
procedure and the called procedure. Consider a procedure
A
, on the left which
calls a procedure
B
on the right in Fig. 5-41.
Procedure
B
computes for a while and then afterwards returns to
A
. At first
sight you might consider this situation symmetric, because neither
A
nor
B
is a
main program, both being procedures. (Procedure
A
may have been called by the
