JavaScript實現斐波那契數列的方法有幾種

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

題目介紹

??斐波那契數列又被稱為黃金分割數列，指的是這樣的一個數列：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是正整數)，請使用js實現斐波那契函數。

方法1：遞歸實現

??由題目中的遞推受到啟發，可以通過遞歸的方式去實現，代碼如下：

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

優點：代碼比較簡潔易懂；
缺點：當數字太大時，會變得特別慢，原因是在計算F(9)時需要計算F(8)和F(7)，但是在計算F(8)時要計算F(7)和F(6)，這里面就會重復計算F(7)，每次都重復計算會造成不必要的浪費，所以這種方法并不是很好。

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

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

function fibonacci(n){
        if(n < 0) throw new Error('輸入的數字不能小于0');
        let arr = [0,1];//在外部函數中定義數組，內部函數給數組添加值
        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;//將每次遞歸得到的值放到數組中保存
            return data;
        }
        return calc(n);
    }

方法3：直接使用數組實現（動態規劃）

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

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

方法4：直接使用變量實現

??相校于使用數組的方式去存放，使用變量的方式就不會那么浪費內存了，因為總共只會有3個變量，但是也有缺點，它只能保存最后計算的值以及前兩個值，以前的值會被替換掉。

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

        if(n < 0) throw new Error('請輸入大于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;
    }

總結

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

以上便是JavaScript實現斐波那契數列的方法，雖然從篇幅上看很復雜，但是示例代碼非常詳細且容易理解，如果想了解更多相關內容，請關注億速云行業資訊。