haskell - 在Haskell中,尾部递归

  显示原文与译文双语对照的内容
60 0

我在尝试理解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的编译器将尾部递归函数转换为场景后面的循环。我想这就是做尾递归函数的原因?

如果这就是原因,当编译器不会做这个智能的--时,绝对不需要尝试使函数尾递归。例如虽然在理论上 C# 编译器可以检测并转换尾部递归函数循环,但我知道( 至少是我所听到的) 目前并没有这样做。因此,现在不存在使函数尾部递归的绝对意义。就是这样?

谢谢!

时间:原作者:0个回答

78 5

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

关于尾递归,你似乎有正确的定义。有用的部分是,因为只需要每个递归调用的最终结果,以前的调用不需要保存在堆栈上。函数与"调用自身"相比,功能更接近"正在替换"本身,结果看起来像一个迭代循环。这是一个非常直接的优化,好的编译器通常会提供。

第二个问题是延迟评估因为Haskell只是根据需要计算表达式,所以默认情况下,尾部递归并不常见。而不是替换每个调用,它构建了一个巨大的嵌套堆,即没有请求它的值的表达式。如果这个thunk堆足够大,它实际上会产生堆栈溢出。

实际上,Haskell中有两个解决方案,具体取决于你需要执行的操作:

  • 如果结果由嵌套数据constructors--like生成,那么你要生成一个你想要进行的list--then,避免尾递归;而是将递归放在构造函数。这将使结果也很懒惰,不会导致堆栈溢出。

  • 如果结果由单个值组成,则希望对它的进行严格评估,从而使递归的每一步都在需要的最后一个值被强制。这给出了你在尾递归中预期的伪迭代。

另外,如果你编译了优化,那么通常会发现评估应该严格地处理。这在GHCi中不起作用。

原作者:
85 4

你应该使用构建的机制,然后不必考虑使函数尾递归的方法。

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

或者,如果产品还没有定义:

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

( 请参见 http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 关于哪个折叠。要使用的版本)

原作者:
...