问题标签 [tail-recursion]

GHC会默认对以下函数进行尾调用优化吗？唯一奇怪的是它递归地定义了一个 IO 操作，但我不明白为什么这不能成为 TCO。

我写了以下函数：

我怎么知道 F# 编译器是否把它变成了循环？有没有办法在不使用 Reflector 的情况下找出答案（我没有使用 Reflector 的经验，也不懂 C#）？

编辑：另外，是否可以在不使用内部函数的情况下编写尾递归函数，或者循环是否必须驻留在其中？

此外，F# std lib 中是否有一个函数可以多次运行给定函数，每次都将最后一个输出作为输入？假设我有一个字符串，我想在字符串上运行一个函数，然后在结果字符串上再次运行它，依此类推......

函数式语言导致使用递归来解决很多问题，因此其中许多执行尾调用优化（TCO）。TCO 导致从另一个函数（或自身，在这种情况下，此功能也称为尾递归消除，它是 TCO 的子集）调用函数，作为该函数的最后一步，不需要新的堆栈帧，这减少了开销和内存使用。

Ruby 显然从函数式语言中“借用”了一些概念（lambda、map 等函数等），这让我很好奇：Ruby 是否执行尾调用优化？

在实现尾调用优化的语言中，递归深度的理论/实践限制是什么？（请假设循环函数被正确地尾调用）。

我的猜测是理论上的限制是 NONE，因为没有递归过程，即使它是递归过程。实际限制将是可用的主存储器允许使用的限制。如果我在某处错了，请澄清或更正。

考虑 C 中的尾递归阶乘实现：

我在“阶乘”中放置了一个断点，然后在“gdb”下运行上面的代码。断点永远不会被击中。

假设它的尾调用已优化（我已使用 gcc -O2 对其进行编译），它应该至少命中一次断点，IIRC。

编辑：我得到最终结果而没有遇到任何断点。例如，

我哪里错了？

显然，关于 Python 是否需要尾调用优化引起了很大的争论。当有人因为 Guido 没有“得到它”而向 Guido 发送了一份 SICP 副本时，这种情况就出现了。我和圭多在同一条船上。我了解尾调用优化的概念。我只是想不出 Python 真正需要它的任何原因。

为了让我更容易理解，有人可以给我一段使用 TCO 可以大大简化的代码片段吗？

我有我为 f# 中的 morris seq 编写的这个“学习代码”，它遭受了我不知道如何避免的堆栈溢出。"morris" 返回一个无限的 "see and say" 序列（即 {{1}, {1,1}, {2,1}, {1,2,1,1}, {1,1,1 ,2,2,1}, {3,1,2,2,1,1},...}）。

您可以使用 Seq.nth 选择第 n 次迭代，但您只能在遇到堆栈溢出之前完成此操作。我有一点递归是尾递归，它本质上构建了一组链接的枚举器。这不是问题所在。这是在第 4000 个序列上调用“枚举”的时候。请注意，对于 F# 1.9.6.16，之前的版本最高超过 14000）。这是因为链接序列的解析方式。序列是惰性的，因此“递归”是惰性的。也就是说， seq n 调用 seq n-1 ，后者调用 seq n-2 等等以获取第一项（第一个 # 是最坏的情况）。

我知道，[|0|] |> Seq.append str |> Seq.windowed 2这使我的问题变得更糟，如果我消除它，我可以产生三倍的#。实际上，代码运行良好。morris 的第 3125 次迭代长度将超过 10^359 个字符。

我真正想要解决的问题是如何保留惰性 eval，并且对于我可以选择的迭代没有基于堆栈大小的限制。我正在寻找合适的 F# 习惯用法来根据内存大小进行限制。

2010 年 10 月更新

在更好地学习 F#，一点点 Haskell，思考和研究这个问题一年多之后，我终于可以回答我自己的问题了。但与难题一样，问题始于错误的问题。问题不在于序列的序列——这实际上是因为递归定义的序列。我的函数式编程技能现在稍微好一点，所以更容易看到下面的版本发生了什么，它仍然得到一个 stackoverflow

这基本上创建了一个非常长的 Seq 处理函数调用链来生成序列。F#自带的Seq模块就是不使用栈就不能跟链的。它对追加和递归定义的序列进行了优化，但该优化仅在递归实现追加时才有效。

所以这会起作用

这个会得到一个stackoverflow。

为了证明 F# 库是问题所在，我编写了自己的 Seq 模块，该模块使用延续实现了追加、成对、扫描和收集，现在我可以毫无问题地开始生成和打印 50,000 个序列（它永远不会完成，因为它已经结束了10^5697 位长）。

一些附加说明：

• Continuations 是我一直在寻找的习语，但在这种情况下，它们必须进入 F# 库，而不是我的代码。我从Tomas Petricek 的 Real-World Functional Programming一书中了解了 F# 中的延续。
• 我接受的惰性列表答案是另一个成语；懒惰的评价。在我重写的库中，我还必须利用惰性类型来避免 stackoverflow。
• 惰性列表版本是靠运气工作的（可能是设计使然，但这超出了我目前的能力范围）——它在构建和迭代时使用的活动模式匹配导致列表在所需的递归变得太深之前计算值，所以它很懒，但不是那么懒，它需要继续以避免stackoverflow。例如，当第二个序列需要第一个序列中的一个数字时，它已经被计算出来了。换句话说，LL 版本对于序列生成并不是严格的 JIT 惰性，只是列表管理。

我喜欢递归地定义序列，如下所示：

我不确定在实践中是否应该使用这样的递归序列。yield! 似乎是尾递归的，但我不能 100% 确定，因为它是从另一个 IEnumerable 内部调用的。从我的角度来看，代码在每次调用时都会创建一个 IEnumerable 实例而不关闭它，这实际上也会使该函数泄漏内存。

这个函数会泄漏内存吗？就此而言，它甚至是“尾递归”吗？

[编辑添加]：我正在摸索 NProf 的答案，但我认为获得有关在 SO 上实现递归序列的技术解释会很有帮助。

我最近一直在阅读有关 Erlang 的文章，以及尾递归是如何被大量使用的，因为使用迭代循环很困难。

递归的大量使用不会减慢它的速度吗？所有的函数调用以及它们对堆栈的影响是什么？还是尾递归否定了大部分？

我对这种语言相当陌生，我想知道尾调用是否得到了优化。在其他语言中，我可以检查机器代码或中间表示并自己计算出来，但我不知道如何在 PL/SQL 中做到这一点。

提前致谢。