问题标签 [tail-recursion]

我正在尝试在 OCaml 中实现尾递归列表排序功能，并且我想出了以下代码：

然而，它似乎实际上并不是尾递归，因为我遇到了“评估期间堆栈溢出（循环递归？）”错误。

你能帮我找出这段代码中的非尾递归调用吗？我已经搜索了很多，没有找到它。Cout 它是sort函数中的 let 绑定吗？

我正在寻找一种算法来计算pow()尾递归并使用记忆来加速重复计算。

性能不是问题；这主要是一项智力练习——我花了一趟火车，pow()想出了我能想到的所有不同的实现，但无法想出一个我满意的具有这两个属性的实现。

我最好的镜头如下：

它可以工作，但它不会记住所有计算的结果 - 只有那些具有指数1..exp/2和exp.

这是方法：

这是此方法的可能输出（y 和 n 是用户输入）：

为什么行的“我是蓝色的”和“我是红色的”打印出来？为什么它们以相反的顺序打印为红色，先输入，最后打印？

嵌套列表上的任何类似 flatten、count-atoms 等的东西都可以。

顺便说一句，我对 CPS 转换或“对树”不感兴趣。

有人可以向我展示一个简单的 C++ 尾递归函数吗？

为什么尾递归更好，如果它甚至更好？

除了尾递归还有哪些其他类型的递归？

下面提到的伪代码的任何尾递归版本？谢谢 ！

在 Scala 2.8.x 中，@tailrec添加了一个新的注解 ( )，如果编译器无法对注解的方法执行尾调用优化，则会给出编译时错误。

Clojure 中是否有一些类似的设施loop/recur？

编辑： 在阅读了我的问题的第一个答案（感谢 Bozhidar Batsov）并在 Clojure 文档中进一步搜索后，我发现了这个：

(recur exprs*)
按顺序计算 expr，然后并行地将递归点的绑定重新绑定到 expr 的值。如果递归点是一个 fn 方法，那么它会重新绑定参数。如果递归点是一个循环，那么它会重新绑定循环绑定。然后执行跳回到递归点。递归表达式必须与递归点的数量完全匹配。特别是，如果递归点是可变参数 fn 方法的顶部，则不会收集其余参数 - 应该传递单个 seq（或 null）。recur in other than a tail position 是错误的。

请注意，recur 是 Clojure 中唯一不消耗堆栈的循环结构。没有尾调用优化，不鼓励使用自调用来循环未知边界。recur 是功能性的，它在尾部位置的使用由编译器验证[重点是我的]。

如何使这个 Haskell 幂函数尾递归？

如何打破循环？

如何将嵌套的 for 循环转换为尾递归？

来自 FOSDEM 2009 上的 Scala Talk http://www.slideshare.net/Odersky/fosdem-2009-1013261 第 22 页：

Break and continue Scala 没有它们。为什么？它们有点势在必行。更好地使用许多较小的函数 问题如何与闭包交互。他们不需要！

解释是什么？

如何将列表作为参数传递给以递归方式向其添加元素的函数，并在递归结束时保持不变？

我想在每个递归级别使用列表，该列表具有由更深的递归级别添加的值。

更具体地说，我想在图表上进行 DFS 搜索，并且我想将访问过的节点存储在列表中。