问题标签 [tail-call-optimization]

基本上，我正在创建一个基类，该基类将用于存储为链表的类，这些类将按照返回布尔值的虚拟 update() 函数的指示进行遍历和删除。

我想知道这是否是最有效的情况（我特别喜欢它可以是单链表的事实）：

注意链表是 NULL 终止的。

我认为在调用下一个遍历函数之后小心地缺少对局部变量的赋值操作将确保使用尾调用来确保使用该函数。谁能发现我做错了什么，或者建议一种稍微不那么复杂的方法：p

我（偶然）发现最后一个 CLR 进行了尾调用优化。我已经用一段代码对其进行了测试，但坦率地说，它的行为并不符合我的预期。我认为当函数中的最后一件事是函数调用时，可能会发生尾调用优化。

我正在尝试“破坏”此代码以防止表单尾调用操作。

然而 Foo 仍然是优化的。怎么来的？

可能重复：
为什么 .net/C# 不消除尾递归？

采用以下 C# 代码：

C# 编译器（无论如何都是我的）会将 Counter 方法编译为以下 CIL：

上面代码的问题是它会导致堆栈溢出（在我的硬件上大约 i=262000）。为了解决这个问题，一些语言执行所谓的尾调用消除或尾调用优化 (TCO)。本质上，它们将递归调用变成了循环。

我的理解是 .NET 4 JIT 的 64 位实现现在执行 TCO 并避免像上面的 CIL 这样的代码溢出。但是，32 位 JIT 没有。Mono 似乎也没有。有趣的是，JIT（在时间和资源压力下）实现了 TCO，而 C# 编译器却没有。我的问题是为什么 C# 编译器本身没有更多的 TCO 意识？

有一条 CIL 指令告诉 JIT 执行 TCO。例如，C# 编译器可以生成以下 CIL：

与原始代码不同的是，即使在 32 位 JIT（.NET 和 Mono）上，此代码也不会溢出并且会运行完成。神奇之处在于tail.CIL 指令。像 F# 这样的编译器会自动生成包含该指令的 CIL。

所以我的问题是，C# 编译器不这样做是否有技术原因？

我知道它在历史上可能只是不值得。类似的代码Counter()在惯用的 C# 和/或 .NET 框架中并不常见。您可以轻松地将 C# 的 TCO 视为不必要的或过早的优化。

随着 LINQ 和其他东西的引入，似乎 C# 和 C# 开发人员都在朝着更多功能的方向发展。因此，如果使用递归不是一件不安全的事情，那就太好了。但我的问题确实是一个更具技术性的问题。

我错过了一些使 TCO 这样的 C# 的坏主意（或冒险的主意）的东西。还是有什么东西让正确的事情变得特别棘手？这确实是我希望理解的。有什么见解吗？

编辑：感谢您提供的重要信息。我只是想明确一点，我并不是在批评缺乏甚至要求这个功能。我对围绕优先级的合理性不是很感兴趣。我的好奇心是我可能无法察觉或理解的哪些障碍使这成为一件困难、危险或不受欢迎的事情。

也许不同的上下文将有助于集中对话......

假设我要在 CLR 上实现我自己的类 C# 语言。为什么我不（除了机会成本）包括“尾巴”的自动和透明发射。指令在哪里合适？在非常像 C# 的语言中支持此功能时，我会遇到哪些挑战或会引入哪些限制。

再次（并提前）感谢您的回复。

阅读Eric Lippert 的博客文章，我发现了这个片段：

...你要么永远循环（如果你在一个可以优化尾调用的架构上）要么用完堆栈并使进程崩溃。

我知道编译器可以优化尾递归，但是可以优化尾调用的架构是什么意思？

ocamldebug 中的调用堆栈是真正的调用堆栈，因此进行尾调用的函数不会出现在其中。这令人困惑。如何获得包含尾调用的回溯？

使用模式匹配确定列表的 lat 元素的代码：

我想编译代码，我被编译器“大喊大叫”：

如果我删除 @tailrec 注释 - 代码编译。如何修改代码以进行尾部记录优化？

我编写了 3 个阶乘算法：

1. 我预计会因堆栈溢出而失败。没问题。
2. 我尝试了尾递归调用，并将先前的算法从递归转换为迭代。它不起作用，但我不明白为什么。
3. 我使用trampoline()方法，它按我的预期工作得很好。

我已经在 python 和 sapid lisp 本身中实现了一个小的 lisp 解释器（谷歌代码中的 lisp ）。或许它的主要特点是通过异常来实现尾递归和相互递归优化。此处的实施细节https://sites.google.com/site/sapidlisp/recursion-optimization。

与标准技术相比，优势在于有限的更改适用于递归解释器以获得尾递归优化。缺点可能是时机。

我发现在 python 装饰器（http://code.activestate.com/recipes/474088/）中使用了类似的技术。现在把这项技术放在它的上下文中，我正在寻找描述这种 lisp 或其他解释语言的技术的参考资料。有什么资料吗？

我们在 Scala 中试验并行集合，并想检查结果是否有序。为此，我在 REPL 上编写了一个小函数来检查我们正在生成的非常大的列表：

它以 stackOverflow 失败（这里的问题多么合适！）。我期待它是尾部优化的。怎么了？

我正在研究 scala TCO 并编写了以下代码

我已经通过了@tailrec 测试，并且我相信我的函数是自递归尾调用。然而，当我查看 java 字节码时

对于自递归函数，我没有看到 TCO 承诺的goto。这是字节码。