Tower of Hanoi Recursion Algorithm

Question

I am having a problem understanding this Tower of Hanoi recursion algorithm:

public class MainClass {
  public static void main(String[] args) {
    int nDisks = 3;
    doTowers(nDisks, 'A', 'B', 'C');
  }

  public static void doTowers(int topN, char from, char inter, char to) {
    if (topN == 1){
      System.out.println("Disk 1 from " + from + " to " + to);
    }else {
      doTowers(topN - 1, from, to, inter);
      System.out.println("Disk " + topN + " from " + from + " to " + to);
      doTowers(topN - 1, inter, from, to);
    }
  }
}

The output is:

Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

I don't understand how do we get:

Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A

Can someone please explain?

Thank you.

the key concept here is understanding the recursive calls changing the arguments... — gtgaxiola, Sep 18 '12 at 19:37
Yes, but I do understand how the Disk 1 from A to C Disk 2 from A to B came but somehow I am not able to understand from where did the Disk 1 from C to B come. Can you please explain me the flow? I would really appreciate it! — user564927, Sep 18 '12 at 19:39
Change `doTowers(nDisks, 'A', 'B', 'C');` to `doTowers(nDisks, 'Left', 'Right', 'Middle');` and see if that helps to visualize it. — Shmiddty, Sep 18 '12 at 19:46
Check this visualization http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html — gtgaxiola, Sep 18 '12 at 20:01
you should check out [this answer in - Tower of Hanoi: Recursive Algorithm](https://stackoverflow.com/a/58259294/7541700) — costargc, Oct 06 '19 at 17:44

Legna · Accepted Answer · 2021-08-16T17:33:03.383

9

Moving a N disks tower from peg A to C is achieved by moving a N-1 (all disks but the last one) tower from A to B, then moving the Nth disk from A to C, and finally moving the tower previously moved to B, from B to C. This shall be applied any time a tower with more than one disk is moved, in the case of a 1 disk tower, you just move its only disk.

edited Aug 16 '21 at 17:33

answered Dec 07 '12 at 22:41

Legna

1,632
15
15

score 0 · Answer 2 · answered Sep 18 '12 at 19:39

If I'm not mistaken you can move 1 disk one peg each turn correct? So you move the first disk from a to b then b to c. That is 2 moves. Then we can now move disk 2 from a to b. Now we can move disk 1 from c back to b. Right now disk 3 is on A and disk 2 and 1 are on a. Now we move disk 1 from a to b then to c. No we need to get disk 1 and 2 on disk 3 in the right order. So we clear disk 1 by moving it from B to A. This allows us to put disk 2 from B to C. Now we finish by moving disk 1 from a to b then to c and we are done.

Does that answer your question?

I understood the whole working.... but when i am trying to recursivly break it down all i get is Disk 1 from A to C Disk 2 from A to B ,Disk 2 from B to C Disk 1 from A to C. I am somehow not able to understand how the recursive function got Disk 1 from C to B Disk 3 from A to C Disk 1 from B to A :( — user564927, Sep 18 '12 at 19:53

Tower of Hanoi Recursion Algorithm

2 Answers2

Linked

Related