javaでのアッカーマン関数

質問

今アルゴリズムの勉強をしていてkupc(2012:practice)のサイトにあったアッカーマン関数の問題を見てプログラムを作りました。
　下記が出来上がったものです。(m,n)=(2,3)であれば出力できましたが、入力例の2としてあった(3,45)はjava.lang.StackOverflowErrorとなりました。
　bigintegerや例外処理できないか考えていますがここから進めないので何か方法があれば教えてほしいです。
import java.util.Scanner;

public class AckermannExec {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.print("[m]>");
long m=scan.nextInt();
System.out.print("[n]>");
long n=scan.nextInt();

long a=Ackermann(m,n);
System.out.println("A(m,n)="+a);
}

public static long Ackermann(long m,long n){
if(m>=1&&n>=1){
return Ackermann(m-1,Ackermann(m,n-1));
}else if(n==0){
return Ackermann(m-1,1);
}else{
return n+1;
}

}

}

よろしくお願いします。

回答No.2

Picosoft · ベストアンサー

java.lang.StackOverFlowErrorは名前の通りスタックがオーバーフローした状態を表します。
変数の桁数は関係ないですから、
このエラーに関しては変数の型を変えても意味はありません。

関数を呼ぶと、引数の情報・関数から戻った後に実行する命令のアドレスが
スタックと呼ばれる領域に格納されます。
これらのデータは関数から戻るまで削除されないため、
再帰の階層が深くなりすぎるとスタックを使い切ってしまい、上述のエラーが発生します。

Java VMの設定でスタック領域を増やすといった対策も考えられますが、
アルゴリズムの勉強とのことですので、
再帰の階層が深くなりすぎないように工夫するのもおもしろいと思います。

回答No.3

salsberry

深い再帰呼び出しでStackOverflowErrorが出る場合は、javaの-Xssオプションでスタックを増やしてあげればStackOverflowErrorを出さずに実行を継続できるようになる場合があります。
しかしこの場合は無意味でしょう。
Ackermann(3,45)の再帰呼び出しの深さは約2の48乗になります。呼び出し1段で仮にスタックを64バイト消費するとすれば、2の54乗バイト(16ペタバイト)のメモリが必要になります。そんな大量のメモリを積めるコンピュータはありません。
再帰が深くならないように書き換えられればいいのですが、アッカーマン関数は再帰を使わない書き方が不可能であることが証明されています。

回答No.1

Tacosan

えぇっと, java.lang.StackOverflowError の理由は把握できてますか?

ちなみにこの問題, 「与えられた引数に対するアッカーマン関数の値」が計算できればいいんだよね.

補足

おっしゃる通りでアッカーマン関数の値が計算するのが目的です。

StackOverFlowは再帰的に行う計算量と桁数が大きくなりすぎてなっていると思っています。