Fibonacci sequence in JS: 7 ways to implement Fibonacci sequence

First in nuggets original link reprint please specify nuggets link

Preface 🎤

I have nothing to do but think of something useless.

Ordinary recursion

function (n) { // N,N
    if (n < 2) return n
    return arguments.callee(n - 1) + arguments.callee(n - 2)}Copy the code

Tail recursive optimization method

function fibonacci(n, current, next) {
    if(n === 1) return next;
    if(n === 0) return 0;
    return fibonacci(n - 1, next, current + next);
}
Copy the code

Dynamic programming method

(n) => { // dynamic programming N,1
    let dp = [0.1]
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]}return dp[n]
}
Copy the code

Dynamic programming, surface space complexity O(1) method

(n) => { // Dynamic programming reduced surface N,1
    let [prev, cur] = [0.1]
    while (n-- > 0) [prev, cur] = [cur, prev + cur]
    return prev
}
Copy the code

Dynamic programming, real space complexity O(1) method

(n) => { // Real dynamic programming reduced edition N,1
    let prev = 0,cur = 1
    let t = 0
    while (n-- > 0){
        t = prev
        prev = cur
        cur = t + cur
    }
    return prev
}
Copy the code

Array. Reduce implementations

(n) => { // N,1
    return new Array(n).fill(0).reduce(prev= > [prev[1], prev[0] + prev[1]], [0.1[])0]}Copy the code

Method of generator

(n)=>{ // a meaningless version N,1
    let g = (function* (){
        let [cur,last] = [0.1]
        yield cur;
        yield last;
        while(true) {yield (cur + last);
            [cur,last] = [last,cur + last]
        }
    })()

    let result = 0
    while(n-->= 0) result = g.next().value
    return result
}
Copy the code

Time and space are

Conclusion 👨 🏫

Generator should not be used in this scenario, shame on him.

Shipped beta version

"use strict";
let tree = {
    'reduce': (n) = > { // N,1
        return new Array(n).fill(0).reduce(prev= > [prev[1], prev[0] + prev[1]], [0.1[])0]},'nomarl': (n) = > { // dynamic programming N,1
        let dp = [0.1]
        for (let i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]}return dp[n]
    },
    'nomarl-one-space': (n) = > { // Dynamic programming reduced surface N,1
        let [prev, cur] = [0.1]
        while (n-- > 0) [prev, cur] = [cur, prev + cur]
        return prev
    },
    'nomarl-one-space-real': (n) = > { // Real dynamic programming reduced edition N,1
        let prev = 0,cur = 1
        let t = 0
        while (n-- > 0){
            t = prev
            prev = cur
            cur = t + cur
        }
        return prev
    },
    'recursion': function (n) { // N,N
        if (n < 2) return n
        return arguments.callee(n - 1) + arguments.callee(n - 2) // arrow have not arguments
    },
    'generator':(n) = >{ // a meaningless version N,1
        let g = (function* (){
            let [cur,last] = [0.1]
            yield cur;
            yield last;
            while(true) {yield (cur + last);
                [cur,last] = [last,cur + last]
            }
        })()

        let result = 0
        while(n-->= 0) result = g.next().value
        return result
    },
    'recursion-plus':function fibonacci(n, current, next) {
        if(n === 1) return next;
        if(n === 0) return 0;
        return fibonacci(n - 1, next, current + next); }}Object.keys(tree).forEach(name= > {
    console.time(name)
    let mem = process.memoryUsage()
    let fib = tree[name]
    function no(n) {
        throw new Error(`${n} but ${fib(n)}`)}try {
        fib(0) = =0 || no(0)
        fib(1) = =1 || no(1)
        fib(2) = =1 || no(2)
        fib(10) = =55 || no(10)
        fib(45) = =1134903170 || no(45)}catch (e) {
        console.log(`err:${name} when ${e.message}`)}let nowMem = process.memoryUsage()
    console.timeEnd(name)
    
    console.log(`${name} mem:${(nowMem.heapUsed - mem.heapUsed)/1024}KB`)});Copy the code