计算一个数字的数列它为什么能瞬间出结果？

Question

请教个问题，计算一个数字的数列是要很长时间的，如下函数：function res(n){    return n < 2 ? n : res(n - 1) + res(n - 2); }var start = new Date();console.log(res(43));console.log(new Date()-start+'ms');Chrome执行结果如下：4334944378358ms但是下面的函数res_1在没有经过缓存计算结果的前提下也能瞬间出结果，这是什么原理？function res_1(n){    if(!res_1.cache[n]){        return res_1.cache[n] = n < 2 ? n : res_1(n - 1) + res_1(n - 2);     }    return res_1.cache[n]; } res_1.cache = {};var start = new Date();console.log(res_1(43));console.log(new Date()-start+'ms');Chrome执行结果如下：4334944370ms计算45的数列：start = new Date();console.log(res_1(45));console.log(new Date()-start+'ms');结果如下，未经过缓存11349031700ms而用res函数计算45的数列，要25468ms

Answer 1

我把你的代码改了下，加了点调试语句，你一眼就能看出来为啥了，当然为了显示方便，我把计算总算改成了 5。

const TOTAL = 5;

(() => {

    console.time("test1");

    function res(n) {

        console.log(`calculating ${n}`);

        return n < 2 ? n : res(n - 1) + res(n - 2);

    }

    var start = new Date();

    console.log(res(TOTAL));

    console.timeEnd("test1");

})();

(() => {

    console.time("test2");

    function res_1(n) {

        if (!res_1.cache[n]) {

            console.log(`calculating ${n}`);

            return res_1.cache[n] = n < 2 ? n : res_1(n - 1) + res_1(n - 2);

        }

        return res_1.cache[n];

    }

    res_1.cache = {};

    var start = new Date();

    console.log(res_1(TOTAL));

    console.timeEnd("test2");

})();

很明显，第1种方法在递归的过程中进行了很多重复计算。

另外，解释器会自己对运算做一些缓存，如果你把两段代码的执行顺序换一下，结果会有些差异。