I have two functions fib1
and fib2
to calculate Fibonacci.
def fib1(n):
if n < 2:
return 1
else:
return fib1(n-1) + fib1(n-2)
def fib2(n):
def fib2h(s, c, n):
if n < 1:
return s
else:
return fib2h(c, s + c, n-1)
return fib2h(1, 1, n)
fib2
works fine until it blows up the recursion limit. If understand correctly, Python doesn't optimize for tail recursion. That is fine by me.
What gets me is fib1
starts to slow down to a halt even with very small values of n
. Why is that happening? How come it doesn't hit the recursion limit before it gets sluggish?
fib1(30)
.. seems reasonablefib2(30)
, real: 0m0.032s, user: 0m0.025s, sys: 0m0.006s on Python 3. What version of Python are you using?