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

Question

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?

Sumbawa

in your example O(1), since you never allocate any memory. and f(n) is simply 2^n – Tillion

The depth of recursion is n – Discommode

Answer 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).

Improbable

@cirular-ruin, what if each function call allocated another, let's say, N^2 memory (not constant like here)? Would we say that space complexity is O(N * N^2) = O(N^3)? – Dictator

It should, I guess. Right @Improbable ? – Ovaritis

Note that 'I still need to compute the second occurrence of f(0)' involves pushing f(m-1), f(m-2), ... , f(0) back onto the call stack (where m is the temporary value of n). This is how we end up making 2^(n)-1 total function calls but the depth of the call stack never exceeds n, i.e the time complexity is O(2^n) but the space complexity is O(n). – Bruckner

Answer 2

The important thing to keep in mind is "What is the size of the call-stack at any given option of time?"

Lets say you were calling 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 **

Although there were a total of 3 calls to f, the call-stack's size did not exceed 2.

Veal