前言前段时间遇到了一个常规的递归方法来优化斐波那契数列的计算，但是没有及时想到好的方法，后来搜索了相关的方法.资料总结了多种计算方案，分享出来和大家一起交流学习。什么是斐波那契数列？“兔子数列”指的是这样一个数列：1,1,2,3,5,8,13,21,34,...在数学中，斐波那契数列递归推导如下定义：F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n≥3,n∈N*)。知道了斐波那契数，那么我们就要用各种不同的方法来计算得到第N个斐波那契数。普通递归是最常规的方法，可以直接按照定义F(n)=F(n-1)+F(n-2)递归计算，但是性能是最低的。/***普通递归*@paramint$n*@returnint*/functionfib($n=1){//低阶处理if($n<3){return1;}//递归计算前两位returnfib($n-1)+fib($n-2);}递归优化从上面的递归方法可以看出，进行了大量的重复计算，性能极差。N越大，计算量就很可怕。是的，那么，既然重复计算会影响性能，那么优化就从减少重复计算入手，也就是把之前计算的存起来，这样就避免了过多的重复计算，优化了递归算法。/***递归优化*@paramint$n*@paramint$a*@paramint$b*@returnint*/functionfib_2($n=1,$a=1,$b=1){if($n>2){//存储前一位，优化递归计算returnfib_2($n-1,$a+$b,$a);}return$a;}memoization从下到上迭代计算斐波那契数列子问题并存储计算值，通过计算值进行计算。使用for循环减少递归带来的重复计算问题。/***自底向上记忆*@paramint$n*@returnint*/functionfib_3($n=1){$list=[];for($i=0;$i<=$n;$i++){//从低位到高位依次存入数组if($i<2){$list[]=$i;}else{$list[]=$list[$i-1]+$list[$i-2];}}//返回最后一个数，即第N个数return$list[$n];}自下而上迭代最低位初始化赋值，从低位到高位迭代计算使用for，从而得到第N个数。/***从下往上迭代*@paramint$n*@returnint*/functionfib_4($n=1){//低阶处理if($n<=0){return0;}如果($n<3){返回1;}$a=0;$b=1;//循环计算for($i=2;$i<$n;$i++){$b=$a+$b;$a=$b-$a;}return$b;}公式方法通过理解斐波那契数列与黄金比例的关系，利用黄金比例计算第N个斐波那契数。/***公式方法*@paramint$n*@returnint*/functionfib_5($n=1){//黄金比例$radio=(1+sqrt(5))/2;//Fib序列与黄金比例关系的计算$num=intval(round(pow($radio,$n)/sqrt(5)));return$num;}无敌无敌法，我就不多说了，大家明白，但是不要轻易尝试.../***无敌无敌法*@paramint$n*@returnint*/functionfib_6($n=1){//列出30个数字$list=[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597、2584、4181、6765、10946、17711、28657、46368、75025、121393、196418、317811、514229、832040、1346269]；return$list[$n];}最后写了几个解决方案，如果有不对的地方，请大家指出，我会及时修改。如果大家还有其他的计算方法，欢迎分享出来一起交流学习，谢谢！
