斐波那契数列简称兔子数列，是一道非常高频的面试题。
为什么它如此受面试官们的欢迎？原因有三：
第一：这个题目的答案简单；
第二：区分度高，水平不同，写出的代码必然不同；
第三：这个题目的变种很多，比如说“上一个N台阶的楼梯，每次只能走一格或者二格，总共有多少种走法？“，不小心就能绕进去，但是归根结底就是一堆兔子怎么生；
斐波那契数列是什么？每一项都等于它前两项和的数列。
第一种解法：传统递归，性能在N>40的时候急剧下降。代码如下：
解法1 递归
第二种解法：迭代（动态规划思想）。不难看出该算法的时间复杂度是O(n) 。代码如下：
解法2 迭代
第三种解法：从数学公式的角度，利用特征方程、母函数来求解。时间复杂度是O(log(n))。代码如下：
解法3 组合数学公式
Math.pow函数的实现代码
自己实现Pow函数的思路，把要求解n次幂的n转换成二进制的形式，凡是二进制有1的位，都乘以对应次数的x的倍数，每次循环的时候处理n的二进制的一位，从最小的一位开始，看它最后一位如果能被2整除，就可以为它乘以对应x的倍数，0不做处理，最后去除最后一位，自此循环看最后一位是0还是1，重复上面的步骤。这样就能在x的n次方内求出，进而得出时间复杂度是log(n)。但是受系统的浮点数（操作系统的浮点运算相当耗时）的影响，切记加上一次Math.round进行取整操作。
第四种解法：矩阵的幂运算。
先来简单回顾一下线性代数的知识，方便理解解法幂运算。
矩阵乘法
矩阵乘法与矩阵的幂
解法4 矩阵运算
今天的学习结束，俗话说的好：“每天进步一点点，未来进步一大截！”
