0

This is for the Tower of Hanoi solution as presented in Geeks for Geeks

I am really struggling to understand HOW is this working. I understand their main idea about breaking it down in "Simpler" operations, but I have no idea how the code itself is working.

// 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) 
        { 
1            if (n == 1) 
2            { 
3                System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod); 
4                return; 
5            } 
6            towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
7            System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod); 
8            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 
    } 
}

I'm adding those numbers to count the lines for easier reading.

First, the if statement in line 1. That should only execute when n == 1, and it should move the smallest disk from rod A to rod C. After that, line 2, it should return, signifying the end of the recursive method. The problem I have with this code is that moving the smallest disk from rod A to rod C is not only the final step to the algorithm, but also the first one. So how is the algorithm continuing when it's basically saying it should end in the first move?

My next questions are related to the other 2 recursive calls. After that if statement, the function is called again in line 6, but with n-1. So if n is 4, then it should call it with 3

But, what happens when it's called with 3? It should then go back to that if statement and since it's not 1, it should go back to line 6 and now call it with 2, which will continue until it's 1, executing the if block and leading out of the method

So how are the lines 7 and 8 being reached? How can this solution go back to higher numbers once it already decreased them? I mean, if n is 4 and becomes 3, how does it go back to 4 to rearrange that largest disk?

Edit: The suggested, related solution does not answer my specific questions. I already read through it and I'm still left with the same doubts.

Dasphillipbrau
  • 524
  • 2
  • 8
  • 17
  • No not really, that's a different piece of code. Furthermore they're not answering my specific questions. – Dasphillipbrau Feb 18 '20 at 05:34
  • The first disk in that base case may or may not be moving from A to C. Note the recursive calls switch the orders of the parameters. n won't start at 1, but at 4. It's only down to 1 3 levels of calls down from there. Your trace of n going down is correct, but the return leads out of that level of the method, not out of the ones who called it. – Jeremy Kahan Feb 18 '20 at 05:39
  • I wouldn't worry about the language, the algorithm is identical and there's a wealth of information in that thread. Us regurgitating it here won't really help you nearly as much since that thread has the last 10 years' worth of information on the topic here on SO. – ggorlen Feb 18 '20 at 05:43
  • I don't understand the last part of your answer. " but the return leads out of that level of the method, not out of the ones who called it" If I run this code, the first line printed is "Move disk 1 from rod A to rod C". The second line that get's printed is Move disk 2 from rod A to rod B. I have no idea how it got to this 2. How did it manage to increase n to 2 when it was previously 1? Is this return statement only leaving the if block and resuming execution at line 6? Then how would the recursion ever stop if return doesn't end it? – Dasphillipbrau Feb 18 '20 at 05:44
  • I already read through that question and I still don't understand. And I can't ask any further questions because it's a 10 years old thread. Nobody is still saying how is the call in line 8 being reached, or why is the result of printing line 7 is "moved disk 2" when n at that point should be 1 – Dasphillipbrau Feb 18 '20 at 05:57
  • @Dasphillipbrau take n=2 or 3. Run the program. You will get it. – Tarun Feb 18 '20 at 06:07
  • @Tarun I already did and I'm not getting it. Int = 3 I put a debugger on every step to see what is going on. The function calls itself recursively until it is 1, then it executes the if statement. Apparently the return statement doesn't end the method, it instead leads to line 7 (Why it doesn't start in line 6 is beyond me) where n is now 2. Then, there's the new function call where the rods are realigned, so that 1C can move to B since it's empty. After that it just gets even weirder...it jumps back to line 7 but n goes UP to 3, HOW does it go up to 3? There is no increment operation. – Dasphillipbrau Feb 18 '20 at 06:17
  • Also to add to my confusion: Why does it matter if the call on line 8 have the arguments in different order? There's no operation checking for the order of the rods, so I don't see how passing a "placeholder" in different order affects the order of the rods. – Dasphillipbrau Feb 18 '20 at 06:24
  • First, view [this video](https://www.youtube.com/watch?v=UsGls01AqCA) so you can see how the game is played. The best way to understand how this method works is to run it through your IDE's debugger and step through each code line. Place a debug **Breakpoint** on the first line of code to be run before the first recursive method is call, the `int n = 3;` code line. The arguments change in the recursive calls to the **towerOfHanoi()** method depending upon which pegs (of the three) it needs to work against. – DevilsHnd - 退職した Feb 18 '20 at 06:53
  • @Dasphillipbrau I think your problem is not this particular question but how recursion works in general. I would recommend you to watch some good videos on it online. You may searh on youtube "recursion nptel" – Tarun Feb 18 '20 at 07:16

0 Answers0