C++中遞歸調用的最大數量級的數量級是多少？

Question

我有一個遞歸函數，它在給定某些輸入時調用自己很多次 - 這正是它應該做的。我知道我的函數並不是無限循環的 - 它只會達到一定數量的調用和溢出。我想知道在堆棧中放置太多內存還是一個問題，或者只是一個正常的調用數量限制。很顯然，很難說具體的最大呼叫次數，但任何人都可以粗略地估計一下數量級？它在成千上萬嗎？數百？百萬？

Answer 1

它完全取決於你在堆棧上使用多少信息。但是，Windows上的默認堆棧爲1MB，而Unix上的默認堆棧爲8MB。簡單地打一個電話可能需要推送幾個32位寄存器和一個返回地址，例如，你可能會看到一個電話可能有20bytes，這將使Windows的最大值約爲50k，而Unix上的最大值爲400k--這是一個空函數。

當然，據我所知，您可以更改堆棧大小。

Answer 2

您的一個選擇可能是更改/增加默認堆棧大小。這裏有一種方法http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.80).aspx

Answer 3

所以，正如你所猜測的，問題是（同名）堆棧溢出。每次通話都需要設置一個新的堆棧幀，將新的信息推送到堆棧上;堆棧大小是固定的，並最終用完。

什麼設置堆棧大小？這是編譯器的一個屬性 - 也就是說，它對二進制可執行文件是固定的。在微軟的編譯器中（在VS2010中使用）它默認爲1兆字節，你可以在編譯器選項中用「/ F」覆蓋它（關於'03例子，請參見here，但語法相同）。

很難弄清楚在實際中有多少個呼叫等同。函數的堆棧大小取決於它的局部變量，返回地址的大小，以及參數如何傳遞（有些可能會在堆棧中），而且大部分依賴於體系結構。一般來說，你可能會認爲後兩者小於一百字節（這是一個總估計）。前者取決於你在功能上做了什麼。如果您認爲函數需要比如256個字節的堆棧，那麼在1M堆棧中，您將在溢出之前獲得4096個函數調用 - 但這並不考慮主函數的開銷等。

您可以嘗試減少局部變量和參數開銷，但真正的解決方案是Tail Call Optimization，其中編譯器在調用遞歸函數時釋放調用函數。你可以閱讀關於在MSVC here中做更多的事情。如果你不能調用tail函數，並且你不能減小你的堆棧大小，那麼你可以用「/ F」參數來查看堆棧大小，或者（首選的解決方案）看一下重新設計。

Answer 4

有工具可以測量堆棧使用情況。他們預先用特定的字節模式填充堆棧，然後查看它改變的地址。通過這些，你可以發現你有多接近極限。

也許valgrind工具可以做到這一點。

Answer 5

遞歸函數使用的堆棧空間量取決於遞歸的深度和每個調用使用的內存空間量。

遞歸的深度指的是在任何給定時刻活動的級數。例如，二叉樹可能有一百萬個節點，但如果平衡良好，則可以不超過20個同時活動呼叫來遍歷它。如果平衡不好，最大深度可能會更大。

每次調用使用的內存量取決於在遞歸函數中聲明的變量的總大小。

遞歸的最大深度沒有固定的限制;如果您的總使用量超過系統強加的堆棧限制，則會發生堆棧溢出。

您可以通過某種方式減少遞歸的深度，也許可以通過重構任何它正在遍歷的內容（您沒有多告訴我們這些內容），或者通過減少在遞歸函數中聲明的任何本地對象（請注意，堆分配的對象不會影響堆棧大小），或者兩者的某種組合。

正如其他人所說的，您可能會增加您允許的堆棧大小，但這可能只是有限的使用 - 而且這是在運行程序之前必須做的額外事情。它也可能消耗資源並干擾系統上的其他進程（由於某種原因限制）。

更改算法以避免遞歸可能是一種可能性，但我們再次沒有足夠的信息來說明這一點。