How to call recursion with Tower of Hanoi

Question

I'm trying to resolve Tower of Hanoi problem; I wrote this code:

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, from, other);
         move(disks - 1, other, to);
         }
   }
}

but the result is wrong. The solution in my book is

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         move(disks - 1, from, other);
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, other, to);
         }
   }
}

why is this? I can't understand the ORDER of these expression:

• first it run System.out.println()
• then it run move(disks - 1, from, other)
• now it run System.out.println() again or run move(disks - 1, other, to)?

and WHEN RESTART the block code? Thanx.

Answer 1

The tower of hanoi works in a way that -:

1. First you have to move n - 1 disks to the 2nd peg from 1st using 3.
2. Move the last nth disk to 3rd peg.
3. Move the n-1 disks from 2nd peg to peg 3rd peg using 1st.

The book solution is correct in. Your solution is wrong because you have moved the last disk in the beginning, this is against rule of tower of hanoi. I hope you get it.

A bit more elegant and understandable code after some modification where it works for any arbitary n. (Atleast for small values of n due to it exponential complexity)

public class TowersOfHanoi {
   public static void main(String[] args) {
      int first = 1, second = 2, third = 3;
      int disk = 5; // or take user input
      move(disk, first, third);
   }

   public static void move(int disks, int first, int second, int third) {
      if (disks > 0) {
              move(disks - 1, first, third, second); // source = first, dest = second
              System.out.println("Move disk from peg " + first+ " to " + third);
              move(disks - 1, second, first, third);  // source = second, dest = third
         }
   }
}