决定性尾递归问题

Question

在参与讨论这个问题之后，我想向整个社区提出一个问题。

.Net代码在什么情况下会应用尾调用优化？

请用可靠的最新资料或可重现的实验来支持你的答案。

- SLaks

---

你到底是在寻找什么？真相还是最流行的答案？这里只提供后者。 - Hans Passant

他要求提供证据（“可靠、最新的来源或可重复实验”），这似乎意味着他正在寻找“真相”。无论你对SO有何感觉，他的问题都是有效的，因为.Net编译器和CLR实际上是确定性的。无论任何人是否能够揭示真相，仍然未知。 - jball

对我来说似乎非常局限。编译器的不同版本可能会看到不同的真相。当然，不同的编译器也会有所不同。我对标题有异议：任何只局限于一个编译器的东西都不能成为任何事情上的“决定性问题”。 - dmckee --- ex-moderator kitten

@dmckee，它被标记为“.net”，标题总是与标签一起存在。必须这样做，否则标题将成为关键字的混乱，而标签将变得多余且边缘化。 - jball

@dmckee，它的适用性与编译器无关，但实际应用取决于编译器。在.NET世界中有很多编译器，有些支持尾调用优化，有些则不支持。 - Rune FS

@Rune：那是问题的一部分。（至少对于主流编译器而言） - SLaks

Answer 1

根据Don Syme等人所著的《Expert F#》，F#支持尾调用优化。我记得在Eric Lippert的博客上读过，C#编译器（任何版本）不支持。如果我错了，请纠正我，Eric。在所有情况下，当最后一条指令是调用方法时，都可以进行尾调用优化。这通常是对方法本身的递归调用，但不必如此。可以进行优化，因为保证当前堆栈帧不再需要。但是，如果之后只需执行简单操作，则无法进行优化。

int Fib(int n)
{
  if(n < 2)
     return 1;

  return Fib(n-1) + Fib(n-2);
}

这段代码无法进行尾递归优化，因为在最后一次调用 Fib 返回之前无法评估 +。 （实际上我认为这也是 Expert F# 中使用的示例，但对此不确定。）

int Fib(int n, int a, int b)
{
  if(n == 0)
    return a+b;
  return Fib(n-1,a+b,a);
}

由于在最后一次调用Fib之前所有参数都已经被计算出来，且在调用之后没有任何操作需要执行，因此可以对此版本进行尾调用优化，以便丢弃当前的栈帧。

- Rune FS