Results 1 to 2 of 2

Thread: Towers of Hanoi

  1. #1
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default 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. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,997
    Blog Entries
    7
    Rep Power
    19

    Default

    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.

Similar Threads

  1. Replies: 5
    Last Post: 04-28-2010, 04:42 PM
  2. Towers of Hanoi using Producer/Consumer Pattern
    By dooey in forum New To Java
    Replies: 0
    Last Post: 09-08-2009, 12:45 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
  •