爲Fibonacci序列避免堆棧溢出錯誤

-4

我最初解決了Project Euler問題＃2，它計算的斐波那契數列的偶數達到4,000,000。我完成了這一步，然後我想增加最大數目，以便它可以無限地繼續下去，從而產生更慢的計算結果，因爲計算時間更長。爲Fibonacci序列避免堆棧溢出錯誤

我得到了堆棧溢出錯誤，並想知道是否有代碼的替代解決方案，以便它能夠繼續運行，儘管緩慢，沒有遇到堆棧溢出錯誤。

有人可以幫助重構我的解決方案嗎？謝謝。

下面提供了此問題的相關代碼。

public static void main(String[] args) { 
    fibonacci(1,2,2); 
    } 

    private static void fibonacci(long first, long second, long sum) { 
     long number = first + second;  
     if (number % 2 == 0){ //Checks for even number 
      sum = sum + number; 
     } 
     System.out.println(sum); 
     fibonacci(second, number, sum); 
     // Produces the following error: 
     // Exception in thread "main" java.lang.StackOverflowError 
    }

來源

2016-04-27 Hiphop03199

http://stackoverflow.com/questions/849813/large-numbers-in-java –

不要使用遞歸，使用循環。 –

打破遞歸調用的基礎條件在哪裏？ – Gangaraju

你的問題是，你沒有停止遞歸的終止條件，你會一直持續下去，直到你的堆棧空間用完。

在僞代碼遞歸函數的一般格式爲：

return-typo function(some, values) 
{ 
    if(got to the end of recursion based on some values) 
    { 
    return something; 
    } 
    else 
    { 
    // Recurse 
    return function(changes to some values); 
    } 
}

注意：這不是一個硬性規定，只是一個大致輪廓。

來源

2016-04-27 14:24:39 Sean

謝謝，我不想看到有邊界條件，因爲我想無限計算。 – Hiphop03199

@ Hiphop03199 - 你無法無限計數如果沒有其他數據類型，'long'，會在某個點溢出。 – Sean

以下功能與您的代碼功能相同，只是沒有遞歸調用;正因爲如此，它會無限期地運行沒有StackOverflowError：

private static void fibonacci(long first, long second, long sum) { 
    while(true) { 
     long number = first + second;  
     if (number % 2 == 0){ //Checks for even number 
     sum = sum + number; 
     } 
     System.out.println(sum); 

     first = second; 
     second = number; 
    } 
    }

然而，正如其他人所指出的，它將運行字面上下去，因爲其中沒有打破循環。

來源

2016-04-27 14:26:09

除了它很快會達到一個數量太大而不適合長期。 – FredK

@FredK在哪個時候它會默默地溢出並繼續。 –

謝謝，我會放棄這一點 – Hiphop03199

這將計算斐波那契記憶2號

private static BigDecimal fibonacci(int n) { 

     BigDecimal cur = new BigDecimal(1); 
     BigDecimal prev = new BigDecimal(0); 

     //System.out.println(0+") "+1); 

     for (int i=1; i<n; i++) { 
      final BigDecimal next = cur.add(prev); 
      prev = cur; 
      cur = next; 
      //System.out.println(i+") "+next); 
     } 

     return cur; 
    }

來源

2016-04-27 14:26:16 Exceptyon

你有兩種選擇：

或者使用你的算法的迭代版本，例如像this
或增加您的堆棧大小當運行Java時，更多details

來源

2016-04-27 14:27:09 slayful

爲Fibonacci序列避免堆棧溢出錯誤

回答

相關問題