# Maudlin ruminations of a mind bit by wanderlust.

And a shaft of light shall sunder the heavens...

## The Towers of Hanoi, recursion, and the end of the world.

These are the towers of Hanoi :

The story goes that a bunch of monks in Vietnam were given 3 pegs and 64 golden discs, and had to move all of them from one peg to another, using the third as storage. However, they could never place a larger disc on top of a smaller one. The day they finished their task would be the end of the world, says the legend. That's quite ok with the most of us though, because if we assume that the monks can move one disc in one second, we can show that it will take them 584542046.09062564 millenia or thereabouts to finish the task. So unless they started a reeeally long time ago, the end of the world isn't going to happen any time soon. But that's assuming they know how to go about doing it. We can do better.

Recursion is a great tool for the lazy programmer. If it is easy to state the problem at hand in terms of the problem itself, then recursion is the way forward. Consider, that to solve the problem of hanoi,

-- We want to move all the discs from one peg to another (source to destination, with the other being called storage).
-- We can do this as follows :
-- If there are no discs on a peg, do nothing.
-- Move all but the last disc from the source peg to the storage peg using the destination as storage.
-- Move the last peg from source to destination.
-- Move all the discs you moved earlier to the destination, now that the largest disc is there.

Using this description, we can write :
```def transfer(discs, source, destination, storage) :
# If there is nothing to transfer, do nothing.
if discs == 0 :
return

# Transfer all but the last disc to the temporary storage location
transfer(discs - 1, source, storage, destination)

# Transfer the last disc to the destination
print "Moving disc %d from %s to %s" % (discs, source, destination)

# Transfer all but the last disc from the temporary storage to the
# destination
transfer(discs - 1, storage, destination, source)

def main() :
n = int(raw_input("Enter the number of discs : "))
source = 'A'
destination = 'B'
storage = 'C'
transfer(n, source, destination, storage)
```

Note that we start the process for n discs by calling,

`transfer(n, source, destination, storage)`

For 3, 4 & 5 discs, the moves are as follows :

```(sykora@nexus)(pts/3 | 0 job(s))(Thursday June 14, 2007 : 22:08:54)
(%:python)- python2.5 hanoi.py
Enter the number of discs : 3
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B

Enter the number of discs : 4
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B
Moving disc 3 from A to C
Moving disc 1 from B to A
Moving disc 2 from B to C
Moving disc 1 from A to C
Moving disc 4 from A to B
Moving disc 1 from C to B
Moving disc 2 from C to A
Moving disc 1 from B to A
Moving disc 3 from C to B
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B

Enter the number of discs : 5
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 4 from A to C
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 3 from B to C
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 5 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 3 from C to A
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 4 from C to B
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
```

Forgetting for the moment about the actual moves, and concentrating on the number of moves, we find :
```3 : 7
4 : 15
5 : 31
...
```

Notice a pattern? For 64 discs, the number of steps would be 2**64 - 1, which is 18446744073709551615. Taking this as a number of seconds we get the above mentioned number of millenia if the monks moved a disc a second.

What's the use? I'm told that a major use of this problem is to evalutate the pyschological stability of patients. Yes, that's apart from predicting the end of the world, and teaching recursion.

Robert Hurleyrfhurley Tuesday, June 19, 2007 3:49:07 PM

I'm very new to programming, so this rumination on the problem of recursion is interesting-- even if I don't fully understand it. I guess I would have to divide 2**64 - 1 by the number of calculations my computer can perform in a second to get some idea of how slow a recursion function would take to process (or something...)

So...

Judging by my comment, what's your assessmant of my pyschological stability?
};-)>

Sykora Skywavesykora Tuesday, June 19, 2007 4:46:56 PM

Judging by my comment, what's your assessmant of my pyschological stability?

Then again, I'd have to be sane myself to answer the question, so that's a dead end there.

The best way for you to find out how long the thing would take, would be to run it yourself. It's not that hard.

Robert Hurleyrfhurley Tuesday, June 19, 2007 4:50:21 PM

Have you tried running it? I'm afraid to-- slow computer...

Unregistered user Wednesday, June 20, 2007 11:30:50 AM

Harsh writes: Am not daring it either, n = 32 made a 700 MB incomplete output file o_O I got only a GB free, so I interrupt it :P I wonder if the terminal starts sucking up RAM/Swap for continuous output like this one ..

Sykora Skywavesykora Thursday, June 21, 2007 5:15:21 AM

Try running it for 4, 5, 6, 7 disks to about 15. Then you should have enough data to exponentially extrapolate it to 64.

However, if there's one thing I've learnt in python (actually, I've learnt a lot), it's that printing output to the screen continually significantly slows down the program itself. If you want to find the sum of the first million fibonacci numbers, add them yes, print them no. Just print the total. If you must have some kind of output in the middle, consider using sys.stdout.write() instead of print.

Unregistered user Sunday, December 9, 2007 5:15:55 AM

Anonymous writes: can you explain its implementation more in detail.

Unregistered user Monday, December 24, 2007 4:22:22 PM

Anonymous writes: can you deal with the same problem for 4 pegs?

### Write a comment

New comments have been disabled for this post.

December 2013
S M T W T F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31