What is the space complexity of this code?

Question

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

I know that the time complexity is O(2^n) and I understand why.

But I don't understand why the space complexity is O(n). I was told that it's because at any given time there are only n nodes, but it doesn't make sense to me.

Answer 1

Because the second f(n-1) can't run until the first one completes (or vice versa -- it's the same either way). The first call will recurse n times, then all those will return, so that will push a total of n stack frames. Then the second call will do the same thing.

So it never gets more than n levels deep in the recursion, and that's the only contributor to space complexity.