问题标签 [tail-call-optimization]

我一直在研究递归和 TCO。似乎 TCO 可以使代码变得冗长并影响性能。例如，我已经实现了接收 7 位电话号码并返回所有可能的单词排列的代码，例如 464-7328 可以是“GMGPDAS ... IMGREAT ... IOIRFCU” 这是代码。

它很短，我不必花太多时间在这上面。但是，当我尝试在尾调用递归中执行此操作以获取 TCO 时。我必须花费大量时间并且代码变得非常冗长。我不会摆出整个代码来节省空间。这是 git repo link 的链接。可以肯定的是，你们中的很多人都可以写出比我更好、更简洁的尾递归代码。我仍然相信总体而言 TCO 更冗长（例如阶乘和斐波那契尾调用递归有额外的参数累加器。）但是，需要 TCO 来防止堆栈溢出。我想知道您将如何处理 TCO 和递归。在这个线程中使用 TCO 的 Akermann 的 Scheme 实现是我的问题陈述的缩影。

以下博客文章展示了如何在 F#foldBack中使用延续传递样式进行尾递归。

在 Scala 中，这意味着：

可以通过这样做使尾递归：

不幸的是，对于长列表，我仍然会出现堆栈溢出。循环是尾递归和优化的，但我猜堆栈累积只是移动到继续调用中。

为什么这不是 F# 的问题？有没有办法用 Scala 解决这个问题？

编辑：这里有一些显示堆栈深度的代码：

这打印：

Ruby中递归函数中的堆栈溢出错误是否有任何解决方法？

比如说，我有这个块：

如果我打电话countUpTo(1, 10000)，我会得到一个错误：stack level too deep (SystemStackError)。

它似乎在 8187 处中断。我可以调用一些函数来告诉 Ruby 忽略堆栈的大小，或者增加最大堆栈大小的方法吗？

PyPy 1.7 的默认构建包含无堆栈，不提供在没有递归深度限制的情况下运行的能力（以直接方式）。

为什么？

Previus 构建的 PyPy 具有无堆栈支持函数调用和尾递归的延续风格。

我不是在问涉及协程的解决方案，而是在寻找集成 stackelss 的问题。

这是我的尝试，它没有优化尾调用，因为我需要处理枚举器：

这是示例用法：

如果我可以避免使用枚举器（即Seq.head AND Seq.tail），我可以让它工作，但没有Seq.tail我会不知所措。我真的希望用通用序列来完成这项工作..

仅供参考，我知道这段代码在当前状态下无法工作，因为我最终会多次处理枚举器。

所以我的问题的简短版本是，一般来说，我们应该如何在 Haskell 中编码循环？Haskell 中没有尾部优化保证，爆炸模式甚至不是标准的一部分（对吗？），折叠/展开范式不能保证在所有情况下都有效。这就是一个很好的例子，只有 bang-patterns 对我来说是让它在恒定空间中运行的技巧（甚至没有使用help $!...尽管测试是在使用 ghc-6.8.2 的 Ideone.com 上完成的）。

它基本上是关于一个嵌套循环，在列表范式中可以表示为

或者在伪代码中：

直到我添加了爆炸模式，我得到了内存爆裂甚至堆栈溢出。但是刘海图案不是标准的一部分，对吧？所以问题是，如何在标准 Haskell 中编写上述代码以在恒定空间中运行？

这是测试代码。计算是假的，但问题是一样的。编辑： -formulatedfoldr代码是：

尝试运行 print $ testR 1000 1000会产生堆栈溢出。更改为foldl仅在使用 bang-patterns 时才会成功f，但它会以相反的顺序构建列表。我想以正确的顺序懒惰地构建它。fold对于惯用的解决方案，可以使用任何类型的, 来完成吗？

编辑：总结一下我从@ehird 得到的答案：使用爆炸模式没有什么好害怕的。虽然不在标准 Haskell 本身中，但它很容易在其中编码为f ... c ... = case (seq c False) of {True -> undefined; _ -> ...}. 教训是，只有模式匹配会强制一个值，并且seq不会自己强制任何东西，而是安排何时 seq x y强制 - 通过模式匹配 -x也会被强制，y并将成为答案。与我从在线报告中所理解的相反，它$!本身不会强制执行任何操作，尽管它被称为“严格的应用程序操作员”。

@stephentetley 的观点 -严格性对于控制空间行为非常重要。因此，可以在 Haskell 中对循环进行编码，并在需要时正确使用带有 bang 模式的严格性注释，以编写任何需要的特殊折叠（即结构消耗）函数——就像我最终做的那样- 并依靠 GHC 来优化代码。

非常感谢大家的帮助。

背景：我正在为一个学校项目编写一个 .NET 编译器（非常类似于 C#）。我目前尝试添加的功能之一是方法内的尾调用递归。

更多信息：在 CIL 中，“this”被传递给实例方法，就好像它只是另一个参数一样。因此，访问静态方法的第一个参数，您将发出 ldarg.0，但访问实例方法的第一个参数，您将发出 ldarg.1，而在实例方法中访问“this”，您将发出 ldarg.0 . （实例方法比我想象的更类似于扩展方法。）

问题：您可以使用starg.0 设置“this”而没有任何副作用吗？

为什么这是有问题的：方法是否是实例方法是通过 MethodBuilder 设置的，这有点像一个黑盒子。尽管“this”看起来就像任何其他参数一样，但据我所知，一些 JIT 编译器会单独跟踪“this”并根据该值更改它们的行为。如果在实例方法中设置“this”时有副作用，那么我该如何避免它们呢？

Mono (2.11) 上的尾调用优化 (TCO) 实现的当前状态是什么？在某处阅读需要修改所有代码库以使用 callee-pops-arguments 约定。这种变化的状态如何？ARM/Linux 端口在这个问题上是最新的吗？

谢谢！

由于 .net 有TailCall操作码，如果 F# 函数是真正的尾递归，这可以用来确定吗？

如果是真的，有没有人制作了一个识别尾函数和非尾函数的 VS 插件？

以下程序破坏了堆栈：

失败

堆栈空间溢出：当前大小 8388608 字节。使用`+RTS -Ksize -RTS'来增加它。

但是，据我了解，可能的递归调用__find_first_occurrence是由 评估的最后一件事__find_first_occurrence，因此应该可以进行尾调用优化。