Python实现斐波那契数列的几种方法

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)

在程序中经常使用斐波那契数列来加深我们对一些结构的理解.下面我们就用python里面几种常见的结构来实现斐波那契数列:

1. 递归实现

递归主要是在函数内部调用自己.

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

递归实现的代码,非常容易理解,代码也非常简洁,缺点是效率较低

2. 迭代实现

迭代主要思想为: 循环代码中参与运算的变量同时是保存结果的变量,最常见的迭代为遍历列表

def fibonacci(n):
    i, num1, num2 = 0, 1, 1
    res = []
    while i < n:
        res.append(num1)
        num1, num2 = num2, num1 + num2 #num1,num2在参与运算的同时也在保存结果
        i = i + 1
    return res

这里的fibonacci函数实际上是定义了斐波拉契数列的推算规则，可以从第一个元素开始，推算出后续任意的元素，这种逻辑其实非常类似generator。而且,在每次函数运行都要保存一个列表，占内存.

3. 使用生成器来实现

    生成器是一个特殊的程序，可以被用作控制循环的迭代行为，python中生成器是迭代器的一种，使用yield返回值函数，每次调用yield会暂停，而可以使用next()函数和send()函数恢复生成器。

　　生成器类似于返回值为数组的一个函数，这个函数可以接受参数，可以被调用，但是，不同于一般的函数会一次性返回包括了所有数值的数组，生成器一次只能产生一个值，这样消耗的内存数量将大大减小，而且允许调用函数可以很快的处理前几个返回值，因此生成器看起来像是一个函数，但是表现得却像是迭代器

def fibonacci(n):
    i, num1, num2 = 0, 1, 1
    while i < n:
        yield num1
        num1, num2 = num2, num1 + num2
        i = i + 1

在这里返回值不再是一个列表,而是一个生成器.可以通过for in  或者 next()来取值

res = fibonacci(5)
fbn = [i for i in res]