JS Six ways to write Fibonacci sequence

Fibonacci number refers to the sequence of numbers 1, 1, 2, 3, 5, 8, 13, 21… In mathematics, the Fibonacci sequence is defined recursively as follows: F0=0, F1=1, Fn= FN-1 +Fn-2 (n>=2, n∈N*). In literal terms, the Fibonacci sequence starts with 0 and 1, and the coefficients of the Fibonacci sequence are added from the previous two numbers.

Common methods for calculating Fibonacci numbers fall into two broad categories: recursion and circulation.

recursive

Method one: ordinary recursion

Beautiful code and clear logic. For example, Fibonacci (4) + Fibonacci (3) is calculated when n is 5, and Fibonacci (3) + Fibonacci (2) is calculated when n is 4. Running Fibonacci (50) will cause the browser to feign dead, because recursion requires a stack and a large number runs out of memory

function fibonacci(n) {
    if (n == 1 || n == 2) {
        return 1
    };
    return fibonacci(n - 2) + fibonacci(n - 1);
}
fibonacci(30)
Copy the code

Method 2: Improve recursion – make the first two digits arguments to avoid double-counting

function fibonacci(n) {
    function fib(n, v1, v2) {
        if (n == 1)
            return v1;
        if (n == 2)
            return v2;
        else
            return fib(n - 1, v2, v1 + v2)
    }
    return fib(n, 1.1)
}
fibonacci(30)
Copy the code

Method 3: improved recursion – use the closure feature to store the result of the operation in an array, avoid double calculation

var fibonacci = function () {
    let memo = [0.1];
    let fib = function (n) {
        if (memo[n] == undefined) {
            memo[n] = fib(n - 2) + fib(n - 1)}return memo[n]
    }
    return fib;
}()
fibonacci(30)
Copy the code

Method four: improve recursion – extract the function function that stores the calculation result

var memoizer = function (func) {
    let memo = [];
    return function (n) {
        if (memo[n] == undefined) {
            memo[n] = func(n)
        }
        return memo[n]
    }
};
var fibonacci=memoizer(function(n){
    if (n == 1 || n == 2) {
        return 1
    };
    return fibonacci(n - 2) + fibonacci(n - 1);
})
fibonacci(30)
Copy the code

cycle

Method 1: Plain for loop

function fibonacci(n) {
    var n1 = 1, n2 = 1, sum;
    for (let i = 2; i < n; i++) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
}
fibonacci(30)
Copy the code

Method 2: for loop + destruct assignment

var fibonacci = function (n) {
    let n1 = 1; n2 = 1;
    for (let i = 2; i < n; i++) {
        [n1, n2] = [n2, n1 + n2]
    }
    return n2
}
fibonacci(30)
Copy the code

The running time of each method is shown below: Normal recursion > Improved recursion >for loop

From the dog brother oh, thank the bosses share the original link: https://www.cnblogs.com/superlizhao/p/11603158.html