Python（超过最大递归深度）vs Haskell（找出答案）

Question

所以我开始学哈斯凯尔。在得到递归定义之后，我将阶乘定义编码为：

let fac n = if n==0 then 1 else n*fac(n-1)

（我知道编码方式完全不同）

我认为这和python的定义是一样的：

^{pr2}$

我的问题是python抛出的最大递归深度错误。虽然这两个函数的编码方式相同，但是什么让python在n=1000时抛出错误并使用haskell计算结果？在

Answer 1

这不是尾部递归，所以Haskell最终也会崩溃。在

fac :: Int -> Int
fac n = if n == 0 then 1 else n*fac(n-1)

（答案不适合Int，只是让它更快地发布崩溃）

不考虑正确性问题，只需运行fac 10000000并看到它因堆栈溢出而崩溃。在

下面是尾部递归：

^{pr2}$

不会崩溃。（但也不是正确答案，因为使用了Int）

（另外，正如注释中正确指出的那样，如果我们让函数保留默认的Integer -> Integer类型，它将使用不受CPU体系结构约束的整数。但从那时起，计算将花费更长的时间，我们将需要更长的时间来满足我们自己，即非尾部递归最终会崩溃。）

在这里的评论中有人抱怨g在a中懒惰。一般来说，这是一个问题，但这并不是重点，在这个特殊情况下，没有区别：

> ghc -O2 -ddump-simpl a.hs > a.dump.lazy
...
Rec {
Main.$wg [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL]
Main.$wg =
  \ (ww_s11J :: GHC.Prim.Int#) (ww1_s11N :: GHC.Prim.Int#) ->
    case ww1_s11N of wild_Xn {
      __DEFAULT ->
        Main.$wg (GHC.Prim.*# ww_s11J wild_Xn) (GHC.Prim.-# wild_Xn 1);
      0 -> ww_s11J
    }
end Rec }

现在，同样，但是要使g严格在a中：

  fac :: Int -> Int
  fac n = g 1 n where
    g !a n = if n == 0 then a else g (a*n) (n-1)
> ghc -O2 -XBangPatterns -ddump-simpl a.hs > a.dump.eager
...
Rec {
Main.$wg [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL]
Main.$wg =
  \ (ww_s11P :: GHC.Prim.Int#) (ww1_s11T :: GHC.Prim.Int#) ->
    case ww1_s11T of wild_Xs {
      __DEFAULT ->
        Main.$wg (GHC.Prim.*# ww_s11P wild_Xs) (GHC.Prim.-# wild_Xs 1);
      0 -> ww_s11P
    }
end Rec }

显然，优化器可以看到g的唯一返回值是a，因此使其变懒是a没有任何好处。在