递归是拖慢脚本运行速度的大敌之一。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然自动退出,所以我们一定要解决在JavaScript中出现的这一系列性能问题。
我们可以通过memoization技术来替代函数中太多的递归调用。memoization是一种可以缓存之前运算结果的技术,这样我们就不需要重新计算那些已经计算过的结果。
对于通过递归来进行计算的函数,memoization简直是太有用了。我现在使用的memoizer是由Crockford写的,主要应用在那些返回整数的递归运算中。当然并不是所有的递归函数都返回整数,所以我们需要一个更加通用的memoizer()函数来处理更多类型的递归函数。
|
这个版本的函数和Crockford写的版本有一点点不同。首先,参数的顺序被颠倒了,原有函数被设置为第一个参数,第二个参数是缓存对象,为可选参数,因为并不是所有的递归函数都包含初始信息。在函数内部,我将缓存对象的类型从数组转换为对象,这样这个版本就可以适应那些不是返回整数的递归函数。在shell函数里,我使用了in操作符来判断参数是否已经包含在缓存里。这种写法比测试类型不是undefined更加安全,因为undefined是一个有效的返回值。我们还是用之前提到的斐波纳契数列来做说明:
|
同样的,执行fibonacci(40)这个函数,只会对原有的函数调用40次,而不是夸张的331,160,280次。memoization对于那些有着严格定义的结果集的递归算法来说,简直是棒极了。然而,确实还有很多递归算法不适合使用memoization方法来进行优化。
有的观点认为,任何使用递归的情况,如果有需要,都可以使用迭代来代替。实际上,递归和迭代经常会被作为互相弥补的方法,尤其是在另外一种 出问题的情况下。将递归算法转换为迭代算法的技术,也是和开发语言无关的。这对JavaScript来说是很重要的,因为很多东西在执行环境中是受到限制的。让我们回顾一个典型的递归算法,比如说归并排序,在JavaScript中实现这个算法需要下面的代码:
|