The Tower of Hanoi: Recursion with Objects

The Tower of Hanoi is a classic game that is often emulated on computers to demonstrate recursion.

The game runs as follows. There are a number of discs each with a hole in the center. Each disc can fit on any of 3 pegs and each peg is high enough to hold all the discs in a stack. In the initial configuration all the discs are stacked on the first peg with the largest disc on the bottom and the smallest on top. A disc is never stacked on top of a smaller disc. The problem is to move the discs, one at a time from peg to peg in such a way that this is always true and to finally end up with all of the discs on peg 3 in the original order.

The solution is elegant. Let's call the three pegs A, B, and C. If you don't know how to move 5 discs from A to C (using B for intermediate storage), then just move 4 discs from A to B, one disk from A to C (this is really easy) and then move 4 discs from B to C. Can't do 4 discs? Well then, move just 3 ...

Guido's hanoi.py in the Python Demo area is a nice demonstration of this recursive process. The heart of the program is just this.

def hanoi(n, a, b, c, report):
   if n <= 0: return
   hanoi(n-1, a, c, b, report)
   report(n, a, b)
   hanoi(n-1, c, b, a, report)
-

The other 99% of the program involves doing TK graphics to make it come alive. Here is a screen shot of the game in progress.

And here is a javascript animation . Use browser back-button to return.

I have tried a couple of times to teach the Hanoi puzzle as a good example of recursion. It is much better than the usual factorial example which does nothing more than use recursion to replace a simple for loop.

But students have a hard time getting it. And I think the problem is the difficulty in visualizing the nested context of the recursive calls.

The recursion can be avoided, or at least made more intuitive by using an object oriented approach. Then the discs, as objects, can hold the information normally held in the call stack.

Lets think of the discs as being animated and that we can request one of them to move itself, along with all of the smaller brethen above it, to another peg.

We'll have each disc use the following strategy. If there is no smaller disc on top, simply move to the requested peg. But if there is, pass the buck. First ask the smaller disc above you to move to the alternate peg (along with its brethren above, if any), make your move, and finally ask the same disc to now move to your peg. When that is done, declare success. Each disc will need only to talk to the one just smaller

It might prove instructive to have the game played in a classroom with a different student playing the role of each disc. It might be a good idea to choose students by height to represent larger or smaller discs so that it is easy to see that the rules are being followed.

Have 3 lines (A,B,C) that the students can stand in and initially line them up on A, tallest to shortest. Finally ask the tallest student representing the largest disc to move to line C.

Each student must follow these instructions exactly. It's probably a good idea that each have their own copy and use a pencil to keep track of exactly where they are at all times.

If you are requested to move to another line then
  If no one is in front, move to that line and say "OK".
Otherwise
  Ask the person in front of you to move to the alternate line
    (not the one you will move to).
  Wait for that person to say "OK".
  Move to line you were requested to.
  Ask the same person to move to the line you are now on.
  Wait for that person to say "OK"
Say "OK"

Play this game with 1, 2, 3, and 4 players. How many total moves are made in each case?

How many moves would you expect for 5 players? 10 players?

The monks of Hanoi were said to play the game with 64 discs and when finished, the universe would end. How well does this jive with current cosmology? ;)

Here is a small python program that essentially follows the instructions above.

Click here to download tower.py .

 2 #
 3 #  t o w e r . p y
 4 #
 5 #  Copyright 2001 by Chris Meyers.
 6 #
 7 class disc :
 8     # create a disc, assigning it a name (so we can watch it better)
 9     # an initial peg, and a reference to the next smaller disc
10     # or the value None if this is to be the smallest disc
11
12     def __init__ (self, name, peg, nextSmaller) :
13         self.name = name
14         self.peg  = peg
15         self.nextSmaller = nextSmaller
16
17     # when asked to move to a new peg, find the alternate peg by starting
18     # with a list of all 3 and removing the 2 I can't use.
19     # then move everything above me to the alternate peg
20     # then move myself (change my peg value).
21     # Finally move the smaller pegs back on top of me
22
23     def move (self,newPeg) :
24         print(self.name + " : I have been requested to move to peg %s" %  newPeg)
25         if self.nextSmaller :
26             pegs = [1,2,3]           # find what has to be the alternate peg
27             pegs.remove(newPeg)      # can't be the one I'm going to
28             pegs.remove(self.peg)    # can't be the one we're on
29             altPeg = pegs[0]         # Ahh. That one.
30
31             print(self.name+" : Asking " + self.nextSmaller.name +
32                              " to get out of my way and move to peg %s" % altPeg)
33             self.nextSmaller.move(altPeg)
34
35             print(self.name + " : Moving to %s" % newPeg)
36             self.peg = newPeg
37
38             print(self.name + " : Asking " + self.nextSmaller.name +
39                                 " to rejoin me on peg %s" % self.peg)
40             self.nextSmaller.move(self.peg)
41         else :
42             # If I'm the smallest disc, life is very simple
43             print(self.name +  " : Moving to %s" % newPeg)
44             self.peg = newPeg
45
46 # Make 3 discs all on peg 1. 'A' is the largest and on the bottom
47
48 def test() :
49     c = disc("C",1, None)   # the smallest disc. No nextSmaller disc
50     b = disc("B",1, c)      # 2nd largest disc
51     a = disc("A",1, b)      # largest disc
52     a.move(3)               # Now move all the discs to peg 3
53
54 if __name__ == "__main__" : test()
55

Here is the output when we run it

$ python tower.py                                      # python3 also works
A : I have been requested to move to peg 3
A : Asking B to get out of my way and move to peg 2
B : I have been requested to move to peg 2
B : Asking C to get out of my way and move to peg 3
C : I have been requested to move to peg 3
C : Moving to 3
B : Moving to 2
B : Asking C to rejoin me on peg 2
C : I have been requested to move to peg 2
C : Moving to 2
A : Moving to 3
A : Asking B to rejoin me on peg 3
B : I have been requested to move to peg 3
B : Asking C to get out of my way and move to peg 1
C : I have been requested to move to peg 1
C : Moving to 1
B : Moving to 3
B : Asking C to rejoin me on peg 3
C : I have been requested to move to peg 3
C : Moving to 3

You can download this zip file for this project

If you have comments or suggestions You can email me at mail me

* * *