防止递归中StackOverflow的优雅方法 [英] Elegant way to prevent StackOverflow in Recursion

问题描述

我正在尝试移植此遗传算法，我做了一个递归函数，可以从一代推向另一代.

但是，由于我是C#递归的新手(并且一般而言)，所以当世代太多(超过4500个)时，我显然碰到了StackOverflowException.

为了解决问题，我让Generation()返回布尔值，因此当遗传算法达到最大适应度(目标)时，它返回true.否则，它返回Generation().

如果即将溢出(Generation> 4500)，则返回false.

现在在Main()中，为了使Generation()一直运行直到返回true，我使用了while循环，因此它将从递归开始直到完成.

这比执行Task.Run效率更高，所以我采用了这种方法.

这是好习惯吗?有没有其他更优雅的方法可以在不牺牲性能的情况下防止StackOverflows发生?

Population.cs:

 类人口{public int GenerationNumber {get;私人套装；}public int TotalGenerationNumber {get;私人套装；}public const int StackGenerationLimit = 4500;公众人口{GenerationNumber = 0;TotalGenerationNumber = 0;}公共布尔Generation(){//工作//if(HasReachedGoal)返回true;GenerationNumber ++;如果(GenerationNumber> StackGenerationLimit){返回false；} 别的{返回Generation();}}公共无效ResetStack(){TotalGenerationNumber + =世代号;//我存储世代总数以供参考GenerationNumber = 0;//重置递归深度值}} 

Program.cs

  class程序{静态void Main(string [] args){人口人口=新的人口()；while(！population.Generation())//直到达到目标{人口.ResetStack();}Console.WriteLine("End.Generations:" +人口.TotalGenerationNumber);}} 

解决方案

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

当然，进行了此更改后，您现在还可以执行许多其他整齐的操作.您不再需要重置堆栈，也不再需要用于检查生成限制的if语句，并且所有重复均从while循环中完成.

所以您有两种方法:

 公共布尔生成(){TotalGenerationNumber ++;//工作返回HasReachedGoal;}静态void Main(string [] args){人口人口=新的人口()；bool hasCompleted = false;while(！hasCompleted)//直到达到目标{hasCompleted =人口.Generation();}Console.WriteLine("End.Generations:" +人口.TotalGenerationNumber);} 

请注意，在tidyup中，我引入了一个名为 hasCompleted 的布尔变量，因为我发现在while条件中使用变量更易读，并且更喜欢将工作放在循环内部./p>

I'm trying to port this Genetic Algorithm, and I made a recursive function for advancing from one generation to another.

However, as I'm new to recursion in C# (and in general), I evidently bumped into StackOverflowException when there were too many generations (more than around 4500).

In order to solve the problem, I made Generation() return a bool, so when the genetic algorithm reachs max fitness (goal), it returns true. Else it returns Generation().

If it's about to overflow (Generation > 4500), it returns false.

Now In Main(), to keep Generation() running until it returns true, I use a while loop, so it will start over the recursion until it completes.

This is way more efficient than doing Task.Run, so I went for this approach.

Is this good practice? Are there any more elegant ways of preventing StackOverflows without sacrificing performance?

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


    }
}

解决方案

The best way to avoid stack overflow is to not use recursion. You're already half way to the answer with your workaround. Now you just need to ask yourself the question of what you gain from recursion any more? If your return Generation(); statement in the Generation function were instead changed to return false; then you would go back to the main loop where it would call Generation() again.

Of course having made this change there are now a lot of other tidy ups you can do. You no longer need your stack reset, you no longer need the if statement that checks for the generation limit and all your repetitions are done from the while loop.

So your two methods:

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

Note that in the tidyup I've introduced a bool variable called hasCompleted since I find it more readable to use a variable for the while condition and prefer to have the work inside the loop itself.

这篇关于防止递归中StackOverflow的优雅方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！