THE INSTRUCTION SET ARCHITECTURE LEVEL - Structured Computer Organization - page 409

public void towers(int n, int i, int j) {
int k;

if (n == 1)
System.out.println("Move a disk from"+i+"to"+j);
else {
k=6 − i − j;
towers(n 1, i, k);

towers(1, i, j);
towers(n − 1, k, j);

−

}

}

Figure 5-39. A procedure for solving the Towers of Hanoi.

Address

k k 1068

SP SP

Old FP = 1024 Old FP = 1024 1064

Return addr Return addr 1060

j=3 j=2 1056

i=1 i=1 1052

FP n=1 FP n=1 1048

SP k k=3 k k=3 1044

Old FP = 1000 Old FP = 1000 Old FP = 1000 Old FP = 1000 1040

Return addr Return addr Return addr Return addr 1036

j=2 j=2 j=2 j=2 1032

i=1 i=1 i=1 i=1 1028

n=2 n=2 n=2 n=2 1024

FP

SP k k=2 k=2 k=2 k=2 1020

Old FP Old FP Old FP Old FP Old FP 1016

Return addr Return addr Return addr Return addr Return addr 1012

j=3 j=3 j=3 j=3 j=3 1008

i=1 i=1 i=1 i=1 i=1 1004

FP n=3 n=3 n=3 n=3 n=3 1000

(a) (b) (c) (d) (e)

Figure 5-40. The stack at several points during the execution of Fig. 5-39.

state of the stack to what it was just prior to the current procedure invocation.
The code that saves the old frame pointer, sets up the new one, and advances
the stack pointer to reserve space for local variables is called the procedure pro-
log . Upon procedure exit, the stack must be cleaned up again, something called
the procedure epilog . One of the most important characteristics of any computer
is how short and fast it can make the prolog and epilog. If they are long and slow,
procedure calls will be expensive. Programmers who worship at the altar of ef-
ficiency will learn to avoid writing many short procedures and write large, mono-
lithic, unstructured programs instead. The Core i7 ENTER and LEAVE instructions