Java遞歸方法StackOverflowError與整數對象

我一直試圖讓一個斐波那契數字返回者（給定一個輸入n返回索引位置n在斐波那契序列中的元素）。我試圖使它既是遞歸的，又具有低空間複雜性（我沒有實例化任何新的變量）。我使用Integer對象作爲值，儘管我知道它們的值溢出（它們返回負值），但這實際上是有意的（用於教育目的）。該函數稱爲smartestFib，因爲它比我的其他函數具有更低的空間複雜度。Java遞歸方法StackOverflowError與整數對象

當我調用130或更高版本的smartestFib（n）時出現問題。它工作得很好（考慮到溢出問題）爲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); 
    } 
}

我會很感激在這個問題上有所幫助，因爲問題的隨意性使我相信這是一些技術上的問題，我不知道，我不知道在哪裏看。非常感謝提前。

編輯：可能它是一個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); 
    } 
}

我不明白爲什麼這樣一個不會導致一個問題，我的新的做..

來源

2016-12-02 user3500869

這是一個[StackOverflowError]（http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror） – resueman

遞歸程序再次調用同樣的方法和增益（即工作，創造更多的&調用該方法的線程更多stackframes），並在達到默認堆棧大小後，您將獲得stackoverflowerror。

所以要解決這個問題，您需要通過傳遞-Xss作爲JVM參數來增加堆棧大小，您可以看看here。

我有其他功能，具有較高的空間複雜度，他們不是有這個問題。怎麼樣？

所以第一和第二方案之間的差異說明如下：

的區別是，一個使用拳擊（當你使用Integer類型goalNum變量），另一個使用原始int當你使用拳擊它導致性能問題，程序未能完成。

所以你goalNum變量從Integer類型更改爲int，然後它的工作原理（我測試）：

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

因此，要總結，總是避免不必要的裝箱/拆箱（從原語轉換爲包裝類，即，int到Integer），當你運行大量的計算時（比如在你的遞歸中）變得更加重要。您可以查看here以瞭解有關拳擊如何導致執行問題的更多信息。

來源

2016-12-02 19:39:34 developer

感謝您的評論，這真的很有幫助！但是對於那些基本上做同樣事情的程序我沒有這個問題，而且我對完全不同的地方完全無能爲力。你能看看我的其他代碼嗎？我編輯了主帖，這對我意味着很多。 – user3500869

堆棧溢出不是基於例程的空間複雜度;這意味着你已經使用了調用堆棧的空間。每個活動的函數調用都會佔用一些堆棧空間，跟蹤傳入和傳回的值，並經常切換上下文空間（寄存器值等）。

SmarterFib傳遞的整數（一個字）和陣列（一個字，通過引用;總存儲器使用是Ñ（goalnum）字加上幾個單詞的開銷）。這是總共2N單詞在堆棧上。

SmartestFib爲每個呼叫傳遞四個整數，或者在堆棧上傳遞4N 4個字。

通常我不會指望那些有嚴重不同的運行時棧要求：如果SmartestFib打擊了N = 130堆棧，我期望SmarterFib吹它N = 260（有一些好之前固定的通話費用）。

來源

2016-12-02 22:06:36 Prune

Java遞歸方法StackOverflowError與整數對象

回答

相關問題