Trying to understand Hanoi algorithm using my own program

Question

I have the following working program for tower of Hanoi where we will move disks from A--B tower and C is the extra tower.I defined the initial state of the function as follows: moveDisks(n, 'A', 'B', 'C');

I will print each time I make a move using the following algorithm:

public static void moveDisks(
        int n,
        char fromTower,
        char toTower,
        char auxTower)
    {
        if (n == 1) // Stopping condition
            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);
        }
    }
}

As you can see from the recursive calls in my program, I have three possible calls:

    A--B--C //fromTower, toTower,auxTower
    A--C--B //fromTower, auxTower, toTower
    C--B--A //auxTower, toTower, fromTower

However, I'm getting the following printouts for 3 disks:

The moves are:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

I know my program is correct but I'm not really getting how it's doing B--C and C--A calls because I never made such function/method.I would appreciate if you can show how this recursive method is working in terms of three disks using my A--B--C, fromTower, toTower,auxTower model.

the debug saying me it's already running.How do I debug an already running program?@pjs — , Jun 19 '16 at 20:36
Since I have no idea which IDE you're using, I can't advise on that. Most debuggers will have a mechanism for setting breakpoints, and a way to step through your code line by line with the ability to inspect the variables. You're on your own for the details of doing so in your IDE. — pjs, Jun 19 '16 at 20:41
If you wrote that program, I can't believe that you don't understant how the tower names are interchanged. — , Jun 19 '16 at 20:49
So what's the surprise there are moves from A to C and C to B ??? — , Jun 19 '16 at 20:53
A--B--C //fromTower, toTower,auxTower A--C--B //fromTower, auxTower, toTower C--B--A //auxTower, toTower, fromTower — , Jun 19 '16 at 20:54
Mh, "Introduction to Java Programming, 20.7 Problem: Tower of Hanoi, p. 691." — , Jun 19 '16 at 20:55
I never said otherwise so how I'm getting them?Is there recursion for each of those that will continue separately? — , Jun 19 '16 at 20:55

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

I have figured out this myself at last.I can see that it's amazingly following binary tree structure, calling the left most child first(in this case a child is a print statement) in the recursion.

The mistake that I had in my understanding was that, I assumed A--B--C as from-to-aux for all recursive calls, although the from-to-aux variables have been changing throughout.So when I start with n=3 and A= from,B=to, C= aux, I get the following calls: moveDisks(2, 'A', 'C', 'B') and moveDisks(2, 'C', 'B', 'A').Now each of these recursive calls will independently start their own calls but for the first one now A=from, C=to, and B=aux and the second one C=from, B=to and A=aux.So for the first one I get moveDisks(1,'A','B','C') and moveDisks(1,'B','C','A') calls and the second one I get moveDisks(1,'C','A','B') and moveDisks(1,'A','B','C') calls.Recurssion continues till it reaches the stopping point.

Note: This is so amazing!I was learning recursion but ended up learning binary tree as well!

score 0 · Answer 2 · answered Jun 19 '16 at 20:00

You are considering the possible calls to moveDisks only from the perspective of the initial call:

moveDisks(.., 'A', 'B', 'C')

will call

moveDisks(.., 'A', 'C', 'B')
moveDisks(.., 'C', 'B', 'A')

but the recursion will continue for these calls and thus the next rounds of calls will be

moveDisks(.., 'A', 'B', 'C')
moveDisks(.., 'B', 'C', 'A')  --> moving B to C

and

moveDisks(.., 'C', 'A', 'B')
moveDisks(.., 'A', 'B', 'C')

...

Trying to understand Hanoi algorithm using my own program

2 Answers2