javaackermann

Keep Getting Error For Ackermans Function


import java.util.Scanner;

//create AckermannsFunction class
public class Ackermann
{
   public static void main(String[] args) {

      //instance variables
      String input; //holds user input for the numbers
      int num1; //holds first number
      int num2; //holds second number

      //create new Scanner
      Scanner keyboard = new Scanner(System.in);

      do {
         //get first number from user
         System.out.println("Enter a number: ");
         input = keyboard.nextLine();
         num1 = Integer.parseInt(input);

         //get second number from user
         System.out.println("Enter another number: ");
         input = keyboard.nextLine();
         num2 = Integer.parseInt(input);

         System.out.println("Result: \n Ackermann: (" + num1 + "," + num2 + ") = " + ackermann(num1, num2));
      }

      //while(Integer.parseInt(input) != -1);
      while(num1 != -1 || num2 != -1);

      System.out.println("Bye!");
   }

   public static int ackermann(int m, int n) {
      //calculate if m = 0
      if(m == 0)
         return n + 1;
      if(n == 0)
         return ackermann(m - 1, 1);
      else
         return ackermann(m - 1, ackermann(m, n - 1));
   }
}

Heres the error I keep getting:

Exception in thread "main" java.lang.StackOverflowError
    at Ackermann.ackermann(Ackermann.java:44)

This goes on many times whenever I input -1 for first number and -1 for the second. I know it has to do with the while loop and have tried many ways to fix it but can't think of a better way to do so.


Solution

  • Your ackermann method's base case, which is responsible for terminating the recursion does not deal with numbers smaller than zero, so you keep going into the else clause infinitely, or until you run out of stack, whichever comes first....

      public static int ackermann(int m, int n) {
          if(m == 0)  <--nope
             return n + 1;
          if(n == 0) <--nope
             return ackermann(m - 1, 1);
          else
             return ackermann(m - 1, ackermann(m, n - 1)); <-- here we go again
       }
    

    I don't remember the precise definition of the ackermann function, but you could easily prevent the StackOverflowError when m < 0 with:

      public static int ackermann(int m, int n) {
          if(m <= 0)
             return n + 1;
          if(n == 0)
             return ackermann(m - 1, 1);
          else
             return ackermann(m - 1, ackermann(m, n - 1));
       }