algorithm - 您如何找到此类递归函数的空间复杂性？

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

假设我们做了f（4）。我的想法是它应该是o（2^n），从那时起，为了找到f（n-1）+f（n-1），我们必须将f（n-1）=f（3）推到调用堆栈两次，然后将f（2）推到调用堆栈四次，等等。然而，我从这本书中得到的信息是o（n）。为什么是真的？

最佳答案

让我们假设为f（4）计算这个值（您考虑的示例）。这就是事情的经过。从看起来

I need to compute f(4)

然后f（4）的计算递归到'f（3），堆栈看起来像

I need to compute f(4), so
 I need to compute f(3)

然后我们继续往下走，最后

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), so
   I need to compute f(1), so
    I need to compute f(0)

然后，我们可以将f（0）计算为1，最后一个调用返回。倒数第二个调用（计算f（1）的调用），然后要计算f（0）的第二个副本，堆栈转到：

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), so
   I need to compute f(1), and although I've already computed the first f(0)=1, I still need to compute the second occurrence of f(0), so
    I need to compute f(0) (again)

然后它返回，因此f（1）的计算可以返回，我们得到

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0)

从那里，堆栈变成：

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0), so...
   I need to compute f(1)

它将一如既往地继续计算f（1）。
关键是堆栈的深度只有n，即使（最终）将执行2^n个操作。因此时间复杂度为O（2 ^ n），但空间复杂度仅为O（n）。