優雅的方法來防止遞歸中的StackOverflow

我試圖端口this Genetic Algorithm, ，我做了一個遞歸函數從一代推進到另一代。但是，因爲我是C＃中的新遞歸（一般情況下），當代數太多（大約4500）時，我顯然遇到了StackOverflowException。優雅的方法來防止遞歸中的StackOverflow

爲了解決這個問題，我讓Generation（）返回一個bool，所以當遺傳算法達到最大適應度（目標）時，它會返回true。否則它返回Generation（）。

如果它即將溢出（代> 4500），則返回false。

Now在Main（）中，爲了使Generation（）繼續運行直到它返回true，我使用一個while循環，因此它將在遞歸開始之前一直運行，直到它完成。

這比做Task.Run更有效率，所以我採用了這種方法。

這是一個很好的做法嗎？有沒有更好的方法來防止StackOverflows而不犧牲性能？

Population.cs：

class Population 
{ 

    public int GenerationNumber { get; private set; } 
    public int TotalGenerationNumber { get; private set; } 
    public const int StackGenerationLimit = 4500; 

    public Population() 
    { 

     GenerationNumber = 0; 
     TotalGenerationNumber = 0; 


    } 
    public bool Generation() 
    { 
     // Work 
     // if(HasReachedGoal) return true; 

     GenerationNumber++; 


     if(GenerationNumber > StackGenerationLimit) 
     { 
      return false; 
     } else 
     { 
      return Generation(); 
     } 


    } 

    public void ResetStack() 
    { 
     TotalGenerationNumber += GenerationNumber; // I store the total number of generation for information purposes 
     GenerationNumber = 0; // Reset the recursion depth value 
    } 




}

Program.cs的

class Program 
{ 
    static void Main(string[] args) 
    { 
     Population population = new Population(); 

     while (!population.Generation()) // Until it reaches its goal 
     { 
      population.ResetStack(); 
     } 

     Console.WriteLine("End. Generations: " + population.TotalGenerationNumber); 


    } 
}

來源

2017-04-24 Nico de Ory

通常你不必保持遞歸方法運行 – EpicKip

如果你得到了一個stackoverflow的點，你應該考慮改變方法到一個非遞歸的方法。在這種情況下，它實際上非常簡單，因爲算法基本上是「配對生成，變異代，過濾器生成，重複」。聽起來更像是一個循環，而不是遞歸。事實上，這在性能方面比遞歸更好（如果正確實施）。 – Paul

避免堆棧溢出的最佳方法是不使用遞歸。您的解決方法已經解決了問題的一半。現在，您只需要問自己關於從遞歸獲得什麼的問題呢？如果Generation函數中的return Generation();語句改爲return false;，那麼您將返回到主循環，它將再次調用Generation()。

當然，做了這樣的改變，現在還有很多其他的整潔你可以做。您不再需要重置堆棧，您不再需要if語句來檢查生成限制，並且所有重複操作都是在while循環中完成的。

所以你的方法有兩種：

注意的是，在tidyup我推出了一個名爲hasCompleted，因爲我覺得它更具可讀性使用變量while條件，並希望有工作的一個布爾變量在循環內部。

來源

2017-04-24 15:03:59 Chris

這很有道理。謝謝！ –

我認爲在這種情況下，你會過得更好preping while循環，並在數據發送你想要檢查.Generation電話。那麼如果它返回false，則更新數據。類似這樣的：

Population population = new Population(); 
    var input = new InputDto() { ... }; 
    while (!population.Generation(input)) // Until it reaches its goal 
    { 
     // update input 
    }

這可以防止得到您所描述的錯誤的過深的嵌套調用。

來源

2017-04-24 15:02:50

優雅的方法來防止遞歸中的StackOverflow

回答

相關問題