JavaScript實(shí)現(xiàn)斐波那契數(shù)列的方法有幾種

JavaScript實(shí)現(xiàn)斐波那契數(shù)列的方法有幾種？這篇文章運(yùn)用了實(shí)例代碼展示，代碼非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

題目介紹

??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個(gè)數(shù)列：1,1,2,3,5,8,13,21,34....，它有如下遞推的方法定義：F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n>=2,n是正整數(shù))，請(qǐng)使用js實(shí)現(xiàn)斐波那契函數(shù)。

方法1：遞歸實(shí)現(xiàn)

??由題目中的遞推受到啟發(fā)，可以通過遞歸的方式去實(shí)現(xiàn)，代碼如下：

function fibonacci(n){
        if(n < 0) throw new Error('輸入的數(shù)字不能小于0');
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

優(yōu)點(diǎn)：代碼比較簡(jiǎn)潔易懂；
缺點(diǎn)：當(dāng)數(shù)字太大時(shí)，會(huì)變得特別慢，原因是在計(jì)算F(9)時(shí)需要計(jì)算F(8)和F(7)，但是在計(jì)算F(8)時(shí)要計(jì)算F(7)和F(6)，這里面就會(huì)重復(fù)計(jì)算F(7)，每次都重復(fù)計(jì)算會(huì)造成不必要的浪費(fèi)，所以這種方法并不是很好。

方法2：使用閉包保存每次的遞歸值

??由方法1可知，使用普通的遞歸，會(huì)造成不必要的浪費(fèi)，所以我們首先想到的應(yīng)該是將每次產(chǎn)生的遞歸值保存下來，下次直接使用就行，代碼如下：

function fibonacci(n){
        if(n < 0) throw new Error('輸入的數(shù)字不能小于0');
        let arr = [0,1];//在外部函數(shù)中定義數(shù)組，內(nèi)部函數(shù)給數(shù)組添加值
        function calc(n){
            if(n<2){
                return arr[n];
            }
            if(arr[n] != undefined){
                return arr[n];
            }
            let data = calc(n-1) + calc(n-2);//使用data將每次遞歸得到的值保存起來
            arr[n] = data;//將每次遞歸得到的值放到數(shù)組中保存
            return data;
        }
        return calc(n);
    }

方法3：直接使用數(shù)組實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃）

??和方法2的思想類似，為了避免后續(xù)的重復(fù)計(jì)算，需要將計(jì)算過的值保存起來，我們可以直接使用數(shù)組進(jìn)行保存。

function fibonacci(n){
        var a = [0,1,1];
        if(n < 0) throw new Error('輸入的數(shù)字不能小于0');
        if(n >= 3){
            for(var i=3;i<=n;i++){
                a[i] = a[i-1]+a[i-2];
            }
        }
        return a[n];
    }

方法4：直接使用變量實(shí)現(xiàn)

??相校于使用數(shù)組的方式去存放，使用變量的方式就不會(huì)那么浪費(fèi)內(nèi)存了，因?yàn)榭偣仓粫?huì)有3個(gè)變量，但是也有缺點(diǎn)，它只能保存最后計(jì)算的值以及前兩個(gè)值，以前的值會(huì)被替換掉。

function fibonacci(n){
        var pre = 0;//表示前一個(gè)值
        var cur = 1;//表示后一個(gè)值
        var data;//表示當(dāng)前值

        if(n < 0) throw new Error('請(qǐng)輸入大于0的值！');
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n > 2){
            for(var i=2;i<=n;i++){
                data = pre + cur;
                pre = cur;
                cur = data;
            }
        }
        return data;
    }

總結(jié)

??其實(shí)大部分人在求斐波那契數(shù)列時(shí)想到的都是遞歸的方法，但是就其事件復(fù)雜度來看，不是一個(gè)好的方法，那么我們的優(yōu)化思路可能就是使用空間換換時(shí)間了，就是將遞歸產(chǎn)生的值保存下來，以免下次還要重復(fù)計(jì)算。

以上便是JavaScript實(shí)現(xiàn)斐波那契數(shù)列的方法，雖然從篇幅上看很復(fù)雜，但是示例代碼非常詳細(xì)且容易理解，如果想了解更多相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊。