我的SML代码需要多少空间？

Question

我有像下面的SML代码。

fun fact(n) = 
    let fun f(n,g) = if n=0 then g(1) 
        else f(n-1, fn x=>g(x)*n) 
in f(n, fn x=> x) end; 

我想知道我的代码中需要多少空间来计算fact（n）。 它是否需要O（n）？我不完全清楚。

Answer 1

是的，你写的函数创建了n在最后评估它们之前关闭。

这里是一个更节省空间的版本：

fun fact n = 
    let fun fact' 0 result = result 
      | fact' n result = fact' (n-1) (n*result) 
    in fact' n 1 end 

它使一个递归调用，而不是推迟它，使它尾递归解析之前n*result。