在Haskell中的尾递归

2018-06-28 21:30:14

我想了解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＃编译器可以检测并将尾递归函数转换为循环，但我知道（至少是我听说的），目前它不这样做。所以现在使函数尾递归是绝对没有意义的。是吗？

谢谢！

这里有两个问题。一个是通常的尾递归，另一个是Haskell如何处理事情。

关于尾递归，你似乎有正确的定义。有用的部分是，因为只需要每次递归调用的最终结果，以前的调用不需要保存在堆栈中。这个函数并没有“自我调用”，而是做了一些更接近“替换”的东西，最终看起来像一个迭代循环。这是体面的编译器通常会提供的非常直接的优化。

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

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

如果结果由嵌套数据构造函数组成 - 比如产生一个列表 - 那么你想避免尾递归; 而是将递归放在其中一个构造函数字段中。这会让结果变得懒惰，不会导致堆栈溢出。

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

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

你应该使用内置的机制，然后你不必考虑如何使你的函数尾递归

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

或者如果产品尚未定义：

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

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

链接地址: http://www.djcxy.com/p/80683.html