python 输出斐波那契数列

斐波那契数列 

 1、非递归算法

def fun(n):
    i= 0
    while (i <= n):
        if i<1:
            print(i)
            a = 0
            b = 1
        else:
            c = a + b
            print(c)
            a = b
            b = c
        i = i + 1

fun(30)

时间复杂度 O(n)

2、递归算法

def fun(n):
    if(-1<n <= 1):
        return (n)
    elif(n >1):
        return (fei(n-2) + fei(n-1))

def out(n):
    i = 0
    while( i < n ):
        print(fun(i))
        i += 1

out(30)

时间复杂度 O(2ⁿ)  

斐波那契数列