假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。
问题分析
我们不妨拿新出生的1对小兔子分析：
第1个月，小兔子①没有繁殖能力，所以还是1对。
第2个月，小兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了1对小兔子②，于是这个月共有2（1+1=2）对兔子。
第4个月，兔子①又生了1对小兔子③。因此共有3（1+2=3）对兔子。
第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤。共有5（2+3=5）对兔子。
第6个月，兔子①②③各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8（3+5=8）对兔子。
…
可以发现一个有趣的规律，第三个月开始：当月的兔子数=上月兔子数+上上月的兔子数。
斐波那契数列如下：
1，1，2，3，5，8，13，21，34，…
递归式表达式：
算法设计
如下所示，用递归实现是不是很简单
public int recursion(int n){if(n < 1){return -1;}if(n == 1 || n == 2){return 1;}return recursion(n-1) + recursion(n-2);}
算法验证分析
一般下面三个方面来考算法：
算法是否正确？
写个方法来验证他
public static void main(String[] args) {Fib1 fib1 = new Fib1();for (int n = 1; n<10 ; n++){System.out.println(fib1.recursion(n));}}
执行结果：
毋庸置疑，算法是正确的。
算法的复杂度如何？
假设T(n)表示计算Fib1(n)所需要的基本操作次数，那么：
n=1时，T(n)=1
n=2时，T(n)=1
n=3时，T(n)=3；//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1)
因此，n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算，即：
n>2时，T(n)=T(n-1)+T(n-2)+1。
当趋n于正无穷市：
由于T(n) >= F(n) 所以这是一个指数级算法（时间、空间复杂度都是指数级的）。
如何改进？
由于 n >= 3 时 F(n) = F(n-1) + F(n-2)，所以可以使用迭代法，每次只需记录单前的值，和上次的值就行。
public int recursion(int n){if(n < 1){return -1;}if(n == 1 || n == 2){return 1;}//前两次的值都为1int s1 = 1;int s2 = 1;//m每次迭代记录单前的值，和上次的值。for(int i = 3; i <= n; i++){s2 = s2 + s1; //当前的值s1 = s2 - s1; //上次的值}return s2;}
该算法时间复杂度为 O(n),空间复杂度为O(1) 。
相关应用
黄金分割数随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值 0.6180339887……杨辉三角
力扣 118. 杨辉三角
