# Speed up your JavaScript, Part 3

Recursion is the enemy of fast-running scripts. Too much recursion can cause the browser to grind to a halt or quit unexpectedly, and so must be addressed a serious performance problem in JavaScript. In part 2 of this series, I wrote briefly about handling too much recursion in a function through memoization. Memoization is a technique for caching previously calculated values so that they need not be recalculated; when a recursive function is doing such a calculation, memoization is incredibly useful. The memoizer I presented was Crockford’s, and is useful primarily for recursive functions that return integers. All recursive functions, of course, don’t return integers. A more generic `memoizer()`

function can be created to deal with any type of recursive function:

```
function memoizer(fundamental, cache){
cache = cache || {}
var shell = function(arg){
if (!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(shell, arg)
}
return cache[arg];
};
return shell;
}
```

This version of the function is a bit different than Crockford’s. First, the order of arguments has been reversed with the original function as the first argument and an optional `cache`

object as the second argument. Not all recursive functions are seeded with initial information, so making that argument optional makes sense. Inside, I’ve changed the caching data type from an array to an object, which makes this version applicable to recursive functions that return non-integer results. Inside the `shell`

function, I’m using the `hasOwnProperty()`

method to see if the argument already has a `cache`

entry. This is safer than testing if the type of value isn’t `undefined`

since `undefined`

is a valid return value. Example usage with the previous Fibonacci example:

```
var fibonacci =
memoizer(function (recur, n) {
return recur(n - 1) + recur(n - 2);
}, {"0":0, "1":1});
```

Once again, a call to `fibonacci(40)`

results in only 40 calls of the original function instead of 331,160,280. Memoization works great for recursive algorithms with a strictly defined result set. There are, however, other recursive algorithms that don’t lend themselves to optimization through memoization.

One of my professors in college insisted that anything written using recursion could also be written using iteration if necessary. Indeed, recursion and iteration are often considered remedies for one another when one is seen as a problem. The techniques for converting a recursive algorithm into an iterative algorithm are the same regardless of the programming language; the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive. Consider a typical recursive algorithm such as a merge sort. In JavaScript, it may be written like this:

```
function merge(left, right){
var result = [];
while (left.length > 0 && right.length > 0){
if (left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
//recursive merge sort algorithm
function mergeSort(items){
if (items.length == 1) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
```

Calling the `mergeSort()`

function on an array returns an array of the items sorted in correct order. Note that for each call to `mergeSort()`

there are two recursive calls. This algorithm won’t benefit from memoization because each result is only calculated once and, therefore, caching the results doesn’t help. If you were to call `mergeSort()`

on an array with 100 items, there would be 199 calls total; a 1,000 item array would result in 1,999 calls. The solution in this case is to convert the recursive algorithm into an iterative one, which means introducing some loops (algorithm credit: List Processing: Sort Again, Naturally):

```
//iterative merge sort algorithm
function mergeSort(items){
if (items.length == 1) {
return items;
}
var work = [];
for (var i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = []; //in case of odd number of items
}
return work[0];
}
```

This implementation of the merge sort algorithm uses a series of loops instead of recursion to sort the array. Since merge sort works by first breaking down an array into several one-item arrays, this method does that explicitly instead of implicitly via recursive calls. The `work`

array is initially an array of one-item arrays. The loops enable the merging of two arrays at a time, placing the result back into the `work`

array. When the function has done its job, the result is stored in the first position of `work`

and is returned. In this version of merge sort, there is no recursion. It does, however, introduce a large number of loops based on the number of items in the array, so it may be worth revisiting the techniques discussed in part 2 to handle the extra overhead.

The bottom line: always be on the look out for recursion in your JavaScript. Memoization and iteration are two ways to avoid excessive recursion and the long-running script dialog.

## Translations

Disclaimer: Any viewpoints and opinions expressed in this article are those of Nicholas C. Zakas and do not, in any way, reflect those of my employer, my colleagues, Wrox Publishing, O'Reilly Publishing, or anyone else. I speak only for myself, not for them.

Both comments and pings are currently closed.

Pingback: Linkdump #4 | CTAPbIu_MABP's BLOG()

Pingback: Speed up your JavaScript, Part 4 | NCZOnline()

Pingback: Ajaxian » Speeding up your JavaScript: Part 3 and 4()

Pingback: My Bad Attitude » Speed up your JavaScript()

Pingback: å¦‚ä½•æå‡JavaScriptçš„è¿è¡Œé€Ÿåº¦ï¼ˆé€’å½’ç¯‡ï¼‰ « ä¸ƒæœˆä½‘å®‰()

Pingback: JAOO 2009 - Brisbane - brettdargan.com()

Pingback: å¦‚ä½•æå‡JavaScriptçš„è¿è¡Œé€Ÿåº¦ï¼ˆé€’å½’ç¯‡ï¼‰ « iUE()

Pingback: å¦‚ä½•æå‡JavaScriptçš„è¿è¡Œé€Ÿåº¦ï¼ˆDOMç¯‡ï¼‰ « Oragg.com()

Pingback: å¦‚ä½•æå‡JavaScriptçš„è¿è¡Œé€Ÿåº¦ï¼ˆé€’å½’ç¯‡ï¼‰ « ä¸ƒæœˆä½‘å®‰()

Pingback: æå‡JavaScriptè¿è¡Œé€Ÿåº¦ä¹‹é€’å½’ç¯‡ » C&F Studio()

Pingback: Neil Skoglund » Blog Archive » 120 Tips, Tricks, and Tuts from 2009 Worth your Time()

Pingback: Java Oracle Solarisâ€”èƒŒè´Ÿä¸€èº«æƒ…å€ºçš„ä¼é¹… » Natural Merge Sort è‡ªç„¶åˆå¹¶æŽ’åº()

Pingback: Seven Must-See Videos and Presentations for Web App Developers - Smashing Magazine()