这节课试图了解一下 斐波那契（Fibonacci）数列（黄金分割数列）的递归实现，作为一个例子。
斐波那契（Fibonacci）数列的脑补链接
斐波那契提出一个著名的兔子繁殖问题：
如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生后的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，50个月后会有多少对兔子？
在第一个月时，只有一对小兔子，过了一个月，那对兔子成熟了，在第三个月时便生下一对小兔子，这时有两对兔子。再过多一个月，成熟的兔子再生一对小兔子，而另一对小兔子长大，有三对小兔子。如此推算下去，我们便发现一个规律（表格省略）：
由此可知，从第一个月开始以后每个月的兔子总数是：1,1,2,3,5,8,13,21,34,55,89,144,233...。若把上述数列继续写下去，得到的数列便称为斐波那契数列。数列中每个数便是前两个数之和，而数列的最初两个数都是1。
用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就由之前的两数相加。首几个费波那契系数是（OEIS A000045）：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
特别指出：0不是第一项，而是第零项。——《维基百科》
斐波那契（Fibonacci）数列的迭代实现：
先用数学函数来定义
f(n) :
当n=1 f(n)=1
当n=2 f(n)=1
当n=3 f(n)=2
当n=4 f(n)=3
…
推理：n>2时数列可表达为： f(n)=f(n-1) + f(n-2)
练习：假设我们需要求出经历了20个月后，总共有多少对小兔崽子
普通迭代写法：（实在不会写！！！不知是数学盲还是脑残。。。。）
#知道逻辑但不会写代码，打击太大了。。deffab(n):
n1= 1#第一个月1n2 = 1#第二个月1n3 = 1#第三个月开始，初始化为1ifn < 1:#判断如果月份小于一那就没意义了。设置返回一个 -1 的错误，供后面调用PRint('输入有误')return-1while(n-2) >0:
n3= n2 + n1#从第三个月开始，第三个月等于第二个月和第一个月之和，赋值给n3n1 = n2#那么第一个月就等于现在的第二个月，也就是n2的值重新赋值给第一个月n2 = n3#同理，第二个月等于现在的第三个月，用n3的值重新赋值给第二个月n -= 1#重新赋值之后，循环次数-1returnn3#返回结果result= fab(20)ifresult != -1:print(‘总共有%d对小兔崽子诞生’ % result)
个人理解：迭代需要一个初始值，那么这里给了第一个月和第二个月的初始值，第三个月是前两个月相加，那么第三个月也有一个初始值，也就是2，当月份变化时，每一个迭代都会重新赋值，也就是说也有三个初始值，一个是当前月的值n3，一个是当前月-1的值即n2，还一个是当前月-2的值，即n1，那么n3就是最后要求的结果。
递归写法：
#Fibonacci数列递归写法：deffab(n):#判断n如果小于1返回错误信息ifn < 1:print('输入有误！')return- 1#如果没有下面这条if件句，程序将陷入死循环，为什么？？？？？？ifn == 1orn == 2:return1else:returnfab(n-1) + fab(n-2)
result= fab(20)ifresult != -1:print('总共有%d对小兔子诞生'%result)#我尝试用deffab(n):returnfab(n-1) + fab(n-2)print(fab(20))#结果返回一个死循环。#为什么要加上条件语句？如果单单是判断n<2的话，我赋给函数fab(20)，并不小于2，
#脑子实在转不过弯来。求明示！！！！！
递归的中心思想就是 分治思想！一个大问题解决不了，那么可以把大问题分解成若干小问题，把若干小问题解决了，那么大问题也就解决了。
但递归也有其缺陷，比如把上面的20改为35，然后运行它，结果发现，递归算法要等那么一秒钟才算出来，如果用迭代，那么结果就是秒出。所以递归要用在适当的位置适当的时机。