JavaScript实现斐波那契数列的四种办法介绍（代码）-百分百源码网

JavaScript实现斐波那契数列的四种办法介绍（代码）

发布时间：09/01 来源：未知浏览：关键词：

本篇文章给大家带来的内容是关于JavaScript实现斐波那契数列的四种办法介绍（代码），有必然的参照价值，有需要的伴侣可以参照一下，但愿对你有所帮忙。

前几天面试被问到了斐波那契数列的实现乃至优化的问题，当时现场卡了挺久的，此刻停止一下总结（使用js实现）。

问题介绍

??斐波那契数列又被称为黄金分割数列，指的是这样的一个数列：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;
    }