python 在这么算 fibonacci 的时候到底在干什么！？

[juicy]

这几天学了点python,有一道题是让练习用python计算fibonacci数列，发现个很有意思的事：
当用传统的写法
return fib(n-1) + fib(n-2)
来算fib(40)的时候，算得超级慢,分钟级别的
而用generator的时候
def fib():
a = 1
b = 2
while 1:
a, b = b, (a+b)
yield a
counter = 0
for n in fib():
if counter == 40:
print n
break
counter +=1
瞬间就计算完了

后来，在这个链接里http://fengmk2.cnpmjs.org/blog/2011/fibonacci/nodejs-python-php-ruby-lua.html 发现了各种语言算fib(40)的效率

我很纳闷的是：
最后几种语言花费的时间跟python一样，都竟然达到1m，2m，甚至3m，
说得夸张一点，人脑算得都比它们快，
那么，问题来了，如题

[jox]

额，v2ex会把前面的空格都处理掉啊，晕了

[xarrow]

Python 切片 尾调，明天贴代码！

[songco]

其实n不大的情况下, 直接用公式比较好:
f(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

[jox]

python对递归深度有限制，默认好像超过1000就不让算了，因为python不支持尾递归优化，所以即使写成尾递归的形式也不会节省资源，但是只要不超过默认的递归深度计算速度也是非常快的，不过有个技巧可以让尾递归形式的函数超过递归深度，就像这样：

[monkeylyf]

一个是递归没有memorization 一个是类似dp的O(n) 当然后者快啦

[juicy]

多谢各位，受益匪浅~

[hahastudio]

Python Tail Call Optimization Decorator
http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/

顺带一提，v2ex 贴代码可以用 gist

[leopanhf]

我觉得楼主其实不太理解 yield 吧？？