I'm struggling to comprehend the Java solution for the Towers of Hanoi problem. It's been challenging for me to grasp the logic behind the code implementation.

1

I have been facing considerable difficulty in comprehending the functioning of this program. Despite reading numerous articles, none of them provide a clear explanation of how the program operates. I will make an effort to articulate my questions as clearly as possible.

Therefore, my inquiry is regarding the operational mechanisms of this program.

// Java recursive program to solve tower of hanoi puzzle 

class GFG
{ 

    // Java recursive function to solve tower of hanoi puzzle 

     static void towerOfHanoi( int n,  char from_rod,  char to_rod,  char aux_rod)

    {

         if (n ==  1 ) 

         { 

             System.out.println( "Move disk 1 from rod " +  from_rod +  " to rod " + to_rod);

             return;

        } 

         towerOfHanoi(n- 1 , from_rod, aux_rod, to_rod); 

         System.out.println("Move disk "+ n +  " from rod " +  from_rod +  " to rod " + to_rod); 

         towerOfHanoi(n- 1 , aux_rod, to_rod, from_rod); 

     }

     

     //  Driver method 

     public static void main(String args[])

     { 

         int n =  4 ;  // Number of disks 

         towerOfHanoi(n,  'A' ,  'C' ,  'B' );  // A, B and C are names of rods 

   }

}

Extracted from an online article on exit interview questions resource.

I have a grasp on the initial call and the subsequent calls that occur after the return statement. However, what perplexes me is how this program is not encountering any errors. It almost appears like magic to me.

In the second call to the method, the arguments are presented in a different order compared to the method's definition. The method's definition states that the arguments are FROM, TO, and AUX, but the second call indicates FROM, AUX, and TOO.

Does this order of arguments affect the result, or is it irrelevant?

Additionally, there comes a point where the value of 'n' needs to revert to its original value; otherwise, the program would only be capable of moving a single disk. I am unable to locate any increment operation in the code. When I run the program through a debugger in my IDE with 3 disks, the value of 'n' sometimes transitions from 1 to 3, and I cannot comprehend how this occurs.

This problem is incredibly confusing, and I feel exhausted from reading articles that do not provide a comprehensive walkthrough of the code solution.

3

Recursive problems can be tricky, especially your first few. Here's a video that may help: Towers of Hanoi: A Complete Recursive Visualization - YouTube

1 Like
4

It's very relevant. The way that Hanoi works to move n disks from FROM to TO is

  • move the top n-1 disks from FROM to AUX
  • move the last disk from FROM to TO
  • move the top n-1 disks from AUX to TO

You see that the top disks follow a kind of two-step path, with an intermediate stop on AUX. This has the effect that the first recursion puts AUX in to the role of "where to move the disks to", whereas the second one puts AUX in the role of "where to love the disks from". This reassigning if roles of the rods/positions is essential and it's what the reordering the arguments that you observed can achieve.

In the bullet list above, you can verify that the descriptions correspond to the first 3 function arguments in your recursive calls.

// move the top n-1 disks from FROM to AUX
towerOfHanoi(n- 1 , from_rod, aux_rod, … 
// move the last disk from FROM to TO
"Move disk "+ n +  " from rod " +  from_rod +  " to rod " + to_rod
// move the top n-1 disks from AUX to TO
towerOfHanoi(n- 1 , aux_rod, to_rod, …

The last argument is just to let the function know which one the last remaining rod is.

The important insight about recursive programs is that there is more than just one variable called n. Calling recursively the towerOfHanoi function with n-1 does not modify the variable n. Instead it creates a new variable, within this recursive call, there also called n but which is set to be one lower than the original variable n. After the recursively called function finishes, the original n still exists.

It never changed its value, it never got decremented, but when you run a debugger this fact that all of those variables on different levels of recursive calls are all called by the same name could lead to the illusion of a single changing value n that decreases by writing n-1 and confusingly and magically increases again after a recursive call ends. This interpretation is absolutely wrong and would be a misinterpretation of what the debugger is trying to tell you - a confusion likely caused by the authors of debuggers just assuming that users are well familiar with how recursion works.

3 Likes
5

To elaborate a bit more about the debugger, at any given step you should be able to see how many levels of nesting there are, showing the various instances of n that exist for each function call. I don't know which debugger you're using, and I haven't programmed in java for some time, so you'll need to figure that part on your own.

6

Trying to find some existing visualization for how this works was slightly harder than expected, but ultimately I found this video which does a great job IMO

Obviously it's going through a simpler recursive algorithm than the Hanoi one, in particular there's only one recursive call, not two, so in the Hanoi algorithm the call stack would not only grow once and shrink back once, but instead grows and shrinks quite a few times, but I think it's important to clearly visualize how there can be different, separate variables, all called n, and each associated with a different function call of the same function, which all co-exist at the same time. (For Hanoi, the same thing of course applies not only to the variable n but just as well to all other variables, from_rod, to_rod, aux_rod.)

Edit: Now looking into computerphile, of course they do a good job, too. Uses factorial as an example, too

2 Likes
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.