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 <p> Advantages: The code is relatively simple and easy Understand; <br> 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. </p><h3 id="Method-Use-closure-to-save-each-recursion-value">Method 2: Use closure to save each recursion value</h3><p>  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: </p><pre class="brush:php;toolbar:false">function fibonacci(n){
        if(n <h3 id="Method-Directly-using-array-implementation-dynamic-programming">Method 3: Directly using array implementation (dynamic programming) </h3><p> 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. </p><pre class="brush:php;toolbar:false">function fibonacci(n){
        var a = [0,1,1];
        if(n = 3){
            for(var i=3;i<h3 id="Method-Directly-use-variables-to-implement">Method 4: Directly use variables to implement</h3><p> 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. </p><pre class="brush:php;toolbar:false">function fibonacci(n){
        var pre = 0;//表示前一个值
        var cur = 1;//表示后一个值
        var data;//表示当前值

        if(n  2){
            for(var i=2;i<h2 id="Summary">Summary</h2><p>   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. </p><p></p>

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!