1. Member
Join Date
May 2010
Posts
44
Rep Power
0

## Towers of Hanoi

Hi. I don't understand how Towers of Hanoi recursive algorithm works:

Java Code:
void move (int height, int fromPeg, int toPeg, int usingPeg){
// recursive procedure for determining moves
// Keep this order - from, to, using - in mind when you read the recursive calls
if (height == 1)
System.out.println ("Move a disk from" + frontPeg + "to" + toPeg);
else{
move(height-1, fromPeg, usingPeg, toPeg);
System.out.println ("Move a disk from" + frontPeg + "to" + toPeg);
move(height-1, usingPeg, toPeg, fromPeg);
}
}
I don't understand how this works recursively...

Attempt:

let's say height=3, fromPeg=1, usingPeg=2, toPeg=3

if (height = 1) ---- false
* move(2, 1, 3, 2) ---- (if height = 1) ---- false
**move(1, 1,3,2) ----- (if height = 1) ---- true
S.o.p ("Move a disk from 1 to 3 (or 2, not sure which toPeg it's referring to...)

but once height = 1, how does it return to the other method calls that were false?? and how does it perform the last two lines of the "else" which includes another method call???

2. I think my old "schizophrenic" example applies again here. Suppose there's me, the big mouthed guy that claims he can solve any Hanoi Tower problem and there's my friend, shy, silent, but highly intelligent who can actually do that. Also suppose you give me a Hanoi Tower problem of size n. I can only do the simple stuff; there are three locations, A, B, and C and you want the tower to be moved from A to C. I keep the largest disk and ask my clever friend to move all but this largest disk to move it from location A to B; then I move the largest disk from location A to C and ask my friend again to move his tower from B to C (he moved it from A to B so he should be able to move it from B to C). Here's the code:

Java Code:
void me(int n, int from, int to, int spare) {
if (n > 0) {
friend(n-1, from, spare, to);
System.out.println("from: "+from+" to: "+to);
friend(n-1, spare, to, from);
}
}
As you can see I took my precautions: if n == 0 there are no disks to move; otherwise I ask my friend to do the hard work, I move the largest disk and ask my friend to do the hard work again.

Here's the sad part: I am schizophrenic and I don't have a friend; that friend is me, so the actual code looks like this:

Java Code:
void me(int n, int from, int to, int spare) {
if (n > 0) {
me(n-1, from, spare, to);
System.out.println("from: "+from+" to: "+to);
me(n-1, spare, to, from);
}
}
Any sensible person doesn't name this method 'me' but 'hanoi' or similar ...

kind regards,

Jos
Last edited by JosAH; 07-11-2010 at 06:30 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•