递归操作是把问题逐渐缩小.
比如斐波那契数列, 其递归公式是:
- [quote]f(n) = f(n-1) + f(n-2)
- f(0) = f(1) = 1[/quote]
如果我要计算 f(5), 我需要计算 f(4) 和 f(3),
而计算 f(4) 时, 我又需要计算 f(3) 和 f(2).
我们用递归树来表示计算过程, 如图.
我们发现 f(3) 计算了 2 次, f(2) 计算了 3 次.
这还只是计算 f(5) 的情形 (用 5 来举例, 只因图好画),
如果是要计算 f(100) 呢, 其中 f(2) 不知会计算多少次.
也就是说递归时, 把问题规模减小时, 可能会出现很多重复的子问题.
我们希望减少无用功, 此时可以使用缓存来做.
比如原先的递归函数
javascript 代码
- function f(n) {
- if (n < 2) return 1;
- return f(n - 1) + f(n - 2);
- }
- console.log(f(10));
可以改成:
javascript 代码
- function f(n) {
- var cache = f.cache = f.cache || {};
- if (n in cache) return cache[n];
- if (n < 2) return cache[n] = 1;
- return cache[n] = f(n - 1) + f(n - 2);
- }
- console.log(f(10));
- console.log(f.cache);
有了缓存确实方便, 但不能每次为了缓存, 都要这么写吧.
因此一个概念横空出世, 函数记忆化.
javascript 代码
- function memoize(func) {
- var fn = function() {
- var cache = fn.cache;
- var key = [].join.call(arguments);
- if (!(key in cache)) return cache[key] = func.apply(this, arguments);
- return cache[key];
- };
- fn.cache = {};
- return fn;
- }
- var fn = memoize(function(n) {
- if (n < 2) return 1;
- return fn(n - 1) + fn(n - 2);
- });
- console.log(fn(10));
- console.log(fn.cache);
memoize 是对参数 func 进行了包装, 优先调用缓存.
缓存里没有时, 运行 func, 并把结果缓存起来. 缓存对象的键是参数以逗号相连接的字符串.
比如, 3 个参数时 sum(1, 2, 3),key 会变成 "1,2,3". 可以如下测试:
javascript 代码
- var sum = memoize(function(a, b, c) {
- return a + b + c;
- });
- sum(1, 2, 3);
- console.log(sum.cache);
当然我们可以允许 key 的形式由用户定义:
javascript 代码
- function memoize(func, hasher) {
- var fn = function() {
- var cache = fn.cache;
- var key = hasher? hasher.apply(this, arguments) : [].join.call(arguments);
- if (!(key in cache)) return cache[key] = func.apply(this, arguments);
- return cache[key];
- };
- fn.cache = {};
- return fn;
- }
- var sum = memoize(function(a, b, c) {
- return a + b + c;
- }, function(a, b, c) {
- return ''+ a +'-'+ b +'--' + c;
- });
- console.log(sum(1, 2, 3));
- console.log(sum.cache);
最后要说明, 函数记忆化, 是函数式编程中的概念.
函数记忆不一定只针对递归, 但要求函数是纯的.
即输入确定, 输出就确定, 不能对程序状态搞下小动作.
因为内部利用了缓存, 并不是每次都会运行函数.
上述代码改编于 underscore.js 的 memoize 方法.
来源: http://www.qdfuns.com/article/17398/7adf5d345c41e7296363fd5571ad2858.html