带有任务的尾部递归

本文关键字：尾部 递归 任务 | 更新日期: 2023-09-27 18:07:46

我正在看这篇关于c#尾部递归的文章

我得到了他们使用(Factorial)的一般示例，我试图将其应用于我使用Task递归的情况。我在尝试将上面的示例应用于没有返回类型的Task时遇到了问题。

假设我在c#中有以下类和方法:

public class Crawler(CancellationToken token)
{
    this.cancelToken = token;
}
public async Task CrawlData(string dataLocation, bool repeat = false)
{
    /*Most of processing done here, omitted for space...*/
    while(canCrawl == false)
    {
        await Task.Delay(250);
    }
    await CrawlData(dataLocation, repeat);
}

目前这个工作很好!它可以运行很长时间(天，周，月)而没有问题，因为canCrawl等于false时的延迟。

如果有人感到困惑，我在任务中使用递归的原因是因为我从另一个依赖于Task.Run()的类调用这个方法来初始执行这个方法，并且它依赖于Task是活的，只要递归仍然在进行，那么在主类中的执行在第一次调用后不会跳转到结束。这一切都与能够在任务进行时取消任务有关。

我担心的是，如果这要运行足够长的，它最终会导致StackOverflowException，就像文章开头的链接中的Factorial示例一样。

我已经尝试将该示例应用于没有返回类型的Task，这就是我正在使用的，但我没有任何运气。

你们谁有使用Task在c#中使用尾递归的经验?

带有任务的尾部递归

如果你问你是否会得到StackOverflowException，答案是肯定没有

因为该方法是异步方法，所以在await之后恢复时不保留堆栈。因此，在延迟250ms后，继续运行的线程将拥有一个新的干净的堆栈。

然而，你最终会得到一个OutOfMemoryException，因为每个异步方法被转换成一个状态机结构，它被装箱并保持活动，直到该方法完成(在你的情况下，只有在它的所有尾部调用完成之后)。

Task.Delay太慢了，不能模拟这种行为，但你可以用Task.Yield来模拟，它是异步完成的(像Task.Delay)，但立即完成(不像Task.Delay，它至少有15ms的延迟)。这个示例在不到一分钟的时间内耗尽了我机器上的内存。

private static void Main()
{
    FooAsync().Wait();
}
private static async Task FooAsync()
{
    await Task.Yield();
    await FooAsync();
}

如果你设法有一个任务返回方法，它不是异步的，但你需要使用延续，它可能会避免异常，但这取决于实现。

"如果有人感到困惑，我使用递归与任务的原因是因为我从另一个依赖于Task.Run()的类调用此方法来初始执行此方法"

在这种情况下可能没有理由使用Task.Run。您可以简单地调用该方法并获得任务作为返回值。

我担心的是，如果这要运行足够长的时间，它最终会导致StackOverflowException，就像文章开头的链接中的Factorial示例一样。

它不会，因为代码被编译到的状态机在使用堆栈的方式上实际上并不是递归的。但是，它可能会耗尽内存，并且肯定不是最优的。

尽管如此，如果你有一个想要优化的尾部调用方法，因为抖动没有为你做尾部调用消除，那么手动执行尾部调用消除的相同方法可以在这里应用。(或者仅仅是因为即使手工消除了尾部调用，在。net中通常性能更高)。

考虑是否有等效的同步方法:

public void CrawlData(string dataLocation, bool repeat = false)
{
  /*Most of processing done here, omitted for space...*/
  while(canCrawl == false)
  {
    Thread.Sleep(250); // yes, not ideal but a reasonable analogy.
  }
  CrawlData(dataLocation, repeat);
}

您可以通过将dataLocation和repeat设置为它们的新值(这在您的示例中是无操作的，因为您使用旧值调用它们，并返回到开始:

public void CrawlData(string dataLocation, bool repeat = false)
{
  start:
  /*Most of processing done here, omitted for space...*/
  while(canCrawl == false)
  {
    Thread.Sleep(250);
  }
  goto start;
}

然后应用一些迅猛龙保护:

public void CrawlData(string dataLocation, bool repeat = false)
{
  for(;;)
  {
      /*Most of processing done here, omitted for space...*/
      while(canCrawl == false)
      {
        Thread.Sleep(250);
      }
  }
}

这是一个迭代的版本。通过类比，迭代异步版本为:

public async Task CrawlDataAsync(string dataLocation, bool repeat = false)
{
  for(;;)
  {
      /*Most of processing done here, omitted for space...*/
      while(canCrawl == false)
      {
        await Task.Delay(250);
      }
  }
}

让我们也有一个返回比较的版本。假设你的非异步版本是:

public void CrawlData(string dataLocation, bool repeat = false)
{
  /*Most of processing done here, omitted for space...*/
  while(canCrawl == false)
  {
    Thread.Sleep(250);
  }
  if(repeat)
    CrawlData(dataLocation, repeat);
}

现在，假设某些东西可以改变repeat在"这里完成的大部分处理"空间，那么它最终可以退出。迭代等效为:

public void CrawlData(string dataLocation, bool repeat = false)
{
  do
  {
    /*Most of processing done here, omitted for space...*/
    while(canCrawl == false)
    {
      Thread.Sleep(250);
    }
  } while(repeat);
}

与之对应的async是:

public async Task CrawlDataAsync(string dataLocation, bool repeat = false)
{
  do
  {
    /*Most of processing done here, omitted for space...*/
    while(canCrawl == false)
    {
      await Task.Delay(250);
    }
  } while(repeat);
}
相关文章：