首页 > 代码库 > 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); }
这个递归中,每次只有一个分支,很明显比原始的递归要优化了很多,而且每次递归都把结果计算出来了,每个数值只需要计算一遍
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。