您的位置:首页 > 编程学习 > > 正文

用php递归函数实现阶乘的计算(php求斐波那契数的两种实现方式递归与递推)

更多 时间:2021-10-23 10:27:23 类别:编程学习 浏览量:1036

用php递归函数实现阶乘的计算

php求斐波那契数的两种实现方式递归与递推

本文实例讲述了php求斐波那契数的两种实现方式。分享给大家供大家参考,具体如下:

斐波那契数,亦称之为斐波那契数列(意大利语: Successione di Fibonacci),又称黄金分割数列、费波那西数列、费波拿契数、费氏数列,指的是这样一个数列: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

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • //使用递归方式求斐波那契数
  • public function fb($n){ //
  •     if( $n <=2){
  •       return 1;
  •     }else{
  •       return fb($n-1) + fb($n-2);
  •     }
  • }
  • 2使用递推方法。

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • public function fb2($n){ //
  •     if( $n <=2){
  •       return 1;
  •     }
  •     $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),实测代码如下。

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • /**性能测试。*/
  • function bench_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());
  • echo  bench_profile($s )."<br/>";
  •   echo fb(35); //使用递归 耗时 40.925 sec  每往上一个数约慢两倍
  • echo bench_profile($s )."<br/>";
  • //使用递推算法。
  • $s = explode(' ',microtime());
  • echo  bench_profile($s )."<br/>";
  •   echo fb2(35); //使用递推 时间极短。
  • echo bench_profile($s )."<br/>";
  • 总结:使用递归算法,到求第100 个斐波那契数 时会卡到机器跑不动,而使用递推算法,几乎不费时间。

    算法复杂度是非常重要的概念,也是区分程序员的一把好尺子。

    希望本文所述对大家PHP程序设计有所帮助。

    原文链接:https://blog.csdn.net/mu_rain/article/details/80240296

    您可能感兴趣