Javaの再帰メソッドIntegerオブジェクトのStackOverflowError

Question

フィボナッチ数リターンを作成しようとしています（入力nがfibonacciシーケンスのインデックス位置nにある要素を返す場合）。私はそれを再帰的にし、空間の複雑さを低くしようとしていました（私は新しい変数をインスタンス化しません）。私はIntegerオブジェクトを値として使用していますが、値のオーバーフロー（負の値を返す）を認識していますが、実際には意図的です（教育目的のため）。この関数はsmartestFibと呼ばれ、他の関数より空間の複雑さが低いためです。

smartestFib（n）を130以上呼び出すと問題が発生します。それは129以下のために完璧に（オーバーフローを考慮して）動作しますが、130以上の例外を与えます。主な問題は、例外が実際に何であるかを知ることができないことです。最初のエラーを見ることができないほど多くのエラーが表示されるため、エラーの内容を正確に知ることができません。私はエラーの種類を知らないので、私はそれをキャッチすることはできません。

私のコードは次のとおりです。

private static int smartestFib(Integer goalNum) 
{ 
    if (goalNum < 2) 
     return 1; 
    else 
     return smartestFib(goalNum-2, 0, 1,1); 
} 

private static int smartestFib(Integer goalNum, Integer currentNum, Integer lastValue, Integer beforeLastValue) 
{ 
    if (goalNum == currentNum) 
     return lastValue + beforeLastValue; 
    else 
    { 
     return smartestFib(goalNum, currentNum + 1, lastValue+beforeLastValue,lastValue); 
    } 
} 

問題の恣意性は、それが私が気づいていないよ、いくつかの技術的な問題であると信じて私をリードしているので、私は、この問題のいくつかの助けを本当に感謝して、私は見当もつかないどこを見るか。事前に多くの感謝。

編集：ApparantlyそれはStackOverflowError、ありがとうございます！しかし、今私は、 私は、より高い空間の複雑さと、他の機能を持っている、彼らはこの問題を抱えていないのだろうかと思います。どうやって？

private static int smarterFib(int goalNum) 
{ 
    assert (goalNum >= 0): "The variable goalNum may not negative."; 

    if (goalNum < 2) 
     return 1; 
    else 
    { 
     ArrayList<Integer> sequenceList = new ArrayList<Integer>(Arrays.asList(new Integer[] {1,1})); 
     return smarterFib(goalNum-2, sequenceList); 
    } 
} 

    private static int smarterFib(int goalNum, ArrayList<Integer> priorValues) 
{ 
    assert (goalNum >= 0): "The variable goalNum may not negative."; 
    assert (priorValues != null): "The array priorValues has not been initialized."; 

    if (goalNum <= priorValues.size()-2) 
     return (priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2)); 
    else 
    { 
     priorValues.add(priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2)); 
     return smarterFib(goalNum, priorValues); 
    } 
} 

この1つは問題にならないと、私の新しいものはありませんなぜ私は&多くを作成することによって、すなわち（もう一度同じメソッドを呼び出して、ゲインによって..

Answer 1

再帰プログラムの動作を確認することはできませんさらにそのメソッドを呼び出すスレッドによってstackframes）、デフォルトのスタックサイズに達した後にはstackoverflowerrorが得られます。

この問題を解決するには、-XssをJVM引数として渡すことによってスタックサイズを増やす必要があります。hereと表示されます。

私は他の機能を有しており、より高い空間の複雑さを有しており、これらはこの問題を抱えていません。 どうやって？

だから第一と第二のプログラムとの違いは、以下に説明する：

差が1でボクシングを使用していることです（あなたはgoalNum変数のIntegerタイプを使用する場合）と、他の一つは、プリミティブintとしたときに使用しますそれはパフォーマンスの問題を引き起こしているボクシングを使用し、プログラムは完了することに失敗しています。

（私がテストした）ので、intにIntegerタイプからあなたgoalNum変数を変更して、それが動作：

private static int smartestFib(int goalNum, int currentNum, 
    int lastValue, int beforeLastValue) { 
     System.out.println(goalNum); 
     if (goalNum == currentNum) 
      return lastValue + beforeLastValue; 
     else { 
      return smartestFib(goalNum, 
        currentNum + 1, lastValue+beforeLastValue,lastValue); 
     } 
} 

ので、ラッパー型すなわちにプリミティブからの変換（不要ボクシング/アンボクシングを避けるため、常に、要約します、〜Integer）これは、（再帰のような）広範な計算を実行しているときにさらに重要になります。あなたはボクシングがどのように問題を起こすかの主題についてもっと理解するためにhereを見ることができます。

Answer 2

スタックオーバーフローは、ルーチンの空間の複雑さに基づいていません。コールスタックのスペースで使用したことを意味します。すべてのアクティブな関数呼び出しは、前後に渡された値、そしてしばしばコンテクストスイッチング空間（レジスタ値など）を追跡しながら、いくらかのスタックスペースを占有します。 （;総メモリ使用がN（goalnum）単語プラス単語のカップルオーバーヘッドである基準によって1ワード）

SmarterFibは整数（1ワード）とアレイを通過します。これは合計で2Nの単語です。

SmartestFibは、各コールのための4つの整数、またはスタック上の4N単語を渡します。

私は通常、これらがひどく異なるランタイムスタックの要件を持って期待していない

：Nは= 260（いくつかありますかなり前SmartestFibは、N = 130でスタックを吹く場合、私はSmarterFibがそれを吹くことを期待したいです通話の固定オーバーヘッド）。