（递归和循环）#10 斐波那契数列
一、斐波那契数列
定义：
n = 0 , f(n) = 0
n = 1 , f(n) = 1
n > 1 , f(n) = f(n-1) + f(n-2)
思考与记录
本题可用递归或循环方法求解，但递归时间复杂度高，有很多重叠部分，并且数字大时容易造成堆栈溢出。一般循环方法比较好。还有第三种方法基于矩阵乘法实现，虽然用的很少，但是解答思路算作一种积累。
二、跳台阶
我们可以将n级台阶的跳法，看做是n的f(n)函数
当 n = 1 时，只有一种跳法
当 n = 2 时，有两种跳法
当 n > 2 时, 第一次跳有两种选择：跳一级台阶时，则还剩n-1，后面则为f(n-1)：跳二级台阶时，则还剩n-2，后面则为f(n-2)
由此可以看出n级台阶的总数为f(n) = f(n-2) + f(n-1)，实际为斐波那契数列问题
三、变态跳台阶
总的跳法，最后用数学归纳法，可以证明f(n) = 2**(n-1)次
四、矩形覆盖
同跳台阶，都是斐波那契数列问题
