[JS]js记忆算法理解

/*
        函数可以用对象去记住先前的操作结果，从而能避免无所谓的运算，这种优化被称作为记忆。
        js对象和数组要实现这种优化是非常方便的。
        比如说，我们想要一个递归函数来计算斐波那契数列。一个数字是前两个数字的和，最前面两个是0和1
*/
var fibonacci = function (n) {
        return n < 2 ? n : fibonacci(n - 1) + fibonacci( n - 2);
};
for(var i = 0;i <= 10;i +=1) {
        document.writeln('//' + i + ':' + fibonacci(i));
}
/*
        这样的写法是可以正常求值的，但它做了很多无所谓的工作。fibonacci函数被调用了453次，
        我们调用了11次，而它自身调用了442次去计算可能已被刚计算过的值，
        如果我们让函数具备记忆功能，就可以显著减少它的运算量
        我们在一个名为memo的数组里保存我们的存储结果，存储结果可以隐藏在闭包中
        当我们的函数被调用时，这个函数首先看是否已经知道存储结果，如果已经知道，就立即返回这个结果
*/
var fibonacci = function () {
        var memo = [0,1],
                fib = function (n) {
                        var result = memo[n];
                        if(typeof result!== 'number'){
                                result = fib(n - 1) + fib(n - 2);
                                memo[n] = result;
                        }
                        return result;
                }
        return fib;
}();
/*
        这个函数返回同样的结果，但它只被调用了29次，我们调用了它11次，他自身调用了18次去取得之前存储的结果。
        我们可以把这种形式一般化，编写一个函数来帮助我们够着带记忆功能的函数。
        memoizer函数将取得一个初始的memo数组和fundamental函数。
        它返回一个管理memo存储和在需要时调用fundamental函数的shell函数。
        我们传递这个shell函数和该函数的参数给fundamentall
*/
var memoizer = function (memo,fundamentall) {
        var shell = function(n){
                var result = memo[n];
                if(typeof result !== 'number'){
                        result = fundamentall(shell,n);
                        memo[n] = result;
                }
                return result;
        };
        return shell;
};
/*
        现在我们可以使用memoizer来定义fibonacci函数，提供其初始memo数组和fundamental函数：
*/
var fibonacci = memoizer([0,1],function(shell,n){
        return shell(n - 1) + shell(n - 2);
});
// 通过设计能产生出其他函数的函数，可以极大减少我们必须要做的工作。
// 例如：要产生一个可记忆的阶乘函数，我们只需提供基本阶乘函数公式即可：
var factorial = memoizer([1,1],function(shell,n){
        return n*shell(n - 1);
});