Продолжайте получать ошибку для функции Ackermans

Question

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));
   }
}

Вот ошибка, которую я продолжаю получать:

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

Это происходит много раз, когда я вводю -1 для первого числа и -1 для второго. Я знаю, что это связано с циклом while, и перепробовал много способов исправить это, но не могу придумать лучшего способа сделать это.

Answer 1

Ваш ackermann Базовый случай метода, который отвечает за завершение рекурсии, не имеет дело с числами, меньшими нуля, поэтому вы продолжаете бесконечно переходить к предложению else или до тех пор, пока не закончится стек, в зависимости от того, что произойдет раньше....

  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
   }

Я не помню точное определение ackermann функция, но вы могли бы легко предотвратить StackruError когда m < 0 с:

  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));
   }

Answer 2

1. Кстати, вы все равно получите ошибку переполнения стека для больших аргументов (m > 3 и n > 12 с размером стека по умолчанию), потому что даже для Ackermann(3,15) у нас есть 45811673828 вызовов функций, но для вычисления Ackermann(3,16) нам нужен максимальный размер стека> 10 мб
2. Ackermann(4,2) = 2^65536-3, поэтому типа int недостаточно для представления этого огромного числа (19 729 десятичных цифр). Вы можете использовать BigDecimal или что-то подобное.