我的 SML 代码需要多少 space？

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;

我想知道我的代码需要多少 space 来计算 fact(n)。它是否需要 O(n)？具体我也不清楚。

Answer 1

是的，您编写的函数在最后计算它们之前创建了 n 个闭包。

这是一个更 space 高效的版本：

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

它在进行递归调用之前解析 n*result，而不是延迟它，使其成为尾递归。

How much space is required in my SML code?