问题标签 [tail-recursion]

在上一个问题中，我被告知如何重写我的计算表达式，以便它使用尾递归。我重写了我的代码，但仍然得到了 StackOverflowException。为了找到问题，我使用 state monad 编写了一些小代码（取自此博客条目）：

这再次抛出 StackOverflowException，尽管 Loop 函数可以使用尾递归（？）。我猜 StateBuilder 类有问题。我试图用延迟方法做一些事情。将所有内容包装在一个额外的 lambda 中，但没有成功。我现在完全卡住了。这是我的第二次尝试（不编译）：

我正在创建一个制造房间的工厂，它传递了一个步骤和一个开始房间，它应该做一个步骤，建造一个房间，然后用更少的步骤调用自己，新房间作为开始房间. 问题是它永远不会结束。在调试器中，我可以看到它正在调用自己，这会在内存中创建另一个方法调用，实际上它少了一个步骤，但随后执行行转到当前方法调用的顶部！所以它永远不会真正完成新的调用。好像它将新调用放入堆而不是堆栈，然后从未真正到达它。

代码：

在上面的代码中，它经历了各种实现，然后到达了对 place() 的新调用，然后它只是创建了一个新的 place() 实例，但没有进入它，而是执行行返回原始呼叫的“房间房间 = start_room”。它无限地执行此操作，循环始终处于其初始值 4，并且越来越多的 place() 实例填满堆栈。我查看了新实例，实际上所有实例的“周期”值都为 3。

奇怪的是，实际运行的每个迭代都在下一个房间运行，所以当它回到顶部时，它会通过下一个房间回到顶部。但是为什么要创建 place() 的新实例（新房间和新循环值为 3），然后使用新房间而不是新循环值 3 重新运行旧 place()？

我是 F# 的新手，正在阅读尾递归函数，希望有人能给我函数 foo 的两种不同实现——一种是尾递归的，另一种不是，这样我可以更好地理解原理。

这个 F# seq 表达式在我看来是尾递归的，但我遇到了堆栈溢出异常（启用了尾调用）。有人知道我错过了什么吗？

如果您想知道，尽管它不应该很重要，但它pick用于生成序列中的元素组合并interleave交错来自 2 个序列的元素。vector是 a 的构造函数ResizeArray。

如果我没记错的话，尾递归函数总是有一个简单的非递归等价物。由于递归涉及不必要的函数调用开销，因此最好以非递归方式进行。

这个假设总是正确的吗？还有其他支持/反对尾递归的论据吗？

我想测试 foldl 与 foldr。从我所看到的情况来看，由于尾递归优化，您应该尽可能使用 foldl 而不是 foldr。

这是有道理的。但是，运行此测试后，我很困惑：

foldr（使用 time 命令时需要 0.057 秒）：

foldl（使用 time 命令时需要 0.089s）：

很明显，这个例子是微不足道的，但我对为什么 foldr 击败 foldl 感到困惑。这不应该是 foldl 获胜的明显案例吗？

我有一个关于 Clojure 的问题：我正在尝试通过Project Euler来学习该语言，但我不明白幕后发生了什么：以下代码旨在使用返回所有素数列表，直到lim. 我认为它在堆空间中应该是 O(n)，因为我列出了所有直到 的数字lim，然后将它们一个一个过滤掉，同时将第一个数字移到一个新列表中。（我知道我实际上每次都在制作新列表，但我认为它们不会占用更多内存？）无论如何我正在运行这个

当我打电话时，我一直在用完堆空间

，但我没有用完空间

所以我认为我一定不明白列表是如何在 recur 调用中被垃圾收集的，并且实际上正在使用 O(n*n) 堆或其他东西。

是否有可能以某种方式结合记忆和尾递归？我目前正在学习 F# 并理解这两个概念，但似乎无法将它们结合起来。

假设我有以下memoize功能（来自Real-World Functional Programming）：

和以下factorial功能：

记忆factorial并不太难，使其尾递归也不是：

但是你能把记忆和尾递归结合起来吗？我做了一些尝试，但似乎无法让它工作。或者这根本不可能？

我正在尝试通过将序列的第一个元素递归地附加到列表中来从序列中构建一个列表：

两个问题：

. 得到一个堆栈溢出，这意味着我的尾巴回避策略很糟糕

和

. 为什么当我放在|> Seq.cache这里 时代码要快 100 倍let newS = s |> Seq.skip(1)|> Seq.cache。

（注意这只是一个小练习，我知道你可以做 Seq.toList 等。）

非常感谢

一种可行的方法是（这两点对我来说仍然有点奇怪）：

我经常听到人们说 C 不执行尾调用消除。即使标准不能保证它，但无论如何，它在实践中不是由任何体面的实现来执行的吗？假设您只针对成熟、实现良好的编译器，而不关心为晦涩平台编写的原始编译器的绝对最大可移植性，那么依赖 C 中的尾调用消除是否合理？

另外，将尾调用优化排除在标准之外的理由是什么？