title: python 2.7 - Recursive Fibonacci blows up
body: <p>I have two functions <code>fib1</code> and <code>fib2</code> to calculate Fibonacci.</p>
  
  <pre><code>def fib1(n):
      if n &lt; 2:
          return 1
      else:
          return fib1(n-1) + fib1(n-2)
  
  def fib2(n):
      def fib2h(s, c, n):
          if n &lt; 1:
              return s
          else:
              return fib2h(c, s + c, n-1)
      return fib2h(1, 1, n)
  </code></pre>
  
  <p><code>fib2</code> works fine until it blows up the recursion limit. If understand correctly, Python doesn't optimize for tail recursion. That is fine by me.</p>
  
  <p>What gets me is <code>fib1</code> starts to slow down to a halt even with very small values of <code>n</code>. Why is that happening? How come it doesn't hit the recursion limit before it gets sluggish?</p>