120

我发现了这个关于哪些语言优化尾递归的问题。为什么 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);
}
4

7 回答 7

89

JIT 编译是在不花费太多时间进行编译阶段（从而显着减慢短期应用程序）与没有进行足够的分析以通过标准提前编译保持应用程序长期竞争力之间的一种棘手的平衡行为.

有趣的是，NGen编译步骤的目标不是更积极地进行优化。我怀疑这是因为他们根本不希望出现行为取决于 JIT 或 NGen 是否负责机器代码的错误。

CLR本身确实支持尾调用优化，但特定于语言的编译器必须知道如何生成相关操作码，并且 JIT 必须愿意尊重它。 F# 的fsc 将生成相关的操作码（尽管对于简单的递归，它可能只是将整个事物while直接转换为循环）。C# 的 csc 没有。

有关详细信息，请参阅此博客文章（鉴于最近的 JIT 更改，现在很可能已过时）。请注意，4.0 的 CLR 更改x86、x64 和 ia64 将尊重它。

于 2009-01-29T12:42:15.690 回答
81

此Microsoft Connect 反馈提交应回答您的问题。它包含微软的官方回应，所以我建议你这样做。

谢谢你的建议。在 C# 编译器的开发过程中，我们考虑过在多个点发出尾调用指令。然而，到目前为止，有一些微妙的问题促使我们避免这种情况：1) 在 CLR 中使用 .tail 指令实际上存在不小的开销成本（它不仅仅是一条跳转指令，因为尾调用最终会变成在许多不太严格的环境中，例如对尾调用进行了高度优化的函数式语言运行时环境）。2) 很少有真正的 C# 方法发出尾调用是合法的（其他语言鼓励具有更多尾递归的编码模式，许多严重依赖尾调用优化的人实际上会进行全局重写（例如继续传递转换）以增加尾递归的数量）。3) 部分由于 2)，C# 方法由于本应成功的深度递归而堆栈溢出的情况相当罕见。

综上所述，我们继续关注这一点，我们可能会在编译器的未来版本中找到一些发出 .tail 指令有意义的模式。

顺便说一句，正如已经指出的那样，值得注意的是尾递归在 x64 上进行了优化。

于 2009-01-29T12:34:11.213 回答
17

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# 之间尾调用递归的设计差异：Generating Tail-Call Opcode in C# and F#。

这是一篇文章，其中包含 C#、F# 和 C++\CLI 中的一些示例：C#、F# 和 C++\CLI中的尾递归冒险

主要的理论区别在于 C# 是用循环设计的，而 F# 是根据 Lambda 演算原理设计的。有关 Lambda 演算原理的非常好的书籍，请参阅这本免费书籍：Abelson、Sussman 和 Sussman 的计算机程序的结构和解释。

有关 F# 中尾调用的非常好的介绍性文章，请参阅这篇文章：F# 中尾调用的详细介绍。最后，这里有一篇文章介绍了非尾递归和尾调用递归之间的区别（在 F# 中）：Tail-recursion vs. non-tail recursion in F sharp。

于 2014-04-28T19:05:42.397 回答
9

最近有人告诉我，64 位的 C# 编译器确实优化了尾递归。

C# 也实现了这一点。之所以不总是应用它，是因为用于应用尾递归的规则非常严格。

于 2009-01-29T12:34:47.203 回答
3

您可以将蹦床技术用于 C#（或 Java）中的尾递归函数。但是，更好的解决方案（如果您只关心堆栈利用率）是使用这个小帮助方法来包装相同递归函数的部分并使其迭代，同时保持函数可读。

于 2012-05-23T11:52:11.863 回答
1

正如其他答案所提到的，CLR 确实支持尾调用优化，而且它似乎在历史上处于逐步改进之中。但是在 C# 中支持它在Proposalgit 存储库中有一个未解决的问题，用于设计 C# 编程语言Support tail recursion #2544。

你可以在那里找到一些有用的细节和信息。例如@jaykrell 提到

让我给出我所知道的。

有时尾声是一种双赢的表现。它可以节省CPU。jmp 比 call/ret 便宜它可以节省堆栈。接触更少的堆栈有助于更好的局部性。

有时尾调用是性能损失，堆栈获胜。CLR 有一个复杂的机制，其中向被调用者传递的参数多于调用者接收到的参数。我的意思是更多的参数堆栈空间。这很慢。但它节省了堆栈。它只会用尾巴做到这一点。字首。

如果调用者参数的堆栈比被调用者参数大，这通常是一个非常简单的双赢转换。可能存在诸如参数位置从托管变为整数/浮点数以及生成精确的 StackMaps 等因素。

现在，还有另一个角度，即需要消除尾调用的算法，以便能够处理具有固定/小堆栈的任意大数据。这与性能无关，而与运行能力有关。

另外让我提一下（作为额外信息），当我们使用命名空间中的表达式类生成编译的 lambda 时System.Linq.Expressions，有一个名为“tailCall”的参数，正如其评论中所解释的那样

一个布尔值，指示在编译创建的表达式时是否应用尾调用优化。

我还没有尝试过，我不确定它对您的问题有何帮助，但可能有人可以尝试它并且在某些情况下可能有用：


var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();
于 2019-12-21T10:39:24.177 回答
1

今天我有一个惊喜:-)

我正在为即将到来的 C# 递归课程复习我的教材。似乎最终尾调用优化已进入 C#。

我正在使用带有 LINQPad 6 的 NET5（已激活优化）。

这是我使用的尾部调用可优化阶乘函数：

long Factorial(int n, long acc = 1)
{
    if (n <= 1)
        return acc;
    return Factorial(n - 1, n * acc);
}

这是为此函数生成的 X64 汇编代码：

汇编代码

看，没有call，只有一个jmp。该功能也进行了积极优化（无堆栈框架设置/拆卸）。哦是的！

于 2021-11-11T21:03:05.033 回答