遞歸堆棧大小？

class Program 
{ 
    static void Main(string[] args) 
    { 
     Test(0); 
    } 

    static void Test(int i) 
    { 
     if (i > 30000) 
     { 
      return; 
     } 
     Test(i + 1); 
    } 
}

爲什麼在調用上面的示例時得到遞歸函數並引發StackOverflowException。遞歸堆棧大小？

（因爲在默認的遞歸堆棧大小？）

，但我不知道如何解決這個問題。

謝謝。

來源

2011-09-24 shenhengbin

[C＃遞歸深度 - 你有多深可以去]的可能重複（http://stackoverflow.com/questions/4513438/c-recursion-depth-how-deep-can-you-go）或[在C＃堆棧容量]（http://stackoverflow.com/questions/823724/stack-capacity-in-c） –

它運行良好！ http://ideone.com/pGZki –

你得到一個例外，因爲30000個堆棧幀是一個相當大的數量:-)

您通過以更謹慎的方式使用遞歸解決它。遞歸地解決的理想問題是那些可以快速減少「搜索空間」的問題^（a）。

例如，二叉樹的遍歷您的搜索空間每次減半你復發：

def find (searchkey, node): 
    if node = NULL: 
     return NULL 
    if searchkey = node.key: 
     return node 
    if searchkey < node.key: 
     return find (searchkey, node.left) 
    return find (searchkey, node.right)

增加兩個無符號整數（及以上自己的算法）是不很適合遞歸，因爲你「會吹出來的計算結果沒過多久，您的堆棧分配：

def add (a, b): 
    if a = 0: 
     return b 
    return add (a-1, b+1)

^（一）搜索空間可定義爲您的整套可能的答案。你想盡可能快地減少它。

而且，順便說一句，遞歸理想的問題無關，在理論上/數學意義上的堆棧空間，他們只是可以表示任何問題：

相同或與「更簡單」的論點類似的問題。
「最簡單」參數的終止條件。

（「簡單」，在這個意義上，意味着接近終止條件）。

理論/數學方法不需要考慮堆棧空間，但我們必須像計算機科學家一樣。現實限制:-)

另請參閱When would I not use recursion?和Situations where you would convert recursion to iteration。

來源

2011-09-24 23:23:48 paxdiablo

很好的答案！我學到了更多。謝謝 – shenhengbin

問題是你正在做太多的遞歸。無論你在做什麼，都會使用如此多的遞歸級別，應該使用循環來解決。

工作將使用遞歸的算法不會爲每個項目使用一個遞歸級別。通常情況下，您將每個級別的工作分爲兩半，因此30000個項目只需要15個遞歸級別。

來源

2011-09-24 23:23:10 Guffa

謝謝你的好回答！ – shenhengbin

你得到StackOverflowException，因爲你的堆棧在這些30k調用中的某處溢出到Test。沒有辦法'解決'問題，堆棧大小是有限的（而且很小）。你可以重新設計你的代碼以迭代的方式工作。

for(int i = 0; i <= 30000; ++i) 
{ 
    Test(i); 
}

但是，我認爲您的實際使用情況比這更復雜;否則遞歸沒有收益。

來源

2011-09-24 23:23:15

感謝您的回答！ – shenhengbin

看看這個問題：Way to go from recursion to iteration

如果你的遞歸將是30K +級深......你可能希望把它變成一個迭代算法。這個問題的答案應該有所幫助。

來源

2011-09-24 23:26:16 bobwienholt

感謝您的回答！ – shenhengbin

雖然你可以手動指定一個新線程的堆棧大小，我會使用一個Stack<T>或循環（這確實是您需要這個號碼簡化的例子都），所以你不需要遞歸所有，即：

Stack<int> stack = new Stack<int>(); 
stack.Push(1); 
while(stack.Count > 0) 
{ 
    int someValue = stack.Pop(); 
    //some calculation based on someValue 
    if(someValue < 30000) 
     stack.Push(someValue +1); 
}

來源

2011-09-24 23:27:18 BrokenGlass

感謝您的好樣品！ – shenhengbin

遞歸堆棧大小？

回答

相關問題