在递归中防止 StackOverflow 的优雅方法

Question

我正在尝试移植 this Genetic Algorithm，我做了一个递归函数，用于从一代推进到另一代。

但是，由于我是 C# 中递归的新手（一般来说），当代数过多（超过 4500 左右）时，我显然遇到了 WhosebugException。

为了解决这个问题，我将 Generation() return 设为 bool，因此当遗传算法达到最大适应度（目标）时，它 return 为真。否则它 returns Generation().

如果即将溢出（代 > 4500），则 return 为假。

现在在 Main() 中，为了保持 Generation() 运行直到它 return 为真，我使用了一个 while 循环，因此它将重新开始递归直到它完成。

这比 Task.Run 更有效，所以我采用了这种方法。

这是好的做法吗？在不牺牲性能的情况下，是否有更优雅的方法来防止 Whosebugs？

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);


    }
}

Answer 1

我认为在这种情况下，您最好准备 while 循环并将要检查的数据发送到 .Generation 调用中。然后，如果它 returns 为假，则更新数据。像这样：

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

这可以防止出现您所描述的错误的嵌套太深的调用。

Answer 2

避免堆栈溢出的最好方法是不使用递归。您的解决方法已经完成了一半。现在你只需要问自己一个问题，你从递归中得到了什么？如果 Generation 函数中的 return Generation(); 语句改为 return false;，那么您将返回到主循环，它会再次调用 Generation()。

当然，进行此更改后，您现在可以进行许多其他整理工作。您不再需要重置堆栈，不再需要检查生成限制的 if 语句，并且所有重复都在 while 循环中完成。

所以你的两种方法：

public bool Generation()
{
    TotalGenerationNumber++;
    // Work
    return HasReachedGoal;
}

static void Main(string[] args)
{
    Population population = new Population();
    bool hasCompleted = false;
    while (!hasCompleted) // Until it reaches its goal
    {
        hasCompleted = population.Generation();
    }

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

请注意，在 tidyup 中我引入了一个名为 hasCompleted 的 bool 变量，因为我发现将变量用于 while 条件更具可读性并且更喜欢在循环本身内部进行工作。

在递归中防止 StackOverflow 的优雅方法

Elegant way to prevent StackOverflow in Recursion

c#

algorithm

recursion

genetic-algorithm