云課堂作業---斐波那契數列的引發的思索

UCloud 發布于2019-08-21 17:42 / 2850人閱讀

摘要：閉包尾遞歸循環迭代實現使用方式，主要是看實現思想從圖中我們可以很明顯的看出，使用尾遞歸計算斐波那契數列性能完勝直接遞歸和閉包，特別是當數值比較大的時候，尾遞歸的作用就越明顯。

前端微專業JavaScript有一道題目是求斐波那契數列的，一開始沒想很多，覺得實現功能自己已經很棒棒了（逃）
后面有同學討論直接遞歸特別耗費時間，開始考慮使用閉包，看我們討論的不亦樂乎的大佬也發話了，指點我們這兩種方式都不是很好，讓我們去看一下尾遞歸(實話說，我早就還給大學老師了=。=)
言歸正傳，開始干活。
------------------------------假裝我是分割線---------------------------
如題：

我最開始的解法是直接遞歸

function sum(n){
        if(n==0){
            return 0;
        }else if(n==1) {
            return 1;
        }
        else{
            return (arguments.callee(n-1)+arguments.callee(n-2));
           }
      }

這個實現簡單明了就是執行速度太慢了，因為編譯器是以如下方式進行計算的（例如計算Fib（6））：

Fib(6) = Fib(5) + Fib(4);
         = Fib(4) + Fib(3) + Fib(3) + Fib(2);
         = Fib(3) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = Fib(2) + Fib(1) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = 8

從上面的遞歸展開式可以看出Fib(4),Fib(3)都被計算了2次，而且遞歸函數以2的指數增長。所以當計算到30時就變得非常慢。(當然這都是后話了，我開始哪里知道這么多~)

后來群里同學說使用閉包會比直接遞歸快，那我就試著用了下閉包；

var sum    =(function (){
        return function(n){
            if(n==0 || n==1){
                return n;
            }else{
                return (sum(n-1)+sum(n-2));
               }
        }})();

使用了閉包確實感覺自己吊了一點啊，整個人都萌萌噠，而且后面測試速度也證實了比我原來的好一點。

后面，大佬指導說直接遞歸和閉包都很影響性能（我實現出來都很不容易呀），告訴我們使用尾遞歸會極大的提高性能，好吧，我只好去查查什么是尾遞歸了，看了幾個demo我寫了如下代碼：

    function sum(n,a,b){
             if (n ==0 ){
                return a;
             }
             else{
                 return sum(n-1, b, a +b);
            }
    }

具體執行過程我后面會給傳送門，我也是從那看到的。

---------------------------------分割線又來了--------------------------------

接下來我們來對比一下代碼性能

直接遞歸的耗時

分別比較了n為30,33,35的值時候的耗時，圖中有兩個數字，上面的是計算得到的斐波那契數列結果，下面是耗時，單位是毫秒。

閉包

尾遞歸

循環

迭代實現

//使用Java方式，主要是看實現思想
public static long fibo3(long n){    
    if(n<2) return n;    
    long pre=1,prepre=1,ret=0;    
    for(int i=2;i
從圖中我們可以很明顯的看出，使用尾遞歸計算斐波那契數列性能完勝直接遞歸和閉包，特別是當數值比較大的時候，尾遞歸的作用就越明顯。循環的方式性能也很好，其實實現斐波那契數列方式多種多樣，真的只是你想不到而已，好了，收工吃飯！
最后想看尾遞歸算法的可以看這里：尾遞歸實現斐波那契

云服務器 GPU云服務器波那契數列簡單的html作業 asp net的作業引發了

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

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

算法記錄 >> 斐波那契數列

摘要：今天去面試筆試題斐波那契數列實現，雖然很簡單?；貋硐胂爰热凰惴ㄟ@么重要那就從這個開始來記錄自己的算法庫吧。在數學上，斐波納契數列以如下被以遞歸的方法定義，，。斐波拉契算法規律很簡單，，觀察下數列值就很容易總結出來了。一、寫在前面算法這塊對于大多數程序員（包括我）來說可能都是一個薄弱的地方，如何彌補尼？每個人都知道那就是學習、特別是算法沒有任何捷徑可走。在這記錄平時自己工作和生...

robin 2019-08-16 17:52 評論0 收藏0
太原面經分享：如何用js實現返回斐波那契數列的第n個值的函數

摘要：那其實這個問題還可以換個問法實現一個函數，輸入一個數字能返回斐波那契數列的第個值。文章預告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面，歡迎關注面試攢經驗，lets go！值此高考來臨之際，閑不住的我又雙叒叕出發去面試攢經驗了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...

Galence 2019-08-26 12:01 評論0 收藏0
js實現斐波那契數列

摘要：實現斐波那契數列斐波那契數列最大數斐波那契數列由和開始之后的斐波那契數列系數就由之前的兩數相加。換個寫法，用箭頭函數最大數斐波那契數列由和開始 js實現斐波那契數列 // 斐波那契數列 let max=10000; // 最大數 let arr=[0,1]; // 斐波那契數列由 0 和 1 開始 // 之后的斐波那契數列系數就由之前的兩數相加。 ...

notebin 2019-08-23 15:42 評論0 收藏0
使用js實現斐波那契數列

摘要：前言前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結使用實現。題目介紹斐波那契數列又被稱為黃金分割數列，指的是這樣的一個數列，它有如下遞推的方法定義是正整數，請使用實現斐波那契函數。前言前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結（使用js實現）。題目介紹 ??斐波那契數列又被稱為黃金分割數列，指...

alexnevsky 2019-08-26 13:36 評論0 收藏0
js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0