问题标签 [tail-call-optimization]

我有一个我知道是尾递归的函数。但是由于我定义它的方式，编译器抱怨该函数在非尾部位置具有递归调用。这就是功能。

我明白了

如果我这样写，它工作正常。

我认为这与def: (Input) => Output = {}类型声明风格有关。我使用它是因为它看起来比编写嵌套匹配或元组匹配更简洁。

我使用分层数据结构做一些事情，并且我设计了一组方法来使用间接递归遍历/分析它，如下所述。

有方法a, b,c和d, 都有一个Unit返回类型。a首先调用方法。根据数据，它会做一些事情，然后停止或调用其中之一b/c/d。b、c 和 d 中的每一个都相同——每个方法都可以停止或调用其他 3 个方法中的任何一个。所以调用了哪些方法，它们的执行顺序直到运行时才知道，并且递归并不直接明显，因为没有方法直接调用自己（不用担心，每个方法都会被注释以描述循环/递归的性质来电）。

a对、b、c或的每次额外调用d都是每个方法中执行的最后一件事，但它并不是每个方法的最后一条语句；将有一个iforcase语句来控制将调用哪个语句。

鉴于没有方法直接调用自身，Scala 编译器是否能够分析这个多层调用链并为其实现尾递归？

我从尾调用优化问题中得到了激励，什么是尾调用优化？

所以，我决定看看我怎么能用普通的 C 来做。

所以，我写了 2 个阶乘程序，第一个可以应用尾调用优化。我将此事实函数称为事实（n，1）。

第二个是需要多个堆栈帧的正常递归。

这是 32 位编译器为前者生成的程序集，带有 -O2

这是由 32 位编译器为后者使用 -O2 生成的程序集。

编译这两个程序并查看生成的程序集，这两个程序仍然有递归调用。但是，当我在前者中使用 -O2 选项（上面发布的程序集）进行编译时，我根本看不到递归调用，所以我认为 gcc 会进行尾调用优化。

但是当我用 -O2 选项编译后者时，它也删除了递归调用，而是放置了相当多的汇编指令，而前者在 -O2 上发生的情况。

我想准确理解编译器在后者中做了什么，为什么即使使用 O4 也不能转换为前者生成的程序集。

据我所知，Clojurerecur由编译器支持，而在其他 lisps 中，它是在较低级别实现的。

正如我所读到的，这不是“一般”的 TCO。除了显而易见的（需要关键字+检查）之外，还有什么recur不那么强大的吗？

有没有办法在 Clojure 中定义一个自动进行尾调用优化的函数？

例如

将在内部翻译为：

你能告诉我这样的东西是否已经存在吗？

问题的标题可能有点奇怪，但事实是，据我所知，根本没有任何东西反对尾调用优化。然而，在浏览开源项目时，我已经遇到了一些积极尝试阻止编译器进行尾调用优化的函数，例如CFRunLoopRef的实现，它充满了这样的hacks。例如：

我很想知道为什么这看起来如此重要，是否有任何情况下我作为​​一个普通的开发人员也应该记住这一点？例如。尾调用优化有常见的陷阱吗？

关于尾递归函数有几个问题，例如this和this但找不到与以下类似的任何内容。

我的理解是尾调用优化函数应该在其最后一次调用中返回一个累积值，而不需要任何进一步的评估。例如，使用阶乘函数很容易理解，它被优化为循环2。但在其他情况下，例如在以下情况下，告诉您最后一次调用是什么并不总是很明显？其中有很多，因为函数在体内不止一次被递归调用。

Brian 提出了一种查找方法，但我不确定如何优化尾调用。我可以将--tailcalls标志传递给编译器以自动执行它，但它总是成功吗？

f并g返回相同的类型。

任何对尾调用优化上述代码的帮助将不胜感激。

两天前我刚开始使用 Haskell，所以我还不确定如何优化我的代码。

作为练习，我重写了foldland foldr(我会foldl在这里给出，但是foldr是一样的，用lastandhead替换init) tail。

代码是：

我唯一担心的是我怀疑 Haskell 不能在这里应用尾调用优化，因为递归调用不是在函数末尾进行的。

我怎样才能优化这个尾调用？Haskell 的内置foldl实现与我的实现方式不同吗？

我在课堂上被告知，以下函数不是尾递归，因为布尔运算符在递归调用之后被评估：

但这并没有把堆栈炸到千万大小的列表上，更重要的是，它是标准库中的实现。如果它不是尾递归，就没有理由使用这种形式来代替看似等效且明显的尾递归

所以看起来 OCaml 编译器能够在像这样的简单情况下优化布尔运算以利用尾递归。但我注意到，如果我像这样切换操作数的顺序

那么堆栈确实在 10m 个元素上被炸毁。所以看起来 OCaml 只有在递归调用出现在右侧时才能利用这一点，这让我怀疑编译器所做的只是用等效if表达式替换布尔运算。有人可以证实或反驳这一点吗？

我在做 SICP练习 2.28并偶然发现了以下代码的奇怪行为：

普通fringe的运行速度比它的迭代版本快得多fringe-tail：

对比

它看起来像fringe被优化成循环并避免了任何分配，但fringe-tail运行速度要慢得多并且花费时间创建和销毁对象。

谁能给我解释一下？（以防我使用球拍 5.2.1）