1202年，意大利数学家Leonardo Fibonacci提出了这样一个问题：在最佳条件下，一年里，一对兔子能繁殖多少对兔子？这个理论实验规定，母兔总是生下成对的兔宝宝，每对由一公一母组成。两只新生的兔子被安置在一个有围栏的院子里，然后让像正常兔子一样繁殖。长到一个月才能开始繁殖，所以第一个月只有一对兔子。在第二个月月底，母兔产下两只兔子。当第三个月到来时，原来的一对兔子又产了一对新生儿，而它们早期的后代则已经成年。此时便留下了三对兔子，其中两对将在下个月再生两对兔子。
每个月的兔子对数为：1，1，2，3，5，8，13，21，34，55，89，144。这个数列从第3项开始，每一项都等于前两项之和，这个数列被命名为斐波那契数列。如果取数列前两个元素为1，那么递推关系就是：f(n)=f(n-1)+f(n-2)。曾经有一度数学家们将0作为斐波那契数列的首项（或第0项）。
菲波拉契数列问题可以有两种方式实现： 递归算法、循环算法。
优点：代码简洁、清晰，并且容易验证正确性。
缺点：1、它的运行需要较多次数的函数调用，如果调用层数比较深，每次都要创建新的变量，需要增加额外的堆栈处理，会对执行效率有一定影响，占用过多的内存资源。
2、递归算法解题的运行效率较低。在递归调用的过程中系统为每一层的返回点、局部变量等开辟了栈来储存。递归次数过多容易造成栈溢出等
注意：递归就是在过程或函数里调用自身；使用递归策略时要注意的几个条件： 1、必须有一个明确的递归结束条件，称为递归出口。 2、递归需要有边界条件、递归前进段和递归返回段。 3、当边界条件不满足时，递归前进。当边界条件满足时，递归返回。
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
题目1：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
分析：第1个月： 1对兔子 ， 第2个月 1对兔子。
第3个月：新生一对兔子，共有2对兔子，其中1对兔子年龄>=3,1对兔子年龄==1，简单表示为：1(3)/0(2)/1(1),括号外表示兔子数量，括号内数字表示兔子年龄。
第4个月：够3个月龄的兔子生一对，不够3个月的年龄+1(若达到3，可以生兔子), 1(3)/1(2)/1(1)，共3对兔子。
第5个月：有一对兔子刚刚达到3个月龄，加上已经达到3个月龄的，共有2对兔子可以生小兔子，2(3)/1(2)/2(1)，共5对兔子。
找规律，按月份列出兔子数量(多少对)：1,1,2,3,5..., 这是一个菲波拉契数列问题
题目2：青蛙跳台阶问题，一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？
分析：当n = 1， 只有1中跳法；当n = 2时，有2种跳法；当n = 3 时，有3种跳法；当n = 4时，有5种跳法；当n = 5时，有8种跳法；.......规律类似于Fibonacci数列: 1, 2, 3, 5, 8...
题目3：青蛙变态跳台阶问题，一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：先跳到n-1级，再一步跳到n级，有f(n-1)种；
先跳到n-2级，再一步跳到n级，有f(n-2)种；
先跳到n-3级，再一步跳到n级，有f(n-3)种；
........
先跳到第1级，再一步跳到n级，有f(1)种；
所以：f(n)=f(n-1)+f(n-2)+f(n-3)+···+f(1), f(n-1)=f(n-2)+f(n-3)+···+f(1), 推出f(n)=2*f(n-1)
