为什么.NET/C#不能优化尾调用递归？

我发现这个问题关于哪些语言优化尾递归.为什么C#不会优化尾递归？

对于具体情况,为什么不将此方法优化为循环(Visual Studio 2008 32位,如果这很重要)？:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

ShuggyCoUk.. 80

JIT编译是一个棘手的平衡行为,在不花费太多时间进行编译阶段(从而大大减慢短期应用程序)与不进行足够的分析以保持应用程序在长期内通过标准的提前编译保持竞争力.

有趣的是,NGen编译步骤的目标并不是在优化过程中更积极.我怀疑这是因为他们根本不想有行为取决于JIT或NGen是否负责机器代码的错误.

在CLR本身不支持尾调用优化的,但具体的语言编译器必须知道如何生成相关的操作码和JIT必须愿意尊重它. F#的 fsc将生成相关的操作码(虽然对于简单的递归,它可能只是将整个事物while直接转换为循环).C#的csc没有.

有关详细信息,请参阅此博客文章(鉴于最近的JIT更改,现在很可能已经过时了).请注意,4.0的CLR更改x86,x64和ia64将尊重它.

1> ShuggyCoUk..：

---

JIT编译是一个棘手的平衡行为,在不花费太多时间进行编译阶段(从而大大减慢短期应用程序)与不进行足够的分析以保持应用程序在长期内通过标准的提前编译保持竞争力.

有趣的是,NGen编译步骤的目标并不是在优化过程中更积极.我怀疑这是因为他们根本不想有行为取决于JIT或NGen是否负责机器代码的错误.

在CLR本身不支持尾调用优化的,但具体的语言编译器必须知道如何生成相关的操作码和JIT必须愿意尊重它. F#的 fsc将生成相关的操作码(虽然对于简单的递归,它可能只是将整个事物while直接转换为循环).C#的csc没有.

有关详细信息,请参阅此博客文章(鉴于最近的JIT更改,现在很可能已经过时了).请注意,4.0的CLR更改x86,x64和ia64将尊重它.

---

另见这篇文章:http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1其中我发现尾巴比常规慢呼叫.EEP!

2> Noldorin..：

---

此Microsoft Connect反馈提交应该回答您的问题.它包含了微软的官方回复,所以我建议你去做.

Thanks for the suggestion. We've considered emiting tail call instructions at a number of points in the development of the C# compiler. However, there are some subtle issues which have pushed us to avoid this so far: 1) There is actually a non-trivial overhead cost to using the .tail instruction in the CLR (it is not just a jump instruction as tail calls ultimately become in many less strict environments such as functional language runtime environments where tail calls are heavily optimized). 2) There are few real C# methods where it would be legal to emit tail calls (other languages encourage coding patterns which have more tail recursion, and many that rely heavily on tail call optimization actually do global re-writing (such as Continuation Passing transformations) to increase the amount of tail recursion). 3) Partly because of 2), cases where C# methods stack overflow due to deep recursion that should have succeeded are fairly rare.

总而言之,我们继续关注这一点,我们可能会在未来的编译器版本中找到一些模式来发出.tail指令.

顺便提一下,正如已经指出的那样,值得注意的是在x64 上优化了尾递归.

---

谢谢你引用它,因为它现在是404!

---

您可能会发现这也很有用:http://weblogs.asp.net/podwysocki/archive/2008/07/07/recursing-into-linear-tail-and-binary-recursion.aspx

3> devinbost..：

---

C#不优化尾调用递归,因为这就是F#的用途!

有关阻止C#编译器执行尾调用优化的条件,请参阅本文:JIT CLR尾调用条件.

C#和F#之间的互操作性

C#和F#互操作性非常好,并且因为.NET公共语言运行时(CLR)在设计时充分考虑了这种互操作性,所以每种语言都设计有特定于其意图和目的的优化.有关显示从C#代码调用F#代码是多么容易的示例,请参阅从C#代码调用F#代码 ; 有关从F#代码调用C#函数的示例,请参阅从F#调用C#函数.

对于委托互操作性,请参阅此文章:委派F#,C#和Visual Basic之间的互操作性.

C#和F#之间的理论和实践差异

这篇文章介绍了一些差异,并解释了C#和F#之间尾调用递归的设计差异:在C#和F#中生成尾调用操作码.

下面是一篇文章,其中包含C#,F#和C++\CLI中的一些示例:C#,F#和C++\CLI 中尾部递归的冒险

主要的理论差异是C#是用循环设计的,而F#是根据Lambda演算的原理设计的.关于Lambda演算原理的一本非常好的书,请参阅Abelson,Sussman和Sussman的这本免费书:计算机程序的结构和解释.

有关F#中尾部调用的非常好的介绍性文章,请参阅此文章:F#中的尾调用详细介绍.最后,这篇文章涵盖了非尾递归和尾调用递归(在F#中)之间的区别:F sharp中的尾递归与非尾递归.

4> Alexandre Br..：

---

我最近被告知64位的C#编译器确实优化了尾递归.

C#也实现了这一点.它并不总是被应用的原因是用于应用尾递归的规则非常严格.

---

x64 _jitter_执行此操作,但C#编译器不执行此操作

---

为了澄清这两条评论,C#*从不*发出CIL'尾'操作码,我相信这在2017年仍然如此.但是,对于所有语言,该操作码始终只是在相应的抖动(x86)的意义上的建议如果不满足各种条件,x64)会默默地忽略它(好吧,除了可能的***堆栈溢出之外没有错误***).这就解释了为什么你被迫用'ret'跟随'尾巴' - 这就是这种情况.同时,当CIL中没有'tail'前缀时,抖动也可以自由地应用优化,同样认为合适,并且不管.NET语言如何.