JS编程建议——32：使用制表

建议32：使用制表
代码所做的事情越少，它的运行速度就越快，因此，避免重复工作很有意义。多次执行相同的任务也在浪费时间。制表法通过缓存先前计算结果为后续计算所使用，避免了重复工作，这使得制表成为递归算法中最有用的技术。
当递归函数被多次调用时，重复工作很多。以下factorial()函数是一个递归函数重复多次的典型例子。

1. var fact6 = factorial(6);
2. var fact5 = factorial(5);
3. var fact4 = factorial(4);
   此代码生成3个阶乘结果，factorial()函数总共被调用了18次。此代码中最糟糕的部分是，所有必要的计算已经在第一行代码中执行过了。因为6的阶乘等于6乘以5 的阶乘，所以5的阶乘被计算了两次。更糟糕的是，4的阶乘被计算了3次。更为明智的方法是保存并重利用它们的计算结果，而不是每次都重新计算整个函数。使用制表法重写factorial()函数：
4. function memfactorial(n) {
5. if(!memfactorial.cache) {
6. memfactorial.cache = {
7. "0" : 1,
8. "1" : 1
9. };
10. }
11. if(!memfactorial.cache.hasOwnProperty(n)) {
12. memfactorial.cache[n] = n * memfactorial(n – 1);
13. }
14. return memfactorial.cache[n];
15. }
    使用制表法设计阶乘函数的关键是建立一个缓存对象，此对象位于函数内部，其中预置了两个最简单的阶乘：0 和1。在计算阶乘之前，先检查缓存中是否已经存在相应的计算结果。没有对应的缓冲值说明这是第一次计算此数值的阶乘，计算完成之后结果被存入缓存之中，以备今后使用。
16. var fact6 = memfactorial(6);
17. var fact5 = memfactorial(5);
18. var fact4 = memfactorial(4);
    上面代码返回3个不同的阶乘值，总共只调用memfactorial()函数8次。既然所有必要的计算都在第一行代码中完成了，那么后两行代码不会产生递归运算，因为直接返回了缓存中的数值。制表过程会因递归函数的种类不同而略有不同，但总体上具有相同的模式。