對遞歸和迭代的效率的思考和分析

tolerious 發布于2019-06-28 18:33 / 1228人閱讀

摘要：問題斐波那契數列的計算有如下一個數列，，其規則是前兩個已知即和，從第個開始，其值為其左邊兩個值的和此數列稱為斐波那契數列。

問題

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

遞歸思想來解決：

遞歸的本質：函數在其內部調用自身

解決問題時可以將其分拆成若干個小步驟，大問題的解決方法與小步驟方法一致，定義求問題的函數，在需要的位置調用函數即可。

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

思考問題：
1.遞歸：

找入口：

找出口：

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

不可以 return結束函數的調用

需要返回給下次遞歸調用使用

迭代思想來解決

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

結論：迭代的運行效率比遞歸高很多，能用迭代解決就別用遞歸，也就是說先考慮迭代再考慮遞歸。

云服務器 GPU云服務器對人工智能的思考數據的表示和分析數據的統計和分析云服務器和挖礦的區別 1對1服務

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/28408.html

對遞歸和迭代的效率的思考和分析

摘要：問題斐波那契數列的計算有如下一個數列，，其規則是前兩個已知即和，從第個開始，其值為其左邊兩個值的和此數列稱為斐波那契數列。問題斐波那契數列的計算：有如下一個數列：1，1, 2, 3, 5, 8, 13, 21，....... 其規則是：前兩個已知（即1和2），從第3個開始，其值為其左邊兩個值的和（此數列稱為斐波那契數列）。定義一個函數，該函數可以求出該數列的任意第n個數的值。遞歸...

codeGoogle 2019-08-22 15:26 評論0 收藏0
【C語言】玩轉遞歸——學好遞歸，你需要掌握的知識！

摘要：所以，遞歸在編程中同樣是很重要的一個知識點。舉個例子用遞歸實現求第個斐波那契數。總結起來四個字大事化小繼續舉斐波那契數的例子三遞歸是怎樣運行的我們通過一道題目來講解。 ...

Donne 2021-09-09 09:33 評論0 收藏0
【零基礎趣學C語言】- 史上最全C語言函數詳解（萬字圖文+代碼演示+圖解）

摘要：語言在設計中考慮了函數的高效性和易用性兩個原則。在語言中，最常見的當屬函數了。以上就是一個函數，它被稱為語言的入口函數，或者主函數。例如和都是函數名。形式參數當函數調用完成之后就自動銷毀了。 ...

468122151 2021-11-24 09:39 評論0 收藏0
JavaScript中的算法（附10道面試常見算法題解決方法和思路）

摘要：中的算法附道面試常見算法題解決方法和思路關注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程技能和文化契合度。值得記住的數組方法有和。一個好的解決方案是使用內置的方法。 JavaScript中的算法（附10道面試常見算法題解決方法和思路）關注github每日一道面試題詳解 Introduction 面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程...

Cruise_Chan 2019-08-26 10:22 評論0 收藏0
Python | 遞歸

摘要：那假如我們用遞歸來描述這種情況呢定義基本情況其它情形所以在上述求和中的定義又用到了自己本身的定義，這就構成了遞歸。說起遞歸，我覺得其實大部分人應該是不陌生的，遞歸廣泛存在于生活中。比如： showImg(https://segmentfault.com/img/remote/1460000007420204?w=294&h=450); The woman in this image ...

qieangel2013 2019-07-31 10:52 評論0 收藏0