title: Space complexity of recursive function
body: <p>Given the function below:  </p>
  
  <pre><code>int f(int n) {
    if (n &lt;= 1) {
      return 1;
    }
    return f(n - 1) + f(n - 1);
  } 
  </code></pre>
  
  <p>I know that the Big O time complexity is <code>O(2^N)</code>, because each call calls the function twice.</p>
  
  <p>What I don't understand is why the space/memory complexity is <code>O(N)</code>?</p>