Memoization优化递归

关于递归（Recursion）

1. 指在函数的定义里使用函数自身的方法，用于描述以自相似方法重复事物的过程
2. 在编程上，它是一种便于理解的心理模型：设定一个边界条件，如果达到则返回结果；如果没有达到，就简化问题，解决更加容易的问题，并且将结果组装成原始问题的解决方法，再返回这个解决方法
3. 许多数学函数可以用递归来表示，但是它具有较高的开销
4. 典型的递归入门例子：斐波那契数列

斐波那契数列（fibonacci）

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return 1
  }
  return fibonacci(n - 2) + fibonacci( n - 1)
}

Memoization可以优化递归的原理

1. 递归是一种循环，会有很大的开销
2. 如果把已经计算过的结果保存下来，直接返回而不是重新执行函数，那么就能大大提高递归的效率
3. Memoization的核心思想就是建立一个散列，然后把递归问循环里的计算结果记录下来，循环中发现重复的计算就直接获取结果。

4. 比如用Memoization优化fibonacci的递归计算

   var fib = {
     // 一般的就这样
     fib: function (n) {
       if (n == 0 || n == 1)
         return 1;
       return this.fib(n - 1) + this.fib(n - 2);
     },
     // 下面会用Memoization来优化
     fib_memo: function (n) {
       if (n == 0 || n == 1)
         return 1;
       return this.fib_memo(n - 1) + this.fib_memo(n - 2);
     },
   }
   // 写成通用的包装函数
   function Memoize(func, obj) {
     var obj = obj || window,
       func = obj[func],
       cache = {};
     return function () {
       var key = Array.prototype.join.call(arguments, '_');
       if (!(key in cache))
         cache[key] = func.apply(obj, arguments);
       return cache[key];
     }
   }
   fib.fib_memo = Memoize('fib_memo', fib);