4/15/Fibonacci数列

[ChenPt]

// 动态规划版
// 其实这个方法也是重复计算了很多次
function caculate1(n) {
    let result = [];

    for(let i = 0; i < n; i++) {
        if(i < 2) {
            result.push(1)
        } else {
            result.push(result[i-1] + result[i-2])
        }
    }

    console.log(result)
}

// 递归优化版
function caculate2(x) {
    let cache = [1,1]
    let result = [];
    let fib = function(n) {
        let temp = cache[n]
        if(typeof temp !== 'number') {
            temp = fib(n-1) + fib(n-2);
            cache[n] = temp;
        }

        return temp
    }
    for(let i = 0; i < x; i++) {
        result.push(fib(i))
    }
    return result;
}

//普通递归版
function caculate3(x) {
    let result = [];

    let fib = function(n) {
        if(n < 2) {
            return 1
        } else {
            return fib(n-1) + fib(n-2)
        }
    }
    for(let i = 0; i < x; i++) {
        result[i] = fib(i);
    }

    return result;
}

caculate1其实花费的时间为什么比优化后的递归还高呢？因为其实它也是重复计算了很多次，可以牺牲空间，利用一个cache数组将计算过的结果存在cache里，当需要调用fib（n）的值先去cache里寻找，若无再进行计算。 测试代码

//测试代码
function test(fn, data) {
    let pre = performance.now();
    let result = fn(data);
    console.log(fn.name + ": " + (performance.now()-pre) + "ms" )
}

var funArr = [caculate1, caculate1_1, caculate2, caculate3]

funArr.forEach(e => {
    test(e, 10)
})

caculate3...使用的测试用例如果是大一点的数的话，浏览器会卡死...说明其性能是真的极差极差，很容易就stack overflow。

[ChenPt]

尾递归版本~

let test = function(n, n1 = 1, n2 = 1) {
  if(n <=1 )   return n1
  else return test(n-1, n1+n2, n1)
}

let fib = function(n) {
  return test.call(null, n)
}