javascript memoization递归优化

memoize优化递归

function createRec(callback, cache) {

    cache = cache || [];

    var rec = function(n) {

　　　　(n in cache) || (cache[n] = callback(rec, n));

           return cache[n];

    }

　　return rec;

}

以Fibonacci数列为例子，如何创建一个优化的递归

var fib = createRec(function(cal, n) {

    return cal(n - 1) + cal(n - 2);

}, [0, 1, 1]);

在callback里面我们传入的参数是返回的递归函数和n，函数体内部是递归函数遇到n后的递归规则，cache里面是一些初始值

作用

典型的，我们使用传统的递归计算Fibonacci数列

function fibonacci(n) {// author黄雪良

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

}

计算fibonacci(80)……卡死了

但是使用经过优化的算法，可以非常快的算出来

原因很明显，由于缓存的原因1~80每个数都只需要计算一遍，80次计算需要的时间可不长，可是在没有缓存的情况下，每个数都需要重复计算很多遍

更进一步，尾递归

当然，我们还可以用尾递归进行优化

function fibonacci(n, ret1, ret2) {

    if (n < 2) {

        return ret1;

    }

    return fibonacci(n - 1, ret2, ret1 + ret2);

}

这个递归中，每次只有一个分支，很明显比原始的递归要优化了很多，而且每次递归都把结果计算出来了，每个数值只需要计算一遍

巴特西

javascript memoization递归优化

最新文章

热门文章