21

我试图理解 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# 编译器可以检测尾递归函数并将其转换为循环，但我知道（至少我听说过）目前它还没有这样做。因此，如今使函数尾递归绝对没有意义。是这样吗？

谢谢！

4

2 回答 2

37

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

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

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

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

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

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

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

于 2010-11-04T00:37:01.260 回答
9

您应该使用内置机制，然后您不必考虑使函数尾递归的方法

fac 0 = 1
fac n = product [1..n]

或者，如果尚未定义产品：

fac n = foldl' (*) 1 [1..n]

（请参阅http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27关于使用哪个折叠...版本）

于 2010-11-04T12:06:02.663 回答