递归函数中使用缓存计算(memoization)提升性能

递归应该是众所周知的概念，而且我们遇到次数最多的例子可能就是斐波那契数列了，规则如下：

f(n)=f(n-1)+f(n-2),
    for n=2,3,4,...n and 
        f(0)=0 and f(1)=1

一个斐波那契数列数列是前面两个斐波那契数的加和。
所以我们一般写的代码可能就是这样的：

function fibonacci(n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

问题引入

如果稍微了解一点数据结构应该知道入栈、出栈、堆栈等等这些概念，所以这个递归的过程其实是把中间值压入到了内存的一个栈中，并且保持到终止条件满足。

拿这个斐波那契数列当例子有点令人费解，这里拿阶乘说明吧，阶乘代码如下：

function factorial(n){
    return n==1?1:n*factorial(n-1);
}

稍微改动下代码，记录它的计算过程：

function factorial(n) {
    var re;
    re = n == 1 ? 1 : n * factorial(n - 1);
    console.log(re);
    return re;
}
factorial(5);

打印出的计算过程

这下应该可以比较清楚地看出对于中间值是先压入栈中保存，最后再一个个出栈，并且符合堆栈中“后入先出”的原则。

再回到斐波那契数列，每次迭代过程中都会计算两个函数，比如f(9)会计算f(8)+f(7)，求f(8)的时候又要计算f(7)+f(6),显然中间有了较多的重复计算，这太浪费内存、白白消耗cpu了，所以如果想要减少重复复杂的、CPU消耗大的计算，很有必要来优化下我们的代码。

解决方案

使用计算缓存(Memoization)来缓存复杂计算的结果。上个例子：

var fibonacci = function() {
    var memo = [0, 1];
    var 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;
}();

也就是我们使用数组缓存中间值，而不再重新创建他们，从而缩减了迭代和计算的次数。尤其对于斐波那契数列和阶乘这种都会使用前面值的计算效果尤其好。赶紧来验证下：

var fibonacci = function() {
    var memo = [0, 1];
    var 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;
}();
console.time("memo");
for(var i=0;i<15;i++){
    fibonacci(i);
}
console.timeEnd("memo");

var fibon = function(n) {
    return n < 2 ? n : fibon(n - 1) + fibon(n - 2);
}
console.time("non-memo");
for(var i=0;i<15;i++){
    fibon(i);
}
console.timeEnd("non-memo");

结果是：

memo: 0.158ms
non-memo: 0.458ms

虽然这样的例子显示结果良好，但是更多时候我们也就计算数列的某一个值，如果数字较小，那么往数组中存储数据的过程的时间消耗就会比较明显了，此时使用缓存会显得是个累赘。但是使用缓存的优势在递归次数越大的时候是会越明显滴~

//这是我只计算斐波那契数列第30个值时两者的运行时间：
memo: 0.171ms
non-memo: 13.369ms

当我想看看计算数列第50个值时运用缓存到底运行时间能差多少，浏览器竟然给我都罢工了。。。

Underscore.js库有提供实现该功能的memoize()函数。使用方法如下：

var fibonacci = _.memoize(function(n) {
  return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
});

对于耗时计算计算较长的计算，强烈推荐使用哦~