I wrote this code to solve towers of hanoi. after 32453 iterations my code stops working

Question

import java.util.*;
class towers{
  public static void  main(String args[])
  {
       honoi('A','B','C',(long)1,n);
   }
  static int disk_no(long i,int n) // to find the next disk to move
   {
       if(i%2!=0)
           return 1;
       else
      {
          int j;
       long k;
       for(j=2;j<=n;j++)
             for(k=0;k<Math.pow(2,n-j);k++)
                  if(i==(long)Math.pow(2,(long)j-1)*((2*k)+1))
                  {
                     System.out.println("returning :"+j);
                     return j;
                  }
         return 0;
      }
      }
      static void honoi(char x,char y,char z,long i,int n)
      {
          if(i<Math.pow(2,n))
          {
             switch((int)i%2)
              {
                 case 0:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+z+" to "+y);
                             honoi(x,y,z,++i,n);break;
               default:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+x+" to "+y);
                              honoi(y,z,x,++i,n);
              }
           }
       }}

I read n value from user as number of disks ofcourse I skipped it here I thought that the problem is with disk_no() function if not mention the logical errors in the code if any

Try explaining the problem in details. For instance, After 32453 iterations what are the values of the local vars ? etc.. — OhadM, Nov 22 '15 at 10:39

score 2 · Accepted Answer · edited May 23 '17 at 11:59

The problem is that your code throws a StackOverflowError.

Essentially, your honoi method prints out all the moves necessary to solve the Towers of Hanoi puzzle with n disks from step i onwards. It does this by figuring out what is necessary for move i and then calling itself with i replaced with i + 1 and optionally with x, y and z switched around.

The problem arises because your method calls itself. Each time Java calls your honoi method, it needs to store where to return to when executing the method finishes. It stores these return locations on a 'stack'. When a method returns, Java removes the last of these locations from the top of the stack and resumes running your program from this location. There is only a limited amount of space for the 'stack' used for these return locations. If this stack grows too large, Java will throw a StackOverflowError.

If you run your program with a large number of disks, your code will require too much space to store return locations, because your method calls itself too many times before it returns. Your honoi method only returns once all of the moves have been displayed.

To avoid the stack overflow, I modified your honoi method to the following, which uses a loop instead of calling itself. i is now a loop variable, so I've removed i as a method parameter. You will need to remove the (long)1 from your call to honoi in main():

  static void honoi(char x,char y,char z,int n)
  {
      for (long i = 1; i < Math.pow(2,n); ++i)
      {
         switch((int)i%2)
          {
             case 0:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+z+" to "+y);
                 break;
             default:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+x+" to "+y);
                 char temp = x;
                 x = y;
                 y = z;
                 z = temp;
          }
      }
  }

The four lines from char temp = x; onwards swap around x, y, and z, as your recursive version of this method called itself with the x, y and z arguments switched around in the default case.

I don't know if you originally wrote this program in another language (e.g. a functional language such as Haskell) which supports tail recursion optimization. If a language supports this optimization, then it will be able to detect whether a method ends with a call to the same method, and if so, jump back to the start of the method using a kind of 'goto'. Your code would seem to benefit from this kind of optimization: if tail recursion optimization was supported in Java, your code would quite possibly run without an error. However, that's not likely to happen in Java.

I wrote this code to solve towers of hanoi. after 32453 iterations my code stops working

1 Answers1