Consider, for example, the problem posed by the game The Towers of Hanoi. In the real world, the pieces of this game would typically be a wooden board with three upright pegs (A, B, C) arranged in a line along it and a collection of wooden disks, each with a hole in the centre, which can be dropped over the pegs to create stacks. The disks are all different in size. To start the game, some (or all) of the disks are chosen and they are stacked on one of the pegs, with the largest disk at the bottom and then progressively smaller ones, with the smallest at the top. One of the remaining pegs is then designated the target, and the problem is to transfer the disks onto that peg maintaining the arrangement, largest to smallest.

There is a catch, of course. Only one disk can be moved from one peg to another at a time and, although the spare peg can indeed be used as a temporary stopping place, no disk must ever be placed on top of a disk smaller than itself. Different attempts at the game can be compared and assigned scores in the obvious way: the fewer the moves, the better.

It is possible to solve this
problem by semi-systematic experimentation, i.e. by trial and error. A more
efficient technique can be found, however, by analysing and decomposing the task.
To achieve this, it is useful
to adopt another general-purpose strategy -* **focus first on the
simplest situations*. Now, the Hanoi game would be extremely simple (pointlessly
so as a real game) if we chose to play with only one disk. To succeed,
we would need to do no more than move that disk from its start peg to the target
peg. And on the face of it, a two-disk game offers scarcely more of a challenge.
But the solution of the two-disk game holds within it the germ of the technique
required to solve all
other cases. What are the steps involved? With two disks, the procedure reduces
to the following sub-tasks:

- move the small disk from the source peg onto the spare peg (out of the way)
- move the large disk onto the target peg
- move the small disk back from the spare peg onto the target peg

- move
*everything but the largest*disk onto the spare peg (out of the way) - move the
*largest*disk onto the target peg - move
*everything*back from the spare peg onto the target peg

Suppose we start with the situation illustrated above with four disks on peg A and we opt to move them to target peg B with peg C left spare. In this context, Step 1 is simply a new, scaled-down version of the game, requiring the movement of (the top) three disks from source peg A to target peg C leaving peg B spare.

Step 2 is the simple one-disk game, moving the bottom disk to the target B,

and step 3 is another small game moving (the same top) three disks from source peg C to target peg B leaving peg A spare.

If you now say: O.K
But how do you play the game with three disks?, the answer is essentially
the same. In steps 1 and
3 you play a game with two disks and in step 2 you play the one-disk game with
the bottom of the three disks . And to play a game with two disks? As you
know, you need in step 1 to play a one-disk game with the top disk (to get it out
of the way), you then play a one-disk game with the bottom disk - step 2 - to
put it on the target, and you lastly play another one-disk game - step 3 - with
the original top disk to get it back again from the spare to the target peg.
Playing the game, in other words,
always involves playing a smaller version of the game until you can make the
one and only real move - shifting one disk from the source to the target peg.

There
is, of course, another possible game situation which we have so
far not considered because we are sensible humans. How do you play Hanoi with
no disks? Forced to reply we would no doubt say that you do nothing, or to put
it slightly differently, you stop as soon as you start. Bearing that in mind,
we should perhaps extend the set
of component steps. (Let us ignore the possibility that an even crazier user
might try to play with a negative number of disks!) Suppose also, just for convenience,
we refer to playing the game as **to hanoi**. We now
end up with the following set of action modules:

- If you have no disks to
**hanoi**then**stop**playing -
**hanoi**all but the bottom disk from**source**to**spare**treating the original**target**as spare -
**hanoi**the bottom disk from**source**to**target**treating**spare**as spare -
**hanoi**the remaining disks from**spare**to**target**treating original**source**as spare

to hanoi :disks :source :target :spare if empty? :disks [stop] hanoi bf :disks :source :spare :target move first :disks :source :target hanoi bf :disks :spare :target :source end

The input **:disks** expects a list of disk
names - for example,** [disk1 disk2 disk3]** or **[red orange
yellow green blue indigo violet]**. The first of this list will be
the bottom disk and the last will be the top. The inputs **:source :target**
and **:spare****
**each expect a single (different) peg name, e.g **"peg1**,
**"green.peg**. Since the source, target
and spare pegs are identified in the **order** of the last three
inputs, the line:**hanoi bf :disks :source :spare :target****
**

has the effect of calling up a new version of **hanoi**
with the current spare peg designated as target (input 3) and
the current target peg as spare
(input 4).

To develop this primitive system so that it displays (e.g.
for a real player) the series of moves required to play the game successfully
with any number of disks, we merely have to define the auxiliary procedure **move**.

to move :disk :source :target (pr "move :disk "from :source "to :target) end

What is most
striking about the definition of the procedure **hanoi** is its apparent
circularity. It seems
as if, to know how to **hanoi**, you need to know how to **hanoi**.
The definition turns back on itself uncomfortably. But not forever.
In the last resort, when there are no disks left on top of the one we really
want to move, the instructions are direct enough. And what is perhaps as
great a surprise is the extreme simplicity of the move operation itself. A procedure
such as **hanoi**, with self-reference built into its definition
is known as recursive.
One of the most powerful features of Logo is its ability to handle
recursive procedures.

Ron Brasington

Department of Linguistic Science

The University of Reading

Reading

UK

E-mail: ron.brasington@rdg.ac.uk

ÿ