The Towers of Hanoi puzzle tasks us with moving N disks from peg 1 to peg 3. We can only move one disk at a time, and that disc must be the top disk.
We cannot place a larger disk on top of a smaller disk.
Remember "... 55 minutes thinking about the problem..."
If you come up with an iterative solution, you will find that the pattern is different whether there are an odd or even number of
starting disks. For this article, we are only concerned with the recursive solution.
The pattern which you need to recognize is not as straightforward as our previous recursion examples.
When we study a problem, it sometimes helps to see the solution first and then figure out how it works (kind of like reverse engineering). In the entry box below,
entering 3 and view the solution.
Until now, all of our recursive functions pushed everything onto the stack before anything was popped off.
The next thing to notice it the aux peg holds each of the three positions in the three function calls.
Get your coins out and I will try to walk you through the recursive thinking process in solving this problem recursively.
Moves will appear here *8 disks max
Recursive algorithm
Recall that we 'Always, Always, Always' start with an algorithm. Whether you devise the algorithm yourself or are supplied one, turning
the algorithm into usable code may not be easy.
Recall that we 'Always, Always, Always' start with an algorithm. Whether you devise the algorithm yourself or are supplied one, turning
the algorithm into usable code may not be easy. Also recall that our objective is to practice thinking recursively.
Start by making a model. Get 4 coins: a quarter, a nickel, a penny and a dime, and 3 labels: src, aux, dst.
Recursion is all about recognizing a problem in terms of smaller versions of the same problem.
When solving your Coin-version, you will find that in order to move the quarter from src to dst, all of the other coins (not just N-1) will
have to be on the aux peg.
Place your model in that state where the nickel, penny, and dime are on the aux peg. Now you can move the quarter.
Take the quarter out of the game. Now we have a new game. A smaller version of the same game except our disks are on the aux peg.
To fix that, we simply rename our pegs!
You need to visualize that, in each smaller version of the problem, all of the other disks will need to be on the auxillary
peg before we can move our large disk to the final destination.
Each peg is sometimes used as the auxillary peg.
To move n discs from src to dst:
function hanoi(disc, src, aux, dst) //the initial call
First move N-1 disks from src to aux.
hanoi(disc - 1, src, dst, aux); //each function call means to first do this
Move disk n from src to dst.
hanoisol +=('Move disc '+disc+' from '+src+' to '+dst);//print the move
Move N-1 discs from aux to dst.
hanoi(disc - 1, aux, src, dst);//but first do this
Carnegie Mellon University has a nice TOH implementation which can help you visualize the
problem and solution. However, they use the center peg as their destination.
Remember that each function call pushes that operation onto the stack, and each move, will pop the stack.
Using your coin model, make an additional set of labels or a diagram to see how each of the arguments will change as they go into the parameters of the
function hanoi(disc, src, aux, dst). Then you can see how the code matches the algorithm.
Analogy
"Teaching recursion with the factorial example and assigning the Towers of Hanoi as an exercise is like showing someone how to build a birdhouse and
assigning them to build the White House."- R. Deveau.
Don't worry, it gets much worse. Next up is Fractals or Return to home page.
