问题标签 [tail-call-optimization]

我开始学习 ocaml，并且非常欣赏这种语言中递归的力量。但是，我担心的一件事是堆栈溢出。

如果ocaml使用堆栈进行函数调用，最终不会溢出堆栈吗？例如，如果我有以下功能：

它最终必须导致堆栈溢出。如果我要在 c++ 中做同样的事情（使用递归），我知道它会溢出。

所以我的问题是，是否有内置的保护措施来防止函数式语言溢出堆栈？如果不是，它们是不是像这样不那么有用，因为上面的求和算法，以带有 for 循环的程序风格编写，可以处理任何数字（不考虑整数溢出）？

一位朋友在 Clojure 中给了我这段代码片段

并问我它与类似的 Scala 实现相比如何。

我编写的 Scala 代码如下所示：

底线是：Clojure 中的代码在我的机器上运行大约 1.8 秒，使用的堆不到 5MB，Scala 中的代码运行大约 12 秒，512MB 的堆还不够（如果我设置堆到 1GB）。

所以我想知道为什么 Clojure 在这种特殊情况下会更快更苗条？您是否有一个在速度和内存使用方面具有相似行为的 Scala 实现？

请不要发表宗教言论，我的兴趣主要在于找出在这种情况下是什么让 clojure 如此之快，以及在 scala 中是否有更快的算法实现。谢谢。

我对最近关于 GOTO 和尾递归的问题的回答是用调用堆栈来表达的。我担心它不够通用，所以我问你：尾调用（或等效）的概念在没有调用堆栈的架构中如何有用？

在继续传递中，所有被调用的函数都会替换调用函数，因此是尾调用，因此“尾调用”似乎不是一个有用的区别。在基于消息传递和事件的体系结构中，似乎没有等价物，但如果我错了，请纠正我。后两种架构是有趣的案例，因为它们与 OOP 而不是 FP 相关联。其他架构呢？旧的 Lisp 机器是基于调用堆栈的吗？

编辑：根据“ What the heck is: Continuation Passing Style (CPS) ”（以及下面的 Alex），连续传递下的尾调用的等价物不是“被调用函数替换调用函数”而是“调用函数传递了它是给定的，而不是创造一个新的延续”。与我所断言的不同，这种尾调用很有用。

另外，我对在较低级别使用调用堆栈的系统不感兴趣，因为较高级别不需要调用堆栈。这个限制不适用于亚历克斯的回答，因为他写的是其他调用架构（这是正确的术语吗？）通常有一个等效的调用堆栈，而不是他们在引擎盖下的某个地方有一个调用堆栈。在连续通过的情况下，结构就像一个树状结构，但边缘方向相反。调用堆栈等价物与我的兴趣高度相关。

从这个问题开始：how-do-i-check-if-gcc-is-performing-tail-recursion-optimization，我注意到使用 gcc 和 -fPIC 似乎破坏了这种优化。我正在创建一个共享库，但我似乎不需要 -fPIC 选项。

好吧，我的问题是，为什么 -fPIC 会改变 gcc 优化？我是否需要出于任何原因保留 -fPIC ？

有人可以将此（plt）Scheme 代码重写为 Clojure 吗？

以不将过程 f、g 和 h 折叠在一起并允许代码无限期运行而不会崩溃的方式？

在参与了这个惨败问题的辩论之后，我想向整个社区提出这个问题。

在什么场景下，尾调用优化将应用于基于 .Net 的代码？

请用可靠的、最新的来源或可重复的实验来支持你的答案。

根据对该问题的回答： 如果有的话，哪些 C++ 编译器会进行尾递归优化？ 看来，编译器应该进行尾递归优化。

但是我已经尝试过建议的选项，并且在模板函数的情况下编译器似乎无法进行这种优化。它可以以某种方式修复吗？

我想看看.tailIL 指令，但是我一直在编写的使用尾调用的简单递归函数显然已优化为循环。我实际上是在猜测这一点，因为我不完全确定 Reflector 中的循环是什么样的。不过，我绝对看不到任何.tail操作码。我在项目的属性中检查了“生成尾调用”。我还尝试了 Reflector 中的调试和发布版本。

我使用的代码来自Chris Smith 的 Programming F#，第 190 页：

谁能建议一些确实会生成的简单 F# 代码.tail？

我认为有@tailrec注释可以确保编译器优化尾递归函数。你只是把它放在声明的前面吗？如果在脚本模式下使用 Scala（例如:load <file>在 REPL 下使用），它是否也有效？

我经常听到人们说 C 不执行尾调用消除。即使标准不能保证它，但无论如何，它在实践中不是由任何体面的实现来执行的吗？假设您只针对成熟、实现良好的编译器，而不关心为晦涩平台编写的原始编译器的绝对最大可移植性，那么依赖 C 中的尾调用消除是否合理？

另外，将尾调用优化排除在标准之外的理由是什么？