问题标签 [tail-recursion]

我有一个用 JavaScript 实现的尾递归寻路算法，想知道是否有任何（所有？）浏览器可能会出现堆栈溢出异常。

考虑一个像下面这样的haskell-expression：（简单的例子，不要告诉我明显的方法是什么！;）

因为这个函数不是尾递归的，所以也可以这样写：

（我希望这个表达没有错）

我想问的是，这些解决方案中哪一个更好。第一个的优点是，它可以很容易地进行部分评估（因为 Haskell:不需要在第一个处停止。），但第二个解决方案（显然）是尾递归的，但在我看来，它需要被完全评估直到你能拿出一些东西。

这个的背景是我的 Brainfuck 解析器，（见我的优化问题），它的实现非常丑陋（各种reverse指令......哦），但可以很容易地在第一个实现 - 我们称之为“半尾递归”方式.

有时它很简单（如果 self 调用是最后一个语句，它就是尾递归），但仍有一些情况让我感到困惑。一位教授告诉我“如果在自调用之后没有执行指令，那就是尾递归”。这些例子怎么样（忽略它们没有多大意义的事实）：

a）这个应该是尾递归的，看看自调用是最后一个语句，并且在它之后没有任何东西可以执行。

b) 但是这个呢？它应该是一个尾调用，因为如果条件为真，除了它之外什么都不会被执行，但它不是最后一个语句？

c) 这个怎么样？在这两种情况下，self 调用都是最后执行的：

我有一个深度递归函数，理论上即使输入很大，它也应该能很好地工作。问题是在撰写本文时，我忘记了 C# 并没有很好地进行尾调用优化（如果有的话），所以StackOverflowException对于任何足够复杂的输入，我都会得到 s。该方法的基本结构是两个大方法，每个方法调用另一个。

两者IsSimple都有ProcessExpansion一个相对固定的堆栈深度——唯一的问题是 Simplify 和 Expand 之间的递归。您将如何减少此处的堆栈深度？

我正在考虑返回代表来计算结果，但这似乎有点矫枉过正——必须有一种更简单的方法。这是我对解决方案的想法（它不是很完美，因为我一直在想我一定是在做一些可怕的错误）：

所以我的两个问题是：

1. 这个解决方案有什么可怕的错误？
2. 你能想出一个更好的吗？

我正在尝试创建一个函数，该函数使用遗传算法递归地玩所有可能的井字游戏，然后返回一个 (wins,losses,ties) 的元组。但是，下面的函数在这样调用时总是会溢出堆栈：

哪里players是染色体列表。溢出不会发生在只有 1 名玩家的情况下，但会发生在 2 名玩家身上。

编辑：如果函数以下列方式调用，它不会溢出堆栈。

但是，以下方式确实会溢出堆栈。

作为参考，ScoredPlayer定义为（字符串为玩家标记，[Int] 为染色体，Float 为分数）：

根据我对 Haskell 的了解，该playAll'函数不是尾递归的，因为foldl'我正在使用的调用正在对函数结果执行进一步处理。但是，我不知道如何消除foldl'呼叫，因为需要确保玩所有可能的游戏。有什么方法可以重构函数，使它是尾递归的（或者至少不会溢出堆栈）？

在此先感谢，并为大量代码清单感到抱歉。

可能重复：
递归比循环快吗？

大约 15 年前，我第一次接受了认真的 C 语言培训。我的雇主想要高度优化的代码来完成计算困难的任务。我记得不止一次被建议将递归重写为循环，即使以牺牲可读性为代价，以避免“递归开销”。正如我当时所理解的那样，递归开销是将数据推送到堆栈然后将其弹出所需的额外工作。

现在我用 C、Python、Perl 和 Java 编写代码，有时我想知道递归。重写它们还有什么好处吗？如果它们是尾递归怎么办？现代编译器是否已经解决了所有这些问题？这些问题与解释语言无关吗？

我想编写一个函数来使用尾递归查找 C(n,k)，非常感谢您的帮助。

我已经达到了这个：

使用二项式系数的以下性质。

但我不知道如何使递归调用成为每个实例执行的最后一条指令，因为最后一条是产品。我一直在尝试使用辅助功能，我认为这是唯一的方法，但我还没有找到解决方案。

我试图理解 Haskell 中的尾递归。我想我明白它是什么以及它是如何工作的，但我想确保我没有把事情搞砸。

这是“标准”阶乘定义：

例如，在运行时factorial 3，我的函数将调用自身 3 次（给予或接受）。如果我想计算阶乘 99999999，这可能会造成问题，因为我可能会出现堆栈溢出。在我到达之后，factorial 1 = 1我将不得不在堆栈中“返回”并乘以所有值，所以我有 6 个操作（3 个用于调用函数本身，3 个用于乘以值）。

现在我向您介绍另一种可能的阶乘实现：

这也是递归的。它会调用自己 3 次。但它不存在仍然必须“返回”来计算所有结果的乘法的问题，因为我已经将结果作为函数的参数传递了。

据我所知，这就是尾递归的含义。现在，它似乎比第一个好一点，但您仍然可以轻松地发生堆栈溢出。我听说 Haskell 的编译器会在后台将 Tail-Recursive 函数转换为 for 循环。我想这就是为什么做尾递归函数有回报的原因？

如果这就是原因，那么如果编译器不打算做这个聪明的把戏，那么绝对没有必要尝试使函数尾递归——我是对的吗？例如，虽然理论上 C# 编译器可以检测尾递归函数并将其转换为循环，但我知道（至少我听说过）目前它还没有这样做。因此，如今使函数尾递归绝对没有意义。是这样吗？

谢谢！

所以我遇到了试图从给定的 N 元素集中找到所有 k 元素子集的问题。我知道使用公式 C(n,k)=C(n-1, k-1)+C(n-1, k) 的 k 子集的总数是多少，我也知道怎么做以迭代的方式，但是当我尝试考虑递归解决方案时，我陷入了困境。谁能给我一个提示？谢谢！

自然数的阶乘（任何大于或等于 的数0）是该数乘以自身的阶乘减一，其中的阶乘0定义为1。

例如：

另一种写法是将1和之间n的所有自然数相乘n!：

如何在 F# 中使用递归函数来表达这一点？我应该用递归函数来做吗？