问题标签 [tail-call-optimization]

我在 Scheme 中读过一些关于尾调用优化的文章。但我不确定我是否理解尾调用的概念。如果我有这样的代码：

可以对此进行优化，使其不会占用堆栈内存吗？或者尾调用优化只能应用于这样的函数：

虽然看起来不会将尾调用优化作为一种​​常见的优化技术添加，尤其是在 Sun 被收购之后，但从技术上讲，让运行在 VM 上的语言决定它们的编译器是否tailcall在字节码？

例如。Java、Groovy 可以决定不使用该指令，而 Scala 或 Clojure 等更多功能语言可以发出它，HotSpot VM 只会优化标有tailcall?

考虑以下代码：

根据生成的 asm 文件一切正常，尾调用优化。

尝试更换

和

很奇怪，但是尾调用优化消失了。据我所知，在 VS2008 中没有这种奇怪的编译器行为。任何想法为什么会发生这些事情以及如何确保完成尾调用优化？

; 函数编译标志：/Ogtp

尝试了 /O2 和 /Ox 优化标志。还有其他重要的编译器选项吗？

编辑：VS2012 设法进行优化

如果我用一个非常高的初始 currentReflection 值调用这个函数，我会得到一个堆栈溢出异常，这表明该函数不是尾递归的（正确的？）。我的理解是，只要递归调用是函数的最终计算，那么它应该被编译器优化为尾递归函数以重用当前堆栈帧。任何人都知道为什么这里不是这种情况？

我最近学习了 Haskell，并尽可能将纯函数式风格带到我的其他代码中。这方面的一个重要方面是将所有变量视为不可变的，即常量。为了做到这一点，许多将使用命令式循环实现的计算必须使用递归来执行，这通常会由于为每个函数调用分配新的堆栈帧而导致内存损失。然而，在尾调用的特殊情况下（被调用函数的返回值立即返回给被调用者的调用者），这种惩罚可以被称为尾调用优化的过程绕过（在一种方法中，这可以通过基本上在正确设置堆栈后用 jmp 替换调用）。MATLAB 是否默认执行 TCO，或者有没有办法告诉它？

我知道 Python 不支持尾调用优化。这是否意味着具有迭代过程的递归过程（如我在下面定义的阶乘）会消耗 O(n) 内存，或者没有延迟操作这一事实是否意味着空间将为 O(1)？

下面是一个为玩具编程语言以编程方式生成的片段，实际代码不同，但以下显示了它在执行时的作用，

我的问题是 GCC 会考虑将其用于消除尾声吗？

编辑：原来我对 TOC 的看法有点缺陷，所以在不同的情况下，一个不同的函数，在尾部有一个返回，会考虑优化吗？我问的原因是c编译器有一堆方案，而AFAIK方案要求TOC，所以必须有办法强制这样做吗？

我用 C/C++ 的邪恶组合编写了一个小型 Scheme 解释器，但我还没有实现正确的尾调用。

我知道MTA 算法中的经典切尼，但是还有其他很好的实现方法吗？我知道我可以将 Scheme 堆栈放在堆上，但这仍然不是适当的消除，因为标准规定应该支持无限数量的活动尾调用。

我也摆弄过longjmps，但到目前为止，我认为它只适用于非相互递归尾调用。

主要的基于 C 的方案如何实现正确的尾递归？

披露：这出现在我维护的 F# 随机测试框架 FsCheck 中。我有一个解决方案，但我不喜欢它。此外，我不明白这个问题 - 它只是被规避了。

(monadic, if we're going to use big words) 序列的一个相当标准的实现是：

其中 gen 可以由选择的计算构建器替换。不幸的是，该实现消耗了堆栈空间，因此如果列表足够长，最终堆栈溢出。问题是：为什么？我知道原则上 foldBack 不是尾递归，但 F# 团队的聪明兔子已经在 foldBack 实现中规避了这一点。计算构建器实现中是否存在问题？

如果我将实现更改为以下，一切都很好：

为了完整起见，可以在 FsCheck 源代码中找到 Gen 类型和计算构建器

当我写这个函数时，我知道我不会得到尾调用优化。我仍然没有想出一个好的方法来处理这个问题，并希望其他人可以提供建议。

我有一棵树：

我想计算其中有多少个节点：

由于添加了子节点的计数，这不是未优化的。如果树有 100 万个节点，你知道如何做这样的事情吗？

谢谢，德里克

下面是使用 CPS 实现计数。尽管如此，它仍然炸毁了堆栈。

也许我可以想出一些方法将树分成足够多的块，这样我就可以在不破坏堆栈的情况下进行计数？

有人询问生成树的代码。它在下面。