I really don't understand the Java solution to Towers of Hanoi

1

I’ve been really struggling to grasp how this program works.
I’ve read a lot of articles and I still can’t understand, none actually refer to how the program works. I’ll really try to make my questions as clear as possible.

So this is the 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 

   }

}

Taken from Geeksforgeeks article on the solution

OK so, I understand the initial call. And I understand that after the return statement, the other calls occur.

What I don’t understand is how is this program not failing? It seems almost like magic to me.
The 2nd call to the method says that its arguments are in a different order from the method’s definition. The method’s definition states that the arguments are FROM, TO and AUX, but the 2nd call says they’re FROM, AUX and TOO.

Is this order affecting the result? Or is the order irrelevant?

Also at one point, the n needs to go back to being its original value, otherwise the program would be unable to move any disk asides from 1. How is this happening? I don’t see any increment operation there. If I run the program through a debugger on my IDE using 3 discs, the value of n sometimes simply goes from 1 to 3 and I have no idea how that can be happening.

It’s a very confusing problem and I’m really tired about reading articles, because none of them actually try to walk you through the code solution.

2

How familiar are you with recursion?

3

This is in a different language, but I thought this video did a really good job of explaining what’s going on in the recursive solution to the Towers of Hanoi.

4

I understand what recursion is. I know that the function calls itself and that the if statement is a base case, which every recursive function should have.

What I don’t understand is how Java is calling these functions and getting the desired results, its absolutely wild for me. I have no idea how is the n = 1 going back to being n = 3, or what is the effect of changing the order of the REFERENCE to the parameters.

5

I think that you’re misunderstanding variable scope. If I call myFunc(myVar), whatever I pass in as the first argument is assigned to myVar for that instance of myFunc().

In this case, the code above, or generally any recursive code, works because the same function is called again with a variation of the original arguments.

6

So in this case, there are 2 function calls inside of the function.

Are you saying that if I pass 3 to the initial function (not the 2 extra ones inside it), the 2 functions inside

**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);**

Are added to a sort of “execution stack”? Where they will be invoked even if the return statement above them is executed?

So essentially, the first one which says n-1, that one gets 2 as its n, whereas the next line which says print n gets 3? (because its only getting the value of the original call)
Then the next call (the last one) also gets 2?

I guess the biggest problem I have is understanding how are these functions called.

It says that the first thing it should do if n != 1 is call the function again but with n-1, but then, this would go on until n IS 1 and it would execute the if statement, including the return, so shouldn’t that mean that the function is over? If return doesn’t mean the function is over, and it instead moves to execute the next function, how will the function ever stop if apparently leaving the base case leads to another execution?

7

I’ve edited your post for readability. When you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read. It was a pain to edit your code.

See this post to find the backtick on your keyboard. The “preformatted text” tool in the editor (</>) will also add backticks around text.

Note: Backticks are not single quotes.

markdown_Forums

8

With recursion, broadly speaking, you are either in the base case or not in the base case.

If you are in the base case, you execute a simple behavior and return.

If you are not in the base case, the function calls itself again with a modified version of the inputs. The function then does a little bit of code before returning.

Try running this code:

function recursionTalks(n) {
  console.log("\nFunction call recursionTalks(): n = " + String(n))

  if (n < 1) {
    console.log("I am the base case!\n")
    return
  } else {
    console.log("Calling the next case: n-1 = " + String((n-1)))
    recursionTalks(n-1)
    console.log("Returned from  next case: n-1 = " + String((n-1)))

    console.log("Returning from case: n = " + String(n) + "\n")
    return
  }
}

recursionTalks(3)