Anyone has truly understood the Tower of Hanoi problem's solution using recursion?

[shivajikobardan]

package com.example.demo;

public class TowerOfHanoi {
    public static void main(String[] args) {
        moveDisks(4, 'A', 'B', 'C');
    }

    public static void moveDisks(int n, char fromTower, char toTower, char auxTower) {
        if (n == 1)
            System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);
        else {
            moveDisks(n - 1, fromTower, auxTower, toTower);
            System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);
            moveDisks(n - 1, auxTower, toTower, fromTower);
        }
    }
}

This is a java code to solve TOH problem using recursion. Although I can trace it. There is no way I can seem to be able to cement and internalize that learnings.

I watched this video for some intuition. It helped a bit i must say, but I am still confused how this entire solution even works. Why this works?

 

[Dr.Peterson]

What part of it confuses you? Why do you think it might not work?

 

[blamocur]

Recursion does take some getting used to, at least it did in my case when I was starting as a programmer.

I did not watch the video, but I can suggest one way of interpreting the code: You have to solve the problem for 'n' disks, and you have an assistant who can solve it for 'n-1' disks. If n==1 you don't need any assistance, but for larger 'n' you:

1. ask you assistant to move 'n-1' disks from 'fromTower' to 'auxTower'
2. move 1 disk from 'fromTower' to 'toTower'
3. ask the assistant to move 'n-1' disks from 'auxTower' to 'toTower

You can visualize a whole stack of assistants with you (in charge of 'n') at the top, and 'n-1', 'n-2', and so on all the way to the assistant 2 at the bottom.
Does this make it any clearer?

 

[Dr.Peterson]

Recursion does take some getting used to, at least it did in my case when I was starting as a programmer.

I did not watch the video, but I can suggest one way of interpreting the code: You have to solve the problem for 'n' disks, and you have an assistant who can solve it for 'n-1' disks. If n==1 you don't need any assistance, but for larger 'n' you:

1. ask you assistant to move 'n-1' disks from 'fromTower' to 'auxTower'
2. move 1 disk from 'fromTower' to 'toTower'
3. ask the assistant to move 'n-1' disks from 'auxTower' to 'toTower

You can visualize a whole stack of assistants with you (in charge of 'n') at the top, and 'n-1', 'n-2', and so on all the way to the assistant 2 at the bottom.
Does this make it any clearer?

... and now you are the assistant who knows how to handle n disks, so you can help the next guy who needs to do n+1!

(Or, since you now know the secret, you can just do it all yourself.)