title: How does this naive recursive fibonacci implementation not stackoverflow?
body: <p>As a joke a few months ago, a coworker of mine sought out to "speed up the heat death of the universe" by calculating fibonacci numbers using this exponential algorithm:</p>
  
  <pre><code>int Fib(int n)
  {
      if (n &lt;= 1)
          return 1;
      else
          return Fib(n - 1) + Fib(n - 2);
  }
  </code></pre>
  
  <p>How does this not cause a stackoverflow in C#? We managed to get to Fib(52) before giving up (and Fib(51) took many hours). I would think this would hammer the stack hard enough to cause a stack overflow, since the CLR by default only allocates 1M to the stack. Also, I'm pretty sure this isn't eligible for tail recursion either. </p>