你如何找到这种递归函数的空间复杂性？

Question

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).为什么这是真的？

Answer 1

让我们假设为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).