简单的尾递归函数和循环一样有效吗？

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

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

(只是一个猜测)

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的微基准测试对此进行了测试)