big o - Space complexity of recursive function

Question

Given the function below:

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

I know that the Big O time complexity is O(2^N), because each call calls the function twice.

What I don't understand is why the space/memory complexity is O(N)?

question from:https://stackoverflow.com/questions/43298938/space-complexity-of-recursive-function

Answer 1

A useful way to approach these types of problems is by thinking of the recursion tree. The two features of a recursive function to identify are:

1. The tree depth (how many total return statements will be executed until the base case)
2. The tree breadth (how many total recursive function calls will be made)

Our recurrence relation for this case is T(n) = 2T(n-1). As you correctly noted the time complexity is O(2^n) but let's look at it in relation to our recurrence tree.

      C
     /          
    /         
T(n-1)  T(n-1)

            C
       ____/ \____
      /           
    C              C   
   /             /  
  /             /    
T(n-2) T(n-2) T(n-2)  T(n-2)

This pattern will continue until our base case which will look like the following image:

With each successive tree level, our n reduces by 1. Thus our tree will have a depth of n before it reaches the base case. Since each node has 2 branches and we have n total levels, our total number of nodes is 2^n making our time complexity O(2^n).

Our memory complexity is determined by the number of return statements because each function call will be stored on the program stack. To generalize, a recursive function's memory complexity is O(recursion depth). As our tree depth suggests, we will have n total return statements and thus the memory complexity is O(n).