Introduction to four methods of implementing Fibonacci sequence in JavaScript (code)

This article brings you an introduction to the four methods (code) of implementing the Fibonacci sequence in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. .

A few days ago, I was asked about the implementation and optimization of the Fibonacci sequence in the interview. The scene was stuck for a long time. Now I will summarize it (implemented using js).

Title introduction

 Fibonacci sequence is also called the golden section sequence, which refers to such a sequence: 1,1,2,3,5,8,13,21 ,34...., it has the following recursive method definition: F(1)=1,F(2)=1,F(n)=F(n-1) F(n-2)(n> =2, n is a positive integer), please use js to implement the Fibonacci function.

Method 1: Recursive implementation

Inspired by the recursion in the question, it can be implemented recursively. The code is as follows:

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

Advantages: The code is relatively simple and easy Understand;
Disadvantages: When the number is too large, it will become particularly slow. The reason is that when calculating F(9), you need to calculate F(8) and F(7), but when calculating F(8), you need to calculate F(7) and F(6), F(7) will be repeatedly calculated. Repeated calculation every time will cause unnecessary waste, so this method is not very good.

Method 2: Use closure to save each recursion value

 From method 1, we can see that using ordinary recursion will cause unnecessary waste, so the first thing we think of is to save each recursion value. The recursive value generated this time is saved and can be used directly next time. The code is as follows:

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        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);
    }

Method 3: Directly using array implementation (dynamic programming)

The idea is similar to method 2. In order to avoid For subsequent repeated calculations, the calculated values ​​need to be saved. We can directly use an array to save them.

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

Method 4: Directly use variables to implement

Compared with using arrays to store, using variables will not waste memory so much, because there will only be 3 variables in total. , but it also has disadvantages. It can only save the last calculated value and the first two values, and the previous values ​​will be replaced.

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

        if(n < 0) throw new Error(&#39;请输入大于0的值！&#39;);
        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;
    }

Summary

  In fact, most people think of the recursive method when calculating the Fibonacci sequence, but in terms of its event complexity, it is not a good method, then Our optimization idea may be to use space to exchange time, which is to save the values ​​generated by recursion to avoid repeated calculations next time.

The above is the detailed content of Introduction to four methods of implementing Fibonacci sequence in JavaScript (code). For more information, please follow other related articles on the PHP Chinese website!