问题标签 [tail-call-optimization]

在 (Common) Lisp 中是否可以跳转到另一个函数而不是调用另一个函数？我的意思是，当前函数被破坏并调用另一个函数，而无需跳回数千个函数，就好像我自己决定是否完成了尾调用优化，即使它不是尾部。我不确定“（return-from fn x）”是否可以，我想要什么。

例子：

'jump' 应该就像调用下面的函数一样，不保存这个函数的位置，而是返回到原来的 funcall 所在的地方，这样就不会发生堆栈溢出。'rest' 只应在 x 为 nil 时执行。

我来自函数式编程背景，首先考虑问题的递归解决方案而不是迭代解决方案。我开始使用 Rebol（特别是 R3），并使用带有累加器的尾递归函数编写了质数因子 kata 的解决方案。但是对于任何足够大的输入，我都会破坏堆栈。我有一个名为“tail-func.r”的 Rebol2 脚本，它实现了 AFAIK 尚未移植到 R3 的尾调用优化版本。我知道 Rebol 3 在许多情况下实现的东西与 R2 不同，那么有没有办法在 Rebol 3 中获得 TCO 而无需任何额外代码？如果没有，是否有更简单的方法可以在不移植旧脚本的情况下获得它？

编辑添加我的代码：

在这次演讲中，在前 8 分钟，Runar 解释了 Scala 在尾调用消除方面存在问题，这让我想知道 F# 是否也有类似的问题？如果不是，为什么不呢？

我尝试在网上挖掘以回答我的问题。我找到了一些与Project DaVinci相关的文件。这被标记为与在 JVM 中包含闭包相关的 JSR 292。这个项目是否实现了，它是 Java 8 的一部分吗？

有些虚拟机，尤其是 JVM，据说不支持 TCO。因此，像 Clojure 这样的语言需要用户使用loop recur。

但是，我可以重写自尾调用以使用循环。例如，这是一个尾调用阶乘：

这是一个等效的循环：

这可以由编译器完成（我已经编写了执行此操作的宏）。对于相互递归，您可以简单地内联您正在调用的函数。

那么，既然您可以在不需要任何 VM 的情况下实现 TCO，为什么语言（例如 Clojure、Armed Bear Common Lisp）不这样做呢？我错过了什么？

到目前为止，我喜欢 JavaScript，并决定使用 Node.js 作为我的引擎，部分原因是因为它声称 Node.js 提供 TCO。但是，当我尝试使用 Node.js 运行这个（显然是尾调用）代码时，它会导致堆栈溢出：

现在，我做了一些挖掘，我发现了这个。在这里，似乎说我应该这样写：

但是，这给了我语法错误。我尝试了它的各种排列，但在所有情况下，Node.js 似乎对某些东西不满意。

本质上，我想知道以下内容：

1. Node.js 做 TCO 还是不做 TCO？
2. 这个神奇yield的东西在 Node.js 中是如何工作的？

特别是如果我有以下代码：

Swift 编译器会将其优化为循环吗？在下面一个更有趣的案例中是这样吗？

tl;博士;

在 C# 中，你是否保证一个惰性迭代器函数只调用它自己并且确实有一个有效的递归退出条件不会导致堆栈溢出？

详细问题：

我知道，作为一项规则，您无法保证 C# 编译器（或 JIT）生成的尾调用优化 (TCO) 指令，因此虽然您可能会获得 TCO，但无法保证。

鉴于对 TCO 的这种认识，我想知道惰性迭代器函数（使用yield return等）是否因为它们作为协程的性质 - 每个尾调用是否会占用堆栈空间？由于协程的可重入性，我对协程的直觉是，默认情况下每个尾调用都经过优化，因为能够跳出函数并从父框架进入下一个函数而不是创建新框架似乎很自然。

这是 C# 中的行为，还是 C# 迭代器函数的递归调用从当前创建一个新框架，而不是弹出到父框架并使用新参数重新输入？

例子：

我的直觉是基于上面的例子subPermutations只是一个堆计算，它似乎在调用迭代它时，它可以知道它是一个堆计算（它是函数sig的一部分，它是一个迭代器函数），因此立即跳转超出当前帧并将堆积的计算扩展到新帧 -在尝试递归调用之前不会花费额外的堆栈空间......

这种直觉可能完全没有根据……

GCC 是否对以下函数执行尾调用优化？

是否可以使用未在 Erlang 中优化尾调用的函数获得 stackoverflow？例如，假设我有这样的功能

看起来如果传入一个足够大的列表，它最终会耗尽堆栈空间并崩溃。我试过这样测试：

但它永远不会崩溃！我尝试了一个包含 100,000,000 个整数的列表，它花了一段时间才完成，但它仍然没有崩溃！问题：

1. 我是否正确测试了这个？
2. 如果是这样，为什么我无法生成stackoverflow？
3. Erlang 是否正在做一些防止堆栈溢出发生的事情？