函数可以将先前操作的结果记录在某个对象中，从而避免无谓的重复运算

以计算 Fibonacci 数列为例

1
2
3
4
5
6
7
8
9
10
11
12
// count 用于计算函数调用次数
var count = 0;

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

for (let i = 0; i <= 10; i++) {
  console.log(`fibonacci(${i}) = ${fibonacci(i)}`);
}
console.log(`count = ${count}`)；

结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
fibonacci(10) = 55

count = 453

可以看到，上面的循环总共调用了453次 fibonacci(i)

如果使用一个数组存储函数运算的结果，在每次调用函数之前先检查结果是否已经存在，则可以大大减少运算次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var count = 0;

const fibonacci = (function () {
  let memo = [0, 1];
  const fib = n => {
    count++;
    let result = memo[n];
    if (typeof result !== 'number') {
      result = fib(n - 1) + fib(n - 2);
      memo[n] = result;
    }
    return result;
  };
  return fib;
})();

for (let i = 0; i <= 10; i++) {
  console.log(`fibonacci(${i}) = ${fibonacci(i)}`);
}
console.log(`count = ${count}`);

结果为

1
2
3
4
5
6
7
8
9
10
11
12
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
fibonacci(10) = 55
count = 29

使用数组存储结果后，函数主体部分仅被调用29次，运算结果不变

将该方法做一个抽象，编写一个函数来构造带有记忆功能的函数

1
2
3
4
5
6
7
8
9
10
11
const memorize = (memo, formula) => {
  const recur = n => {
    let result = memo[n];
    if (result === undefined) {
      result = formula(recur, n);
      memo[n] = result;
    }
    return result;
  };
  return recur;
};

memorize函数有一个初始的memo数组和formula函数，返回一个能管理memo存储和调用formula函数的recur函数

举个例子，通过memorize来定义fibonacci函数

1
2
3
const fibonacci = memorize([0, 1], (recur, n) => {
  return recur(n - 1) + recur(n - 2);
});

阶乘函数

1
2
3
const factorial = memorize([1, 1], (recur, n) => {
  return n * recur(n - 1);
});