How do you find the space complexity of recursive

问题:

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

Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f(n-1) = f(3) to the call stack twice, and then f(2) four times the call stack, etc. However, the book I got this from says that is is O(n). Why is that true?

回答1:

Let's imagine evaluating this for f(4) (the example you consider). Here's how it would go. The stack starts by looking like

I need to compute f(4)

Then the calculation of f(4) recurs to `f(3), and the stack looks like

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

Then we keep going down and we eventually get to

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)

Then, we can calculate f(0) as 1, and the last call returns. The penultimate call (the one to compute f(1)), then wants to compute the second copy of f(0), and the stack goes to:

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)

Then that returns, and so the computation of f(1) can return, and we get to

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)

and from there the stack becomes:

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)

and it will continue computing f(1) as before.

The point is that the stack only ever gets as deep as n, even though (ultimately) 2^n operations will be performed. So the time complexity is O(2^n) but the space complexity is only O(n).