php求斐波那契数的两种实现方式【递归与递推】
本文实例讲述了php求斐波那契数的两种实现方式。分享给大家供大家参考，具体如下：
斐波那契数，亦称之为斐波那契数列（意大利语：SuccessionediFibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列列由0和1开始，之后的斐波那契数列系数就由之前的两数相加。
1使用递归方法。 顺着思路去想，f(1)=1;f(2)=1;f(3)=f(2)+f(1) 【2】 f(4)=f(3)+f(2)3
//使用递归方式求斐波那契数
publicfunctionfb($n){//
if($n<=2){
return1;
}else{
returnfb($n-1)+fb($n-2);
}
}
2使用递推方法。
publicfunctionfb2($n){//
if($n<=2){
return1;
}
$t1=1;$t2=1;
for($i=3;$i<$n;$i++){
$temp=$t1;
$t1=$t2;
$t2=$temp+$t2;
}
return$t1+$t2;
}
最后，进行性能分析。
明显的可以预测，递归方法，每多一层，就要向下递归两次。约为O(2的N次方) 而递推算法为 O(n),实测代码如下。
/**性能测试。*/
functionbench_profile($starttime,$flag=''){
$endtime=explode('',microtime());
$thistime=$endtime[0]+$endtime[1]-($starttime[0]+$starttime[1]);
$thistime=round($thistime,3);
return$flag."-bench:".$thistime."sec";
}
//使用递归算法。
ini_set("max_execution_time",3600);
$s=explode('',microtime());
echobench_profile($s)."
";
echofb(35);//使用递归耗时40.925sec每往上一个数约慢两倍
echobench_profile($s)."
";
//使用递推算法。
$s=explode('',microtime());
echobench_profile($s)."
";
echofb2(35);//使用递推时间极短。
echobench_profile($s)."
";
总结：使用递归算法，到求第100个斐波那契数时会卡到机器跑不动，而使用递推算法，几乎不费时间。
算法复杂度是非常重要的概念，也是区分程序员的一把好尺子。
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。