對(duì)遞歸和迭代的效率的思考和分析

codeGoogle 發(fā)布于2019-08-22 15:26 / 3495人閱讀

摘要：?jiǎn)栴}斐波那契數(shù)列的計(jì)算有如下一個(gè)數(shù)列，，其規(guī)則是前兩個(gè)已知即和，從第個(gè)開(kāi)始，其值為其左邊兩個(gè)值的和此數(shù)列稱為斐波那契數(shù)列。

問(wèn)題

斐波那契數(shù)列的計(jì)算：有如下一個(gè)數(shù)列：1，1, 2, 3, 5, 8, 13, 21，....... 其規(guī)則是：前兩個(gè)已知（即1和2），從第3個(gè)開(kāi)始，其值為其左邊兩個(gè)值的和（此數(shù)列稱為斐波那契數(shù)列）。定義一個(gè)函數(shù)，該函數(shù)可以求出該數(shù)列的任意第n個(gè)數(shù)的值。

遞歸思想來(lái)解決：

遞歸的本質(zhì)：函數(shù)在其內(nèi)部調(diào)用自身

解決問(wèn)題時(shí)可以將其分拆成若干個(gè)小步驟，大問(wèn)題的解決方法與小步驟方法一致，定義求問(wèn)題的函數(shù)，在需要的位置調(diào)用函數(shù)即可。

    function fibonacci($n){
      //找出口：什么時(shí)候結(jié)束遞歸的調(diào)用
      if($n==! || $n==2) return 1;
      
      //計(jì)算其他項(xiàng)
      //找入口：什么時(shí)候開(kāi)始遞歸調(diào)用
      return fibonacci($n-1)+fibonacci($n-2);
      
      /**思考
      *return是否可以使用echo替換
      *不可以，因?yàn)閞eturn  結(jié)束函數(shù)的調(diào)用
      *需要返會(huì)給下次遞歸調(diào)用使用
      **/
    }
    $start=microtime(true);//開(kāi)始計(jì)時(shí)
    echo fibonacci(35);
    $end=microtime(true);//函數(shù)調(diào)用結(jié)束在計(jì)時(shí)
    echo "計(jì)算耗時(shí)".($end-$start)."秒";//4.9秒
    //遞歸每次調(diào)用時(shí)，沒(méi)有立即結(jié)束函數(shù)的調(diào)用，內(nèi)存沒(méi)有釋放，等到后面計(jì)算出結(jié)果，才從后面開(kāi)始釋放內(nèi)存

思考問(wèn)題：
1.遞歸：

找入口：

找出口：

2.return是否可以使用echo替換

不可以 return結(jié)束函數(shù)的調(diào)用

需要返回給下次遞歸調(diào)用使用

迭代思想來(lái)解決

    function fibonacci($n){
      
      if($n==1 ||$n==2) return 1;
      
      //其他項(xiàng)
      //第三項(xiàng)-->
      //假設(shè)求第七項(xiàng)，從第三項(xiàng)考試逐個(gè)計(jì)算
      //本次計(jì)算作為下次計(jì)算的條件使用
      
      //定義初始條件
      //前兩項(xiàng)作為基本條件
      $first=1;
      $secont=2;
      
      for($i=3;$i<=$n;$i++){
        //之間兩項(xiàng)之和
        $res=$first+$second;
        //為后續(xù)計(jì)算做準(zhǔn)備
        //下次計(jì)算的第一項(xiàng)來(lái)自本次計(jì)算計(jì)算的第二項(xiàng)
        $first=$second;
        //下次計(jì)算的第二項(xiàng)來(lái)自本次計(jì)算的結(jié)果
        $second=$res;
      }
      //循環(huán)結(jié)束   得到結(jié)果
      return $res;
    }
$start=microtime(true);
echo fibonacci(135);
$end=microtime(true);
echo "計(jì)算耗時(shí)：".($end-$start);//4.315秒，比遞歸效率高幾千萬(wàn)倍

結(jié)論：迭代的運(yùn)行效率比遞歸高很多，能用迭代解決就別用遞歸，也就是說(shuō)先考慮迭代再考慮遞歸。