问题标签 [tail-recursion]

在以下函数中，我尝试通过使用累加器来设置尾递归。但是，我遇到了堆栈溢出异常，这让我相信我设置函数的方式没有正确启用尾递归。

我的理解是，使用acc编译器可以让编译器看到没有必要为每个递归调用保留所有堆栈帧，因为它可以将每次传递的结果填充到 acc 并从每个帧返回。显然，我不明白如何正确使用累加器值，因此编译器会进行尾调用。

这实际上是F#中 Project Euler Problem 14的解决方案。但是，在尝试计算更大数字的迭代序列时，我遇到了 System.OutOfMemory 异常。如您所见，我正在编写带有尾调用的递归函数。

我遇到了 StackOverFlowException 的问题，因为我在 Visual Studio 中进行调试（它禁用了尾调用）。我已经在另一个问题中记录了这一点。在这里，我在发布模式下运行——但是当我将它作为控制台应用程序运行时（在具有 4gb ram 的 windows xp 上），我出现了内存不足的异常。

我真的不知道我是如何将自己编码到这种内存溢出中的，并希望有人能以我的方式向我展示错误。

编辑

鉴于通过答案提出的建议，我重写以使用惰性列表并使用 Int64。

这解决了这个问题。不过，我也会看看殷朱的解决方案，哪个更好。

我有一个家庭作业，要求一个函数使用直接递归来查找数组中最左边、最低、负整数的索引。附加要求是函数的参数是数组和大小，并且没有有效值的返回值为 -999。

我想出了这个：

它有效，满足要求，并得到了我的充分肯定。这可以用尾递归来实现吗？

在我看来，由于您必须从递归调用中获取结果以用于比较，以决定是否将其传递或更新它，这是不可能的，但递归仍然将我的大脑联系在一起，所以可能有一些明显的东西我错过了。

注意：我的家庭作业已经上交并评分。

Is it possible to use both recur and post-condition functionality in the same Clojure function? I was hoping to throw an exception using the post-condition, but Clojure appears to be trying to wrap the exception throwing code after the recur somehow, so (just as a stupid example) functions like this cannot be evaluated.

I'm using Clojure 1.3 at the moment.

我不明白为什么这是前向递归：

这是一个练习考试的问题，答案是它的前向递归。为什么会这样？我怎么能区分这两者？

我有一个 Scheme 函数，其基本形式如下所示

我觉得这很明显需要针对编译中的迭代进行优化，但是当我编译它（用鸡）时，它仍然运行得非常慢。（如果我了解 R5RS 规格：http ://groups.csail.mit.edu/mac/ftpdir/scheme-reports/r5rs-html.old/r5rs_22.html ，这看起来应该可以）

我在 python 中使用 while 循环编写了完全相同的算法，解释程序在几秒钟内终止。我编译的方案大约需要 15 分钟，我很肯定算法是相同的。

我认为这是一个没有得到优化的尾递归问题，因为我想不出还有什么可能，但我想不通。有任何想法吗？就其价值而言，var 是一个散列，破坏性更新只是添加一个元素，尽管它还返回要作为 newvar 传入的更新后的散列。

在 Haskell 中，如果我写

并用 GHC 编译它，结果会与我使用的不同吗

我可以轻松地做到fac n = product [1..n]并避免整个事情，但我对尾递归的尝试如何在惰性语言中发挥作用很感兴趣。我知道我仍然可以得到堆栈溢出，因为 thunk 正在建立，但是当我使用累加器时，实际上发生的任何事情（就生成的编译程序而言）与我只是陈述天真的递归时不同吗？除了提高易读性之外，省略尾递归还有什么好处？如果我runhaskell用来运行计算而不是先编译它，答案是否会发生变化？

我正在使用以下控制结构（我认为它是尾递归的）

做迭代深化

在每次迭代深化之后，这个空闲内存（因为它在技术上将不再能够到达它），如果不是，我应该如何重写控制结构？

PS在第二个虽然看起来这会失败，因为尾递归结构经常能够访问堆栈上的东西，比如添加到前一个值，即使在这种情况下它没有。– Roman A. Taycher 11 月 28 日 12:33 PPS 在第三个问题上，尽管它让我认为它可以在 dfsWithMaxDepth 返回后立即丢弃 dfsWithMaxDepth 中的值，并且一堆答案不会占用太多内存。– Roman A. Taycher 11 月 2 日

Rich Hickey 和其他人提到 Clojure 不会从即将推出invokeDynamic的 JVM 7 或 8 计划中获得显着改进，但会从尾递归中看到性能提升。

尾递归是否会影响

或者

我不希望它们变得更快，因为编译器可能已经生成了循环结构。

可能重复：
为什么 JVM 仍然不支持尾调用优化？

我在网上看到很多不同的答案，所以我想我会问专家。