Js implementation of Fibonacci sequence of several methods

recursive

Method one: ordinary recursion

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 3-1: Improved recursion – extract the functional functions that store the calculated results

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

Arguments.callee is not very recommended

The most common use of Callee is to recursively call itself from anonymous functions, but ECMAScript 3 already allows named function expressions without polluting the namespace, so it’s not inelegant to do the same thing.

Arguments is a large object that needs to be recreated each time a recursive call is made (although arguments.callee is constant, arguments. Caller is different, and arguments to call are different). ECMAScript5 is forbidden in Strict Mode.

var result = [];
function fn(n) { // Typical Fibonacci sequence
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        if (result[n]) {
            return result[n];
        } else {
            result[n] = arguments.callee(n - 1) + arguments.callee(n - 2);
            returnresult[n]; }}}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