recursion - 以下函数的空间复杂度是多少以及如何？

Question

考虑以下递归函数。

int f(int n){
   if(n<=0) return 1; return f(n-1)+f(n-1);
}

据说虽然有 2^N(2 次幂为 N)次调用，但在给定时间仅存在 N 次调用。有人能解释一下怎么做吗？

Answer 1

当然。复杂性部分位于else部分:

return f(n-1)+f(n-1)

对于 n 处的每次调用，这会在 n-1 处生成两次调用。但是，请注意评估顺序:

call f(n-1) ... left side
save the value as temp1
call f(n-1) ... right side
add the value to temp1
return that value

整个左侧调用树必须在右侧调用树开始之前完成 - 这发生在每个深度级别。对于n的每个值，在任何时间点都只有一个调用处于事件状态。例如，f(2) 给我们一个像这样的序列:

call f(2)
n isn't <= 0 ...
    call f(1) ... left
    n isn't <= 0 ...
        call f(0) ... left | left
        n <= 0; return 1
        save the 1
        call f(0) ... left | right
        n <=0; return 1
        add the 1 to the temp value;
        return 2
    save the 2
    call f(1) ... right
        call f(0) ... left | left
        n <= 0; return 1
        save the 1
        call f(0) ... left | right
        n <=0; return 1
        add the 1 to the temp value;
        return 2
    add this 2 to the temp value, making 4
    return the 4
done ...

尽管我们最终执行了 2^(n+1)-1 次调用，但在每个点，事件调用都不超过 n+1 个(请参阅缩进级别)。我们偏离了 1(n+1 而不是 n)，因为我们在 0 而不是 1 处终止。

这样就可以解决问题了吗？