问题标签 [tail-recursion]

Steve Yegge 在一篇博文中提到了它，我不知道它是什么意思，有人能补充一下吗？

它与尾调用优化相同吗？

这样做的haskell方法是什么？

更多背景：我正在解决欧拉问题 27，我得到了：

下一步是通过遍历所有可能的 a 和 b 来获取元组列表，然后进行以下处理：

但我不知道如何遍历两个变量..谢谢。

一位朋友在 Clojure 中给了我这段代码片段

并问我它与类似的 Scala 实现相比如何。

我编写的 Scala 代码如下所示：

底线是：Clojure 中的代码在我的机器上运行大约 1.8 秒，使用的堆不到 5MB，Scala 中的代码运行大约 12 秒，512MB 的堆还不够（如果我设置堆到 1GB）。

所以我想知道为什么 Clojure 在这种特殊情况下会更快更苗条？您是否有一个在速度和内存使用方面具有相似行为的 Scala 实现？

请不要发表宗教言论，我的兴趣主要在于找出在这种情况下是什么让 clojure 如此之快，以及在 scala 中是否有更快的算法实现。谢谢。

只是为了让我直截了当。考虑一下这个 Erlang 代码示例：

不是 test() 调用，只是一个 goto 吗？

我问这个是因为我们在 C 中了解到，如果你进行函数调用，返回位置总是放在堆栈上。我无法想象这里的 Erlang 一定是这种情况，因为这会导致堆栈溢出。

我们有两种不同的调用函数的方式：goto 和 gosub。goto 只是将程序流引导到其他地方，gosub 记住了你从哪里来，这样你就可以返回。

鉴于这种思维方式，我可以更轻松地查看 Erlang 的递归，因为如果我只是阅读：test() 作为 goto，那么根本没有问题。

因此我的问题是： :Erlang 不只是使用 goto 而不是记住堆栈上的返回地址吗？

编辑：

只是为了澄清我的观点：

我知道 goto 可以在某些语言中使用，以便到处跳转。但是只是假设你也可以不做 someFunction() ： goto someFunction() 在第一个例子中流程返回，在第二个例子中流程只是在 someFunction 中继续并且永远不会返回。

所以我们通过跳转到方法的起点来限制正常的 GOTO 行为。

如果你这样看，Erlang 递归函数调用看起来像一个 goto。

（我认为 goto 是一个函数调用，无法返回您来自的地方）。这正是 Erlang 示例中正在发生的事情。

要每x秒重复一次方法调用（或消息发送，我想合适的术语是），最好使用 NSTimer（NSTimer 的 scheduleTimerWithTimeInterval:target:selector:userInfo:repeats:) 还是让该方法在结束（使用 performSelector:withObject:afterDelay）？后者不使用对象，但可能不太清晰/可读？另外，只是为了让您了解我在做什么，它只是一个带有标签的视图，该标签倒计时到午夜 12:00，当它到达 0 时，它会闪烁时间 (00:00:00)并永远播放哔声。

谢谢。

编辑：另外，重复播放 SystemSoundID (forever) 的最佳方式是什么？编辑：我最终使用它来永远播放 SystemSoundID：

似乎工作正常.. 对于闪烁的标签，我猜我会使用 NSTimer。

如何将以下内容转换为尾递归版本。

由于分支的数量级为 2^n，因此维护单个累加器似乎是不可能的。

一个可能的解决方案是让累加器在每次迭代时将一个新的累加器添加到列表中。也许上述解决方案是最佳的？

提前致谢。

除了典型的递归函数设计方法之外，还有哪些其他与语言无关的方法：

是否存在其他方法？每当查看示例时，我总是会看到上面代码的一个版本。

谢谢！:)

我怎样才能做到这一点：

为以下每个谓词给出一个尾递归定义。
power(X,Y,Z): XY=Z。
gcd(X,Y,Z): X 和 Y 的最大公约数是 Z。
sum(L,Sum): Sum 是 L 中元素的总和。

到目前为止我已经这样做了，但不确定这是否正确

你能总是构造一个递归函数来消除尾调用吗？如果不是，限制堆栈大小的其他策略是什么？

例如：（受Break or shortcircuit a fold in Scala启发）

目标不是挑剔这个特定的函数，而是将其用作学习限制堆栈大小的技术。

更新

我的收获是：

如果问题域使得递归可能达到堆栈大小的限制：

将代码重写为 scala-compiler-version-of-tailcall-optimizable。这可以通过新的 (2.8) @scala.annotation.tailrec 注释来辅助/验证。

如果这不可行，请重写它以使用迭代循环结构。

我也感觉到这种重写（无论哪种情况）都需要一定的技能/才能/智能/实践。

Does Scala support tail recursion optimization?