遞歸求和堆棧溢出

我寫了一個Java遞歸方法來計算n從0到n的總和。這裏的代碼：遞歸求和堆棧溢出

private static long sum (long n) { 
    if (n == 0) { 
     return 0; 
    } else { 
     return n + sum(n-1); 
    } 
}

當我通過一個大的數字，如11000及以上，有時會發生堆棧溢出。是的，我有時會說。當n大於或等於11000時，程序運行並給出答案或堆棧溢出。

任何人都可以解釋發生了什麼？

2016-07-07 J.Doe

相關：[什麼是最大深度的Java調用堆棧？]（http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack ） –

請考慮使用[For-loop]（https://docs.oracle.com/javase/tutorial/java/nutsandbolts/for.html）。 –

@AlanTuning考慮使用'n *（n + 1）/ 2'代替:) –

考慮使用一個for循環，而不是

public static long sum(long n) { 
    long result = 0; 
    for (int i = 1; i <= n; i++) { 
     result += i; 
    } 
    return result; 
}

當然或者，你可以只用一個花哨的公式:)_{感謝@Andy特納}

public static long sum(long n) { 
    return n * (n + 1)/2; 
}

原因你得到一個StackOverflow異常是因爲你生成的調用堆棧比JVM所期望的要大。

2016-07-07 12:00:02

每次調用方法時，都需要在調用堆棧上爲該方法調用分配空間，以便存儲對局部變量和方法參數等的引用。

堆棧位於地址空間的頂部，從上到下分配。在地址空間的底部是堆，它從下到上分配。一旦處理完該方法，它就會從堆棧中彈出。

基本上你的方法會在每次調用時繼續在堆棧上分配內存，如果調用過多，堆棧最終會堆入堆中。此時，您試圖聲明已在使用的內存，並以堆棧溢出的形式出現分段錯誤。

這是爲什麼大多數時候通常不鼓勵遞歸實現的原因的一部分。

2016-07-07 12:35:26

回答