问题标签 [tail-call-optimization]

在dos-the-jvm-prevent-tail-call-optimizations两年后，似乎有一个原型 实现，并且MLVM已经将该功能列为“原型 80%”已有一段时间了。

Sun/Oracle 方面对支持尾调用没有积极的兴趣，还是只是尾调用“[...]注定要在每个功能优先级列表中排在第二位[...]”，正如JVM中提到的那样语言峰会？

如果有人测试了 MLVM 构建并且可以分享一些关于它工作得如何的印象（如果有的话），我会非常感兴趣。

更新： 请注意，像Avian这样的一些虚拟机支持正确的尾调用，没有任何问题。

我有一个深度递归函数，理论上即使输入很大，它也应该能很好地工作。问题是在撰写本文时，我忘记了 C# 并没有很好地进行尾调用优化（如果有的话），所以StackOverflowException对于任何足够复杂的输入，我都会得到 s。该方法的基本结构是两个大方法，每个方法调用另一个。

两者IsSimple都有ProcessExpansion一个相对固定的堆栈深度——唯一的问题是 Simplify 和 Expand 之间的递归。您将如何减少此处的堆栈深度？

我正在考虑返回代表来计算结果，但这似乎有点矫枉过正——必须有一种更简单的方法。这是我对解决方案的想法（它不是很完美，因为我一直在想我一定是在做一些可怕的错误）：

所以我的两个问题是：

1. 这个解决方案有什么可怕的错误？
2. 你能想出一个更好的吗？

我看到了一些关于 C# 中缺少尾调用优化的问题，据说这使得该语言不适合递归算法实现。然而，这引出了一个问题，我们如何进行尾调用优化，并且在引发异常或可以使用反射来检查调用堆栈并对其采取行动时仍然提供合理的堆栈跟踪。

可能重复：
为什么 JVM 仍然不支持尾调用优化？

我在网上看到很多不同的答案，所以我想我会问专家。

我得到了StackOverflowException这个 Java 方法：

我正在玩尾调用递归，所以我想这就是当 JVM 不短路堆栈时会发生的情况，对吧？

在制定另一个 SO question 的答案时，我遇到了一些关于 Mathematica 中尾递归的奇怪行为。

Mathematica 文档提示可能会执行尾调用优化。但是我自己的实验给出了相互矛盾的结果。对比一下，例如下面两个表达式。第一个使 7.0.1 内核崩溃，可能是由于堆栈耗尽：

第二个运行完成，似乎利用尾调用优化来返回有意义的结果：

两个表达式都定义了一个尾递归函数f。在第一个函数的情况下，Mathematica 显然认为复合语句的存在足以阻止任何尾调用优化的机会。另请注意，第一个表达式受控于$RecursionLimit，第二个受控于$IterationLimit-- 这表明 Mathematica 对这两个表达式的处理方式不同。（注意：上面引用的 SO 答案有一个不那么做作的函数，它成功地利用了尾调用优化）。

所以，问题是：有谁知道 Mathematica 在什么情况下执行递归函数的尾调用优化？最好参考 Mathematica 文档或其他WRI材料中的明确声明。也欢迎投机。

我有以下 Clojure 代码来计算具有特定“可分解”属性的数字。（代码的确切作用是次要的）。

现在，我进入 TCO 并意识到 Clojure 只有在使用recur关键字明确告知时才能提供尾递归。所以我重写了代码来做到这一点（用 recur 替换 factor-9 是唯一的区别）：

据我所知，TCO 有双重好处。第一个是它没有像非尾递归调用那样大量使用堆栈，因此不会在更大的递归上破坏它。第二个，我认为因此它更快，因为它可以转换为循环。

现在，我做了一个非常粗略的基准测试，但没有看到这两种实现之间有任何区别。我的第二个假设是错误的，还是这与在 JVM（没有自动 TCO）上运行并recur使用技巧来实现它有关？

谢谢你。

我正在尝试尽可能多地用 C 编写函数式程序。我知道像 GCC/Clang 这样的编译器会默默地进行尾调用优化，但不能保证。是否有任何选项可以强制对编译器进行尾调用优化？（当然，只有在它自己的末尾才被调用）

为什么除非方法是最终的，否则 Scala 编译器不会应用尾调用优化？

例如，这个：

结果是

错误：无法优化 @tailrec 注释方法：它既不是私有的也不是最终的，因此可以被覆盖

如果编译器在这种情况下应用TCO ，究竟会出现什么问题？

我正在使用 F# 规范中的最终工作流的修改版本在 Xbox 上进行开发。Xbox 上的 .net 框架似乎不支持尾调用。因此，我必须在编译时禁用尾调用优化。

尽管乍一看这种限制会阻止在计算表达式中使用任何形式的循环，但我最初认为“步进”会避免这个问题：计算表达式中的递归函数 f 不会直接调用自身，而是它返回包含调用 f 的 lambda 的最终值。

实验表明我对 while 循环的看法是正确的（在计算表达式中使用它们不会导致堆栈溢出），但对递归函数却不是。

为了澄清，这有效：

这会导致堆栈溢出：

在第二种情况下，堆栈跟踪显示对“bind@17-1”的一长串调用，其代码如下所示。堆栈跟踪中出现的行号是第 17 行。

我哪里错了？我关于“​​可步进递归”是无害的 wrt 堆栈溢出的推理不正确吗？我的绑定实现有问题吗？

哦，我的头！递归的继续传递让我头疼......

编辑：“可步进递归是无害的 wrt 堆栈溢出”有一个名字，我刚刚了解到。它被称为蹦床。