title: Recursive Finbonacci Optimization
body: <p>The code below is written to calculate the first 70 Fibonacci Numbers. I have two questions:</p>
  
  <p>1) Why does the program get increasingly slower for each successive value of <code>i</code>?
     Is it because calling the function with high numbers causes heavy memory      footprint.</p>
  
  <p>2) What technique or coding scheme could I use to speed up the programs calculations at run time?    </p>
  
  <pre><code>#include &lt;iostream&gt;
  
  int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
  }
  
  void main() {
    for (int i = 1; i&lt;70; i++)
      cout &lt;&lt; " fib(" &lt;&lt; i &lt;&lt; ") = " &lt;&lt; fib(i) &lt;&lt; endl;
  }
  </code></pre>