面试经常遇到有人问菲波那切数列，并且问题也越来越刁钻，递归，非递归，尾递归等各种实现方式不一而足，已经不是最开始那个正经的斐波那契了。弄来弄去，还是要理解他的实现原理，以不变应万变。
数列形式：1,1,2,3,5,8,13·······求第n个数（n>=3）
这个数列的第n个数，等于前两个数的和，数列的前两个数为固定值，从第三个开始形成规律。现在说一下我对n的理解，很多网上的数列都是从0开始的，0,1,1,2,3······（n>=3），我觉着这个n的含义是第几个数，第0个数总感觉怪怪的，如果只是纯数学不管n的含义，那倒是随便。
正常递归：
public function test($n){ if($n<=0) return false; if($n==1||$n==2) return 1; return test($n-1)+test($n-2); }执行结果：n=35 结果：9227465 时间：16秒
尾递归：
function lastTest($n,$res1,$res2){ if($n==1) return $res1; return lastTest($n-1,$res2,$res1+$res2); } //调用 echo lastTest($n,1,1)执行结果：结果：9227465 时间：0.0000472069秒
先解释一下这俩个递归和结果为什么差距这么大：
第一：正常递归那个一次递归调用两次本身，类似于二叉树往下分裂，1生2,2生4，对于内存的消耗是指数级增长。而尾递归每次只是调用一次本身，内存消耗是线性增长。
第二：随便举个例子，求第6个数，正常递归：test(5)+test(4) 继续分裂 test(4)+test(3)+test(3)+test(2) 继续分裂：test(3)+test(2)+test(2)+test(2)+test(2) 继续分裂 test(2)+test(2)+test(2)+test(2)+test(2)+test(2)，可以看到，相同的值他要进行多次重复运算。尾递归：每次算完的res1+res2的值都会赋给下一次循环的的res2,然后将res2赋给res1，不会进行重复运算。
假如计算第6个数，res1每次计算等于上次的res2，res2每次计算等于上次的res1+res2：
尾递归执行演示 nres1res26115124233352581813我只计算到第35个数，是因为数再大正常递归已经超过php脚本默认执行时间30秒，再大很快内存就超了。这个算法要是运行在程序中简直就是毒瘤······
下边是非递归for循环（这两个for循环其实一样的就是一个递增一个递减）：
正常循环：
function test($n){ if($n<=0) return false; if($n==1||$n==2) return 1; $res1 = 1; $res2 = 1; for ($i=3; $i <=$n ; $i++) { $res = $res1+$res2; $res1 = $res2; $res2 = $res; } return $res; }执行结果：结果：9227465 时间：0.0000119209秒
也是正常循环（代码就改了一点点）：
function test($n){ if($n<=0) return false; if($n==1||$n==2) return 1; $res1 = 1; $res2 = 1; for ($i=$n; $i >=3 ; $i--) { $res = $res1+$res2; $res1 = $res2; $res2 = $res; } return $res; }执行结果：结果：9227465时间：0.0000119209秒
这俩个for循环的时间刚好一样，多点几次相差不大，我就用这两个时间了。尾递归那个很厉害了，竟然跟for循环一个量级，不过还是慢了4倍左右，多刷几次都是4倍左右，第一个就不说了。
所以这里边就牵扯到一个程序优化问题，面试的时候如果问你程序如何优化，我觉得尽量不用递归也算是很重要的一个优化手段。
