斐波那契数列：
1、1、2、3、5、8、13、21、……
简单说，就是前两项的和是第三项的值。
1、求第N个斐波那契数的值（非递归）
//斐波那契数列int fun(int n){int a = 1, b = 1, c = 1;for (int i = 3; i <= n; i++){c = a + b;a = b;b = c;}return c;}//O(n) S(1)
2、求第N个斐波那契数的值（递归）
很简单，求第N个斐波那契数，我们需要求第n-1和n-2个斐波那契数，而求第n-1个斐波那契数，我们需要求第n-2和n-3个斐波那契数…以此类推，比如求第5个斐波那契数如图：
递归出口很显然，当n = 1或者2时，fib(n) = 1,所以递归出口便是n <= 2 return 1；
int fib(int n){if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);}//O(2^n) S(n)
此递归算法时间复杂度为O(2^n) ，空间复杂度为S(n)。由上图可见时间复杂度高是因为f(n)的值被多次计算，那怎么将递归的O(2^n)改成O(n)?
可见，当我们使f(n)只被计算一次，那么时间复杂度自然降为O（n）
3、优化后的斐波那契数列递归算法
尾递归法：通过两个变量保存计算值，传递给下一次进行计算，递归的过程中也是根据n值变化逐步重复运算。
//怎么将递归的O(2^n)改成O(n)?int fib(int n, int a, int b){if (n <= 2){return b;}else{return fib(n-1, b, a+b);}}int fib(int n){int a = 1, b = 1;return fib(n, a, b);}
