CODEWITHSUNDEEP
javarecursion
Andrew
Andrew

Reputation: 13

Hanoi Tower recursion solution error

Professor shows us a recursive solution for Hanoi Tower problem:

public class Hanoi {

   static Stack<Integer> from;
   static Stack<Integer> temp;
   static Stack<Integer> to;

   public static void print() {
         System.out.println("------------------------");
         System.out.println(" FIRST " + from.toString());
         System.out.println("SECOND " + temp.toString());
         System.out.println(" THIRD " + to.toString());
   }

   public static void move(Stack<Integer> from, Stack<Integer> to) {
         to.push(from.pop());
         print();
   }

   public static void invokeHanoiLogic(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third, int quantity) {

         if(quantity > 0) {
                invokeHanoiLogic(first, third, second, quantity - 1);

                move(first, third);

                invokeHanoiLogic(second, first, third, quantity - 1);
         }

   }

   public static void main(String[] args) {
         from = new Stack<>();
         temp = new Stack<>();
         to = new Stack<>();

         from.push(3);
         from.push(2);
         from.push(1);

         invokeHanoiLogic(from, temp, to, from.size());
   }

}

But if we comment third string // invokeHanoiLogic(second, first, third, quantity - 1); to check first recursion depth result:

             if(quantity > 0) {
                invokeHanoiLogic(first, third, second, quantity - 1);

                move(first, third);

                //invokeHanoiLogic(second, first, third, quantity - 1);
         }

I found error at console log:

 ------------------------
FIRST [5, 4, 3, 2]
SECOND []
THIRD [1]
------------------------
FIRST [5, 4, 3]
SECOND [2]
THIRD [1]
------------------------
FIRST [5, 4]
SECOND [2]
THIRD [1, 3]
------------------------
FIRST [5]
SECOND [2, 4]
THIRD [1, 3]
------------------------
FIRST []
SECOND [2, 4]
THIRD [1, 3, 5]

But this solution is corresponds to a lot of examples at web. So, the question is : does any solution like this (that i found in the web) really contains error or my understanding of recursion is wrong?

Upvotes: 1

Views: 124

Answers (1)

Eran
Eran

Reputation: 393821

It makes sense that if you comment out part of a working algorithm, it will stop working.

The idea of the (correct) recursive implementation of Hanoi Tower is that if you have to move n elements from the first tower to the third tower, you first recursively move elements n-1 to 1 to the second tower, than you move the n'th element to the third tower and finally you recursively move elements n-1 to 1 to the third tower. If you skip the second recursive call, it simply doesn't work.

Upvotes: 1

Related Questions