遞歸函數引起溢出，儘管它不是無限

-1

下面的函數我寫了導致程序崩潰是由於堆棧溢出，雖然遞歸是有限的。遞歸函數引起溢出，儘管它不是無限

public static void Key(char[] chars, int i, int l, string str) { 
    string newStr=null; 

    for(int j=0; j<l; j++) 
     newStr+=chars[i/(int)Math.Pow(68, j)%68]; 

    if(newStr==str) 
     return; 

    Key(chars, ++i, l, newStr); 
}

當我打電話與這些參數的方法，一切順利的罰款：

Key(chars, 0, 4, "aaaa");

但是，當涉及到呼叫的數量越大，它拋出StackOverflowException。所以我認爲問題在於方法是有限的，調用堆棧在方法的工作完成之前被填滿。所以我有幾個問題：

爲什麼函數不能從棧中清除，它們不再需要，它們不返回任何值。
如果是這樣，有沒有辦法我可以手動清除堆棧？我嘗試了StackTrace類，但在這種情況下它是無助的。

來源

2013-04-05 Nathan Abramov

我得到的印象很深刻，你不明白堆棧是什麼或它有什麼作用。請仔細研究，您的問題應該自行解答。 – asawyer 2013-04-05 18:46:44

從技術上講，你的代碼是尾遞歸的，如果你用c＃優化來構建它，你永遠不會有堆棧溢出，你應該只是得到一個無限循環（如果你的基本情況實際上永遠不會被打）。嘗試開啓優化，看看你是否仍然堆棧溢出 – devshorts 2013-04-05 18:50:09

也許你應該試圖描述你想要完成這個看起來真的不必要的過於複雜 – 2013-04-05 18:55:53

堆棧仍然有限。對於標準的C＃應用程序，它是1 MB。對於ASP，它是256 KB。如果你需要更多的堆棧空間，你會看到異常。

如果您自己創建線程，則可以使用此constructor來調整堆棧大小。

或者，你可以因此跟蹤狀態，而無需使用遞歸重寫你的算法。

來源

2013-04-05 18:47:01

當downvoting請求者發表評論。謝謝。 – 2013-04-05 19:49:15

它看起來像NewStr == Str的退出條件永遠不會發生，最終，您將用完堆棧。

來源

2013-04-05 18:48:58 Metaphor

爲什麼不會發生？當調用次數小於堆棧可以處理的調用次數時，它就會發生。 – 2013-04-05 18:51:36

@NathanAbramov針對可能輸入子集的算法並不能證明它適用於所有可能的輸入。 – 2013-04-05 18:54:08

我沒有看到問題，爲什麼它不能用於所有可能的輸入？（不管溢出問題） – 2013-04-05 18:57:15

1），當它已經結束執行的功能清除。在本身調用Key意味着每次調用它都會在堆棧中，直到最後一次調用結束，在這個階段它們將以相反的順序結束。

2）您不能清除棧和與呼叫矣。

來源

2013-04-05 18:52:17

所以，不管你的代碼是否達到其基本情況或沒有，你的代碼應該永遠不會在生產堆棧溢出異常。

例如，這應該給我們一個堆棧溢出嗎？

private static void Main(string[] args) 
{ 
    RecursorKey(0); 
} 

public static int RecursorKey(int val) 
{ 
    return RecursorKey(val ++); 
}

事實上，如果您使用.NET 4並且沒有進行調試，並且您的二進制文件被編譯爲發佈版，

這是因爲clr足夠聰明，可以做所謂的tail recursion。尾遞歸併不適用於任何地方，但就您的情況而言，我很容易就能夠重現您的確切問題。就你而言，每次調用函數時都會將另一個stack frame推入堆棧，因此即使該算法在理論上會在某個時間點結束，也會出現溢出。

要解決您的問題，here是您如何啓用優化。

但是，我應該指出，Jon Skeet建議不要依賴尾部調用優化。鑑於Jon是個聰明人，我會聽他的。如果您的代碼將遇到大堆棧深度，請嘗試重寫它而不遞歸。

來源

2013-04-05 19:06:49 devshorts

我試圖使用優化，但我不明白該怎麼做，當我檢查優化屬性它不會做任何事情。 – 2013-04-05 19:46:30

在發佈版本中在Visual Studio之外運行代碼。 – devshorts 2013-04-05 19:47:49

我做了，它不會工作 – 2013-04-06 08:09:03

遞歸函數引起溢出，儘管它不是無限

回答

相關問題