使用任务实现尾递归？

Question

我正在查看关于C#尾递归的这篇文章。

我理解了他们使用的一般示例（阶乘），并尝试将其应用于我使用任务递归的情况。我在尝试将上面的示例应用于没有返回类型的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时会有延迟，因此它可以长时间运行（天、周、月）而没有问题。

如果有人感到困惑，我之所以在Tasks中使用递归，是因为我从另一个类中调用了这个方法，该类依赖于Task.Run()来最初执行这个方法，并且它依赖于该Task在递归仍在进行时保持活动状态，以便在第一次调用后不会跳转到结束。这一切都与能够在进程中取消任务有关。

我的担忧是，如果这个程序运行的时间足够长，它最终会导致StackOverflowException，就像本文开头的阶乘示例一样。

我尝试将那个示例应用到没有返回类型的Task上，这就是我正在使用的，但我没有成功。

你们中有谁有使用Task进行尾递归的经验吗？

- user2357446

---

你真正想要问什么呢？ - i3arnon

Answer 1

如果你在问是否会出现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();
}

如果您成功创建了一个不使用异步但使用连续性完成所需任务的方法，则可以避免该异常，但这取决于实现方式。

---

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

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

- i3arnon

Answer 2

我的担忧是，如果这个程序运行时间足够长，它最终会导致StackOverflowException，就像本帖开头的阶乘示例一样。但实际上，它不会这样，因为代码被编译成状态机时并没有递归地使用堆栈。然而，它可能会耗尽内存，而且肯定不是最优解。不过，可以采用手动消除尾调用的方法来优化此处的代码，就像你想要优化尾调用方法一样，因为Jitter不能为你消除尾调用（或者即使在.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);
}

其中异步等效的代码如下：

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

- Jon Hanna