Keep Получение ошибка Для 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)); 
    } 
} 

Heres ошибки я получаю:

Exception in thread "main" java.lang.StackOverflowError 
    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, но вы можете легко предотвратить StackOverflowError когда м < 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 или что-то подобное.