代码所做的事情越少,它的运行速度就越快,因此,避免重复工作很有意义。多次执行相同的任务也在浪费时间。制表法通过缓存先前计算结果为后续计算所使用,避免了重复工作,这使得制表成为递归算法中最有用的技术。
当递归函数被多次调用时,重复工作很多。以下factorial函数是一个递归函数重复多次的典型例子。
var fact6=factorial(6);
var fact5=factorial(5);
var fact4=factorial(4);
此代码生成3个阶乘结果,factorial函数总共被调用了18次。此代码中最糟糕的部分是,所有必要的计算已经在第一行代码中执行过了。因为6的阶乘等于6乘以5的阶乘,所以5的阶乘被计算了两次。更糟糕的是,4的阶乘被计算了3次。更为明智的方法是保存并重利用它们的计算结果,而不是每次都重新计算整个函数。使用制表法重写factorial函数:
function memfactorial(n){
if(!memfactorial.cache){
memfactorial.cache={
"0":1,
"1":1
};
}
if(!memfactorial.cache.hasOwnProperty(n)){
memfactorial.cache[n]=n*memfactorial(n-1);
}
return memfactorial.cache[n];
}
使用制表法设计阶乘函数的关键是建立一个缓存对象,此对象位于函数内部,其中预置了两个最简单的阶乘:0和1。在计算阶乘之前,先检查缓存中是否已经存在相应的计算结果。没有对应的缓冲值说明这是第一次计算此数值的阶乘,计算完成之后结果被存入缓存之中,以备今后使用。
var fact6=memfactorial(6);
var fact5=memfactorial(5);
var fact4=memfactorial(4);
上面代码返回3个不同的阶乘值,总共只调用memfactorial函数8次。既然所有必要的计算都在第一行代码中完成了,那么后两行代码不会产生递归运算,因为直接返回了缓存中的数值。制表过程会因递归函数的种类不同而略有不同,但总体上具有相同的模式。