代码之家 › 专栏 › 技术社区 › devoured elysium

Haskell中的尾递归

tail-recursion recursion haskell

devoured elysium · 技术社区 · 14 年前

下面是“标准”阶乘定义:

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

factorial 3 ,我的函数将调用自己3次(给予或接受)。如果我想计算阶乘99999999,这可能会造成一个问题,因为我可能有堆栈溢出。在我到达之后 factorial 1 = 1

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

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

这个也是递归的。它会叫自己三次。但它不存在这样的问题,即仍然需要“返回”来计算所有结果的乘法,因为我已经将结果作为函数的参数传递。

这就是我所理解的尾部递归的意义所在。现在,它看起来比第一个要好一点,但是您仍然可以很容易地得到堆栈溢出。我听说Haskell的编译器会在幕后将尾部递归函数转换为for循环。我想这就是为什么做尾部递归函数会有回报的原因吧?

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

谢谢!

2 回复 | 直到 14 年前

C. A. McCann Ravikant Cherukuri 14 年前

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

第二个问题是 懒惰的评价 . 由于Haskell只根据需要对表达式求值,因此默认情况下,尾部递归并不完全按照通常的方式工作。它没有按原样替换每个调用,而是构建了一个巨大的嵌套“thunks”堆,即尚未请求其值的表达式。如果这个重击堆变得足够大,它确实会产生堆栈溢出。

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

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

Landei 14 年前

您应该使用内置机制,这样就不必考虑如何使函数尾部递归

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

或者如果尚未定义产品:

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