斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为兔子数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
斐波那契数列是一个非常神奇的数列，在我们生活中的各处都有。比如：当数列趋近于无穷大的时候，斐波那切数列的前一项与后一项的比值就是黄金分割比：0.618……
自然界的斐波那切数列（百度百科搬的）.png
如果我们第一项多一个0（哨兵的作用）出来，那么斐波那切数列就是： 0、1、1、2、3、5、8、13、21、34、……
我们可以看到，这个数列的得到方式是从第三项开始，每一项都是前两项的和：
从第三项开始每一项都是前两项的和.png
斐波那切数列
那么我们怎么得到这个数列呢？我们现在已知的就是，数列的第一项是 0，第二项是 1，之后每一项是前两项的和。
我们利用递归的思想，首先找出递归的递归条件。要想得到数列的第 n 项，我们就需要知道数列的第 n - 1 项和数列的 n - 2 项。因为从第三项开始，每一项都是前两项的和，也就是说：
第n项的值的取得.png
何为 递归，其实 递 跟 归 是两个过程，先递后归。就像是电影院中你在看电影，漆黑一片。此时你想知道你坐的是第几排，你自己并不能直接的知道，那怎么办呢？你可以拍拍前面人的肩膀，问问他是第几排。此时漆黑一片，他也不知道自己是第几排，于是他也问他前面的人……。就这样，直到问道了第一排的人之后，由于第一排前面没有人了，所以第一排的同学知道自己是第一排，于是告诉后面一排的，我是第一排。后面的就知道了，自己是 1 + 1 = 2 排。于是再告诉自己后面的，后面的都陆续加1，等消息归来的时候，你就知道自己是在第几排了。
递
相对于这个数列来说，第 n 项是多少我们不知道，但是我们可以问问前面的，因为 第n项 = 第n-1项 + 第n-2项。于是n-1项和n-2项开始确认自己是几，他们也不知道，于是就再往前去找，直到找到第0个位置和第1个位置，终于知道答案了，第0个位置的数是0，第1个位置的数是1，首先就是利用 递 来找到可以确认自己这个位置的值是多少：
向前递的过程通过问前面等于多少来知道自己等于多少.png
归
当想要知道自己所在位置的值是多少的消息传递出去之后，我们就可以坐等回复了，这个回复回来的过程，就是 归 。随着各个位置都不知道自己的值是多少，消息就逐渐向前传递，直到传递到0、1的位置，总算遇到了明白人，0、1的位置说：我知道自己的值是多少，0、1 ! 于是，告诉位置2，我俩的值是0、1。于是位置2就知道了自己的值是 0 + 1 = 2；然后向后继续回复，告诉位置3，1的位置的值是1，2的位置的值是1。于是位置3就知道了自己的值是 1 + 1 = 2…… ：
向后回归的过程后面的等于前面两项的和.png
我们可以通过这种递归的方式来得到斐波那契数列的某个位置的值是多少，知道了每个位置的值是多少，我们就能得到指定长度的斐波那切数列！
得到斐波那切数列
我们可以根据以上递归的手段来得到整个斐波那切数列。具体的思想是，只要我们想办法去获取最后一个位置的值，那么，递归的整个过程就会得到整个数列中间位置的相应的值。因为要想得到最后位置的值，就必须先向前递，然后再回归，向前递的过程我们是为了能够找到知道自己值的位置，一但找到，这个回归的过程，我们就可以按照位置来记录下来回归过程所得到的从前向后的所有位置的值！我们将回归的每一步得到的值填入数组，最终当回归到最后一个的时候，我们就得到了整个斐波那切数列的数组！
代码实现
#coding:utf-8
array = []
def get_array(number):
# 基线条件
if number == 0:
# 回归的第一个位置
if len(array) == 0:
array.append(0)
return 0
if number == 1:
# 回归的第二个位置
if len(array) == 1:
array.append(1)
return 1
# 递归条件
n = get_array(number-1) + get_array(number-2)
# 依次按照回归的位置填入最终数列数组的相应位置
if number == len(array):
array.append(n)
return n
# 获取斐波那切数列
get_array(20)
print(array)
结果是：
长度为19的斐波那切数列.png
网友评论