1

我想知道 Haskell 中的每个函数都应该是尾递归的。

阶乘函数实现为非尾递归函数:

fact 0 = 1
fact n = n * fact (n - 1)

每个运算符也是一个函数,所以这相当于

fact 0 = 1
fact n = (*) n (fact (n - 1))

但这显然是对我的尾声。我想知道如果每次调用都在堆上创建一个新的 thunk,为什么这段代码会导致堆栈溢出。我不应该堆溢出吗?

4

1 回答 1

2

在代码中

fact 0 = 1
fact n = (*) n (fact (n - 1))

(*) ...正如您所观察到的,最后一个是尾声。然而,最后一个参数fact (n-1)将建立一个 thunk 立即被(*). 这导致对 的非尾调用fact。递归地,这将消耗堆栈。

TL;DR:发布的代码执行尾调用,但(*)没有。

(此外,Haskell 中的“堆栈”的概念并不像严格的语言那样清晰。Haskell 的一些实现使用的东西比这更复杂。如果你想要一些血淋淋的细节,可以搜索“push/enter vs eval/apply”策略.)

于 2015-03-30T08:16:24.790 回答