java - フィボナッチの再帰呼び出しによるスタック オーバーフロー

Question

Javaスタックはどのように設定されていますか?

大学では、再帰的な方法で計算され、スタックで処理できる最大のフィボナッチ数を決定します。

興味深いのは、-XmxJVMがどれだけ持っているかは問題ではないことがテストで示されたということです。Fib(4438) まで実行できます。しかし、結果は一貫していません。4436 まで下がることもあります。-Xms

スタックの公式はありますか？

スタック ビアを増やして-Xss 4096mも違いはありません。

Answer 1

あなたは割り当てを誤解しました。スタックサイズはほとんど問題になりません。問題は指数関数的です。また、単純な再帰プログラムで Fib(4438) に到達することはできません。次のコードを使用すると、Fib(50) に到達できれば幸運です。

public static BigInteger f(int n) {
    if (n == 0) 
        return BigInteger.ZERO; 
    if (n == 1) 
        return BigInteger.ONE; 
    return f(n-1).add(f(n-2));
}

Answer 2

-Xmx および -Xms は、JVMヒープにアクセス可能なメモリを設定します。スタックサイズを増やす必要があります。これは、-Xss オプションを使用して行います。

Answer 3

ジャバ。プログラミング方法、第 9 版、Deitel および Deitel、771 ページ:

 // Fig. 18.5: FibonacciCalculator.java
 // Recursive Fibonacci method.
 import java.math.BigInteger;
 public class FibonacciCalculator
 {
     private static BigInteger TWO = BigInteger.valueOf( 2 );


     // Recursive declaration of method fibonacci
     public static BigInteger fibonacci( BigInteger number )
     {
         if ( number.equals( BigInteger.ZERO ) ||
              number.equals( BigInteger.ONE ) ) // Base cases
             return number;
         else // Recursion step
             return fibonacci( number.subtract( BigInteger.ONE ) ).add(
         fibonacci( number.subtract( TWO ) ) );
     } // end method fibonacci


     // Displays the Fibonacci values from 0-40
     public static void main( String[] args )
     {
         for ( int counter = 0; counter <= 40; counter++ )
             System.out.printf( "Fibonacci of %d is: %d\n", counter,
         fibonacci( BigInteger.valueOf(counter)));
     } // End main()

 } // end class FibonacciCalculator

これが役立つことを願っています。