你如何找到递归函数的 space 复杂度，例如这个函数？

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，最后调用returns。倒数第二个调用（计算 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)

然后returns，所以f(1)的计算可以return，我们得到

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) 但 space 复杂度只有 O(n).

你如何找到递归函数的 space 复杂度，例如这个函数？

How do you find the space complexity of recursive functions such as this one?

algorithm

recursion

big-o

time-complexity

space-complexity