首页 > 代码库 > javascript memoization递归优化

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);
}

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