c# - 简单的尾递归函数和循环一样高效吗？

Question

有时我发现自己在编写尾递归函数。我一直在上下搜索，我发现.NET框架中有尾递归，但我不确定在什么情况下我可以，在什么情况下我不能有效地使用尾递归。例如，我有一个简单的树，我们称它为

public class Tree
{
  public Tree parent = null;

  public Tree(Tree parent)
  {
    this.parent = parent;
    this.children = new List<Tree>();
  }

  public List<Tree> children {get; private set;}

  public Tree root
  {
    get
    {
      return this.parent == null ? this : parent.root;
    }
  }
}

对于根属性，编译器会发出一个循环吗？它会发出.tail吗？抖动会尊重.tail吗？不会有什么奇怪的事情发生，算法会递归运行吗？最重要的是，我是否应该将其重写为迭代？

Answer 1

C# 编译器永远不会发出 tail 前缀。

如果调用在尾部位置，F# 会这样做。是否适用尾递归取决于遍历树的顺序。

在您的代码中，尾部位置没有任何内容。原因是三元运算符的使用。如果代码被重写为使用 if 语句并返回每个分支，那么对 parent.root 的调用将位于尾部位置。

在优化方面，编译器(F# 或 IronScheme)通常会将尾递归调用转换为 while (true) { ... } 循环。这样做是因为它消除了尾调用和再次调用该方法的需要。

因此，如果允许 C# 发出尾调用(实际上不是)，它可能会从以下位置转换:

public Tree root
{
  get
  {
    if (parent == null) return this;
    else return parent.root; // now in tail position
  }
}

到(只是一个guestimate)

public Tree root
{
  get
  {
    Tree temp = this;
    while (true)
    {
      if (temp.parent == null)
      {
         return temp;
      }
      temp = temp.parent;
    }
  }
}

F# 和 IronScheme 都进行相同的转换。这称为 tail call elimination (TCE)。是的，它会比 C# 版本快一点。 (我已经通过在 C#、F# 和 IronScheme 上对 fib 进行微基准测试对此进行了测试)