Hardware Reference
In-Depth Information
control, such as
while
loops. Of course, these programs compile down to level 2
programs that may contain many branches, because the implementation of
if
,
while
,
and other high-level control structures requires branching around.
The most important technique for structuring programs is the procedure. From
one point of view, a procedure call alters the flow of control just as a branch does,
but unlike the branch, when finished performing its task, it returns control to the
statement or instruction following the call.
However, from another point of view, a procedure body can be regarded as
defining a new instruction on a higher level. From this standpoint, a procedure call
can be thought of as a single instruction, even though the procedure may be quite
complicated. To understand a piece of code containing a procedure call, it is only
necessary to know
what
it does, not
how
it does it.
One particularly interesting kind of procedure is the
recursive procedure
, that
is, a procedure that calls itself, either directly or indirectly via a chain of other pro-
cedures. Studying recursive procedures gives considerable insight into how proce-
dure calls are implemented, and what local variables really are. Now we will give
an example of a recursive procedure.
The ''Towers of Hanoi'' is an ancient problem that has a simple solution in-
volving recursion. In a certain monastery in Hanoi, there are three gold pegs.
Around the first one were a series of 64 concentric gold disks, each with a hole in
the middle for the peg. Each disk is slightly smaller in diameter than the disk di-
rectly below it. The second and third pegs were initially empty. The monks there
are busily transferring all the disks to peg 3, one disk at a time, but at no time may
a larger disk rest on a smaller one. When they finish, it is said the world will come
to an end. If you wish to get hands-on experience, it is all right to use plastic disks
and fewer of them, but when you solve the problem, nothing will happen. To get
the end-of-world effect, you need 64 of them and in gold. Figure 5-37 shows the
initial configuration for
n
5 disks.
The solution of moving
n
disks from peg 1 to peg 3 consists first of moving
=
n
1 disks from peg 1 to peg 2, then moving 1 disk from peg 1 to peg 3, then
moving
n
−
1 disks from peg 2 to peg 3. This solution is illustrated in Fig. 5-38.
To solve the problem we need a procedure to move
n
disks from peg
i
to peg
j
.
When this procedure is called, by
−
towers(n, i, j)
the solution is printed out. The procedure first makes a test to see if
n
=
1. If so,
the solution is trivial, just move the one disk from
i
to
j
.If
n
1, the solution con-
sists of three parts as discussed above, each being a recursive procedure call.
The complete solution is shown in Fig. 5-39. The call
≠
towers(3, 1, 3)
