haskell - Haskell 中的尾递归

Question

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

这是“标准”阶乘定义:

factorial 1 = 1
factorial k = k * factorial (k-1)

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

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

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

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

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

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

谢谢!

Answer 1

这里有两个问题。一个是一般的尾递归，另一个是 Haskell 处理事情的方式。

关于尾递归，您的定义似乎是正确的。有用的部分是，因为只需要每个递归调用的最终结果，因此不需要将早期的调用保存在堆栈上。该函数没有“调用自己”，而是做了一些更接近“替换”自己的事情，最终看起来很像一个迭代循环。这是一个相当简单的优化，体面的编译器通常会提供。

第二期是懒惰评测 .因为 Haskell 只根据需要评估表达式，默认情况下尾递归并不像通常的方式那样工作。它不是在执行过程中替换每个调用，而是构建了一大堆嵌套的“thunk”，即尚未请求其值的表达式。如果这个 thunk 堆变得足够大，它确实会产生堆栈溢出。

Haskell 中实际上有两种解决方案，具体取决于您需要做什么:

如果结果由嵌套的数据构造函数组成——比如生成一个列表——那么你要避免尾递归；而是将递归放在构造函数字段之一中。这将使结果也变得懒惰并且不会导致堆栈溢出。

如果结果由单个值组成，您需要严格评估它，以便在需要最终值时强制执行递归的每一步。这给出了尾递归所期望的通常的伪迭代。

另外，请记住，GHC 非常聪明，如果您使用优化进行编译，它通常会发现评估应该严格的地方并为您处理。不过，这在 GHCi 中不起作用。