如何找到像这样的递归函数的空间复杂度？

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)。

重点是，即使（最终）执行 2^n 次操作，堆栈的深度也只能达到 n。所以时间复杂度是 O(2^n) 但空间复杂度只有 O(n)。

Answer 2

要记住的重要一点是“在任何给定时间选项下调用堆栈的大小是多少？”

假设您正在打电话

f(2)

f(2) --> f(1) # f(2) pushed f(1) to call-stack
f(2)          # f(1) finished executing and popped from stack.
f(2) --> f(1) # f(2) pushed the second f(1) to call-stack
f(2)          # the second f(1) finished executing and popped. 
** End of recursion **

虽然总共有 3 次调用

f

，但调用堆栈的大小并未超过 2。