# Towers of Hanoi

• 07-11-2010, 07:02 PM
myst
Towers of Hanoi
Hi. I don't understand how Towers of Hanoi recursive algorithm works:

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???
• 07-11-2010, 07:24 PM
JosAH
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:

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:

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