问个有关python的斐波那契的问题

Question

def fib1(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib1(n-1) + fib1(n-2)
 
 print fib1(7)

问题是：为什么输入7算出来的是13而不是11，(n-1)+(n-2)不是等于（7-1）+（7-2）吗？13是怎么来的
贴主说fib1的慢，就是因为每次都要计算前面已经算过的项目.这里将上述算法进行稍微改进。怎么看出这段程序会计算已经算过的项目？

def fib3(n):
    a, b = 0, 1    
for i in range(n):
    a, b = b, a+b
return a    

据说这段会比上面的快，特别是n很大的时候，这段会快很多。为什么这段会快呢？大神解答下

n = int(raw_input())
    if n==0:
        print '0'
    elif n==1:
        print '1'
    else:
        m = (n-1) + (n-2)
    print m

这段和第一段有哪里不一样，为什么这段计算结果不一样

Answer 1

第一第三问不予回答，自行去恶补 python 语法

---

第二问：

因为前者是递归调用，调用栈如下：

fib(7) --> fib(6) --> fib(5) --> fib(4) --> fib(3) --> fib(2) --> fib(1) --> fib(2) --> fib(3) --> fib(4) --> fib(5) --> fib(6) --> fib(7)

明眼人都看出有多慢。更何况没有尾递归优化。

而后者，只是从1循环到7，计算次数少了很多。

Answer 2

题主你太逗了，这个是递归

fib1(7) 不是 （7-1）+（7-2）

  fib1(7)
= fib1(6) + fib1(5)
= fib1(5) + fib1(4) + fib1(4) + fib1(3)
= fib1(4) + fib1(3) + fib1(3) + fib1(2) + fib1(2) + fib1(1)
= ...

Answer 3

第一段

def fib1(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib1(n-1) + fib1(n-2) #返回 调用函数
 
 print fib1(7) 

这段函数使用递归进行斐波那契的求值，返回 fib1(6) + fib1(5) 那 fib1(6)和 fib1(5)的 值会继续反复调用函数本身进行计算，直到求出结果为止。而你后面的

n = int(raw_input())
    if n==0:
        print '0'
    elif n==1:
        print '1'
    else:
        m = (n-1) + (n-2)
    print m

其中区别，自然不用多说了吧，既然说到了递归，第二段代码则是使用了循环，该问题的效率问题可见上面回答，但递归和循环的效率问题不敢妄自回答，自行 Google。