斐波拉契数列递归实现与优化

今天看到一道面试题，优化一个函数。 ``` function fei($n) { if ($n == 1 || $n == 2) { return 1; } return fei($n - 1) + fei($n - 2); } ``` 起初不知道这个函数的作用，后面查了一下才知道。这个函数可以求大名鼎鼎的“斐波拉契数列”。 返回到正题上，先说说什么是<font color="#ff0000">递归</font>。 递归有<font color="#ff0000">四大原则</font>。 1\. 基准情形： 必须有某些基准情形，它无需递归即可解出。 2\. 不断推进： 对于需要递归求解的情形，每次递归调用都必须使得求解状况朝着基准情形推进。 3\. 设计法则： 假设所有的递归调用都能运行。 4\. 合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性工作。 其中第四点在递归的效率中至为关键。这是为什么用递归实现斐波那契数列的常规方法时效率很低的原因，而在二叉树中表现相当优良的原因！ 什么是 斐波那契数列 又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)，即从第三项开始每一项都等于前面两项的和。 <div></div>``` global $n1; function fei($n){ $GLOBALS['n1']++; if($n==1 || $n==2){//基准情形，法则1 return 1; } return fei($n-1) + fei($n-2); //通过调用自身，不断推进直到达到基准情形，法则2,3 } ``` 通过观察上面的代码，我们发现一个问题，当给定一个数N时，需要先计算N-1 和N-2的情况，但是在计算N-1时同样要用计算N-2的情况，每个递归调用都触发另外两个递归调用，而这两个调用的任何一个又将调用另外连个递归调用，这样冗余计算的增量是非常快的，例如图：  再计算 fib(5)时，需要先求fib(4)和fib(3)， 而求fib(4)时又要求fib(3)和fib(2)以此类推这样就做了大量重复计算造成了不必要的浪费，如果我们能把fib(3),fib(2),fib(1)计算好的数据先存起来，下次需要计算时直接调用就可以省去大量的重复计算，因而有了下面的优化方式： ``` global $n2; function fei2($a,$b,$n){ $GLOBALS['n2']++; if($n>2){ return fei2(intval($a+$b),$a,$n-1); //将本次计算的结果和上次计算的结果作为参数传入下一次计算中，以减少重复计算。第四法则 } return $a; } ``` 代码执行效果：  同时求第十位数值，未优化的递归函数执行了109次，而优化后的仅仅执行了9次，  并且随着所求位数的增大执行数的差别会成几何倍的速度增加。