代码之家 › 专栏 › 技术社区 › Inaimathi

哈斯克尔蓄能器

tail-recursion haskell

Inaimathi · 技术社区 · 14 年前

在哈斯克尔,如果我写

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

然后用ghc编译,结果会和我使用的结果有什么不同吗?

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

我很容易做到 fac n = product [1..n] 避免整个过程,但我对在懒惰的语言中如何尝试尾部递归感兴趣。我知道我仍然可以得到一个栈溢出,因为thunk正在累积,但是当我使用一个累加器时,是否有任何事情实际发生的不同(就结果编译的程序而言)而不是当我只声明简单的递归时?除了改进易读性之外,省略尾部递归还有什么好处吗?如果我用的话答案会变吗 runhaskell 运行计算而不是先编译它?

3 回复 | 直到 14 年前

nominolo 14 年前

fac

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
  ~> ((1*4)*3) * 2
    ~> (1*4) * 3
      ~> 1*4
    ~> 4 * 3
  ~> 12 * 2
~> 24 * 1
~> 24

facRec

foldl' foldl

runhaskell runghc

David V. 14 年前

a good blog post from Don Stewart explains things

Thomas M. DuBuisson 14 年前

facRec fac

推荐文章

Luiz Miranda · 尾递归pow-Erlang

7 年前

Srinivas · Scala中的尾部递归

7 年前

madtyn · Python:有可能使这个尾部递归阶乘更快吗?

7 年前

clay · Scala中的尾部递归findNextAndTail

7 年前

Sanitiy · 如何在调用另一个函数后强制函数退出?

7 年前

Lorinc Nyitrai · Lua-将协程递归重写为尾部调用递归

7 年前

Alex · 尾部递归调用(C primer加上书本示例)

9 年前

Thomas Ahle · 递归联合查找是否可以优化?

9 年前

user87219 · 迭代对数幂

10 年前

beta Rob · 这个函数真的是尾部递归的吗?

11 年前