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

问题描述

问 题

请教个问题，计算一个数字的数列是要很长时间的，如下函数：

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执行结果如下：
433494437
8358ms
但是下面的函数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执行结果如下：
433494437
0ms

计算45的数列：

start = new Date();
console.log(res_1(45));
console.log(new Date()-start+'ms');

结果如下，未经过缓存
1134903170
0ms
而用res函数计算45的数列，要25468ms

解决方案

我把你的代码改了下，加了点调试语句，你一眼就能看出来为啥了，当然为了显示方便，我把计算总算改成了 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种方法在递归的过程中进行了很多重复计算。

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

这篇关于javascript - 计算一个数字的数列它为什么能瞬间出结果？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！