Another look at recursion

Towers of Hanoi

A normal (and highly recommendable) tactic in software development is to break down a problem into simpler sub-problems. Often such breakdowns result in the isolation of a set of quite dissimilar activities - having in common merely that they conspire to produce the desired outcome. Not infrequently, however, attempts at decomposing a task into sub-tasks reveal a much more restricted and interestingly interrelated set of constituent operations.

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:

  1. move the small disk from the source peg onto the spare peg (out of the way)
  2. move the large disk onto the target peg
  3. move the small disk back from the spare peg onto the target peg
As it stands, this account is clearly specific to a two-disk game. But to see the connection with the 'more difficult' cases, we need only slightly re-word our description of the procedure steps:
  1. move everything but the largest disk onto the spare peg (out of the way)
  2. move the largest disk onto the target peg
  3. move everything back from the spare peg onto the target peg
Now, obviously, since step 2 is straightforward, if we can find a way to handle steps 1 and 3 when there is more than one disk, the problem is solved. And here lies the interesting feature of the game. You need to notice that not only is step 2 the same as the simple game with one disk, but also that steps 1 and 3 are themselves no more than new versions of the general game but played with one less disk and with the source, target and spare pegs differently assigned.

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:

  1. If you have no disks to hanoi then stop playing
  2. hanoi all but the bottom disk from source to spare treating the original target as spare
  3. hanoi the bottom disk from source to target treating spare as spare
  4. hanoi the remaining disks from spare to target treating original source as spare
As it happens, this English breakdown of the strategy is a barely disguised Logo procedure definition:

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

ÿ