由遞歸函數引起的堆棧溢出

作爲C++編程和計算機系統體系結構的初學者，我仍然在學習C++的基礎知識。昨天，我讀到遞歸函數，所以我決定寫我自己，這是我寫的：（很基本的）由遞歸函數引起的堆棧溢出

int returnZero(int anyNumber) { 
    if(anyNumber == 0) 
     return 0; 
    else { 
     anyNumber--; 
     return returnZero(anyNumber); 
    }

}

當我這樣做：INT ZERO1 = returnZero（4793）;它會導致堆棧溢出，但是，如果將值4792作爲參數傳遞，則不會發生溢出。

任何想法爲什麼？

來源

2013-04-12 charles

也許更大的價值究竟是什麼需要使棧溢出？ – Listing

嘗試5000 - 它很可能會溢出堆棧。你的系統有多少內存？ – Silas

你問你爲什麼堆棧有特定的大小？ –

您剛剛觸及系統的調用堆棧的大小限制，就是發生了什麼。由於某些原因，系統中的堆棧很小，4793個函數調用的深度很小。

來源

2013-04-12 16:24:13

無論何時調用一個函數（包括遞歸），返回地址和參數通常會被推送到call stack上。堆棧是有限的，所以如果遞歸太深，你最終會用完堆棧空間。

令我驚訝的是，在您的機器上只需要4793次調用即可使堆棧溢出。這是一個非常小的堆棧。通過比較，在我的電腦上運行相同的代碼在程序崩潰之前需要多達100倍的調用次數。

堆棧的大小是可配置的。在Unix上，該命令是ulimit -s。

鑑於函數tail-recursive，某些編譯器可能能夠通過將遞歸調用轉化爲跳轉來優化遞歸調用。一些編譯器可能會進一步把你的例子：當問及最大的優化，gcc 4.7.2轉換整個功能分爲：

int returnZero(int anyNumber) { 
    return 0; 
}

這需要整整兩個彙編指令：

_returnZero: 
     xorl %eax, %eax 
     ret

整齊漂亮。

來源

2013-04-12 16:24:36 NPE

他說它適用於i = 4793，所以它應該適用於i = 4792 ...或者不適用？ – Fernando

@Fernando：他說4793失敗，4792工作。 – NPE

呃...他編輯或我醉了！謝謝！ – Fernando

您的堆棧尺寸有限，所以當您撥打4793來電時，您正在達到限值，而4792剛剛進入。每次函數調用都會在堆棧中使用一些空間來保存內容，也許會有參數。

該頁面給出了一個example在遞歸函數調用期間堆棧的樣子。

來源

2013-04-12 16:24:37

我的猜測是你的堆棧大到足以容納4792個條目 - 今天。明天或未來，這個數字可能會不同。遞歸編程可能是危險的，這個例子會導致病態。我們儘量不讓遞歸得到這種深度或「不好」的事情。

來源

2013-04-12 16:25:06

任何「無限」遞歸，即遞歸調用不會自然限制爲小（ish）數字，都會產生這種效果。具體到哪裏取決於操作系統，調用函數的環境（編譯器，哪個函數調用遞歸函數等）。

如果向調用遞歸函數的函數中添加另一個變量，例如int x[10];，則崩潰所需的數量將會更改（可能大約爲5個左右）。

使用不同的編譯器編譯它（或者甚至是不同的編譯器設置，例如開啓優化），它可能會再次改變。

來源

2013-04-12 16:29:07

使用遞歸，就可以實現SuperDigit：

public class SuperDigit 
{ 
    static int sum = 0; 

    int main() 
    { 
     int n = 8596854; 
     cout<<getSum(n); 
    } 

    int getSum(int n){ 
     sum=0; 
     while (n > 0) { 
      int rem; 
      rem = n % 10; 
      sum = sum + rem; 
      n = n/10; 
      getSum(n); 
     } 
     return sum; 
    } 
}

來源

2016-09-28 17:18:52

由遞歸函數引起的堆棧溢出

回答

相關問題