20

有时我发现自己在编写尾递归函数。我一直在寻找高低，我发现.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 吗？不会发生任何幻想，算法会递归运行吗？最重要的是，我应该将其重写为迭代吗？

4

2 回答 2

9

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

到（只是一个猜测）

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# 版本稍微快一点。（我已经通过fibC#、F# 和 IronScheme 的微基准测试对此进行了测试）

于 2012-12-19T11:31:13.113 回答
1

其他答案也有类似的答案。

关于速度。尾递归优化与小函数的循环并没有真正的不同。当尾调用优化触发时，只需将“调用”指令（在 x86 上）替换为“jmp”。当执行相同的循环时，您将有相同的“jmp”指令进入下一个循环。您应该记住的一点是，整个函数体将是循环体，因此您应该尝试最小化递归函数的大小。

于 2012-12-19T11:59:19.130 回答