博客

Python输出斐波那契数列【递归、迭代】

首先 斐波那契数列的定义是什么？

斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 2，n ∈ N*）

接下来我们使用Python程序代码

第一种解决方法：迭代

完整代码：

a = [1, 1]
max = 20
for i in range(2, max):
    a.append(a[i - 1] + a[i - 2])

print(a)

运行结果：

第二种解决方法：递归

完整代码：

def fei(day):
    if day < 3:
        return 1
    return fei(day - 1) + fei(day - 2)


for i in range(1, 21):
    print(fei(i), end=' ')

运行结果：

总结

迭代和递归本不是同一种编程思想，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量值

迭代虽然要简单一些，但是可读性差；同样的递归看似更加“美丽”，但是在这美丽的外表下却也有致命缺陷，那就是占用空间大，且随着递归的层次变化，所耗费的时间会比迭代更加的长，所以并不适合深层次计算。