[This article address] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
Recursion is one of the enemies that slows down the running speed of scripts. Too much recursion will make the browser slower and slower until it dies or automatically exits suddenly and inexplicably, so we must solve this series of performance problems in JavaScript. In the second article of this series, I briefly introduced how to use memoization technology to replace too many recursive calls in functions. Memoization is a technique that caches the results of previous calculations so that we don't need to recalculate those results that have already been calculated. For functions that perform calculations through recursion, memoization is simply too useful. The memoizer I am currently using was written by Crockford and is mainly used in recursive operations that return integers. Of course, not all recursive functions return integers, so we need a more general memoizer() function to handle more types of recursive functions.
function memoizer(fundamental, cache){ cache = cache || {} var shell = function(arg){ if (!(arg in cache)){ cache[arg] = fundamental(shell, arg) } return cache[arg] ; }; return shell;} This version of the function is slightly different from the one written by Crockford. First, the order of parameters is reversed, the original function is set as the first parameter, and the second parameter is the cache object, which is optional because not all recursive functions contain initial information. Inside the function, I cast the type of the cache object from an array to an object so that this version can accommodate recursive functions that don't return integers. In the shell function, I use the in operator to determine whether the parameters are already included in the cache. This way of writing is safer than testing that the type is not undefined, because undefined is a valid return value. We still use the Fibonacci sequence mentioned before to illustrate:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1":1}); Similarly, executing the function fibonacci(40) will only call the original function 40 times, instead of the exaggerated 331,160,280 times. Memoization is great for recursive algorithms with strictly defined result sets. However, there are indeed many recursive algorithms that are not suitable for optimization using memoization methods.
One of my professors in school always insisted that any situation where recursion was used could be replaced by iteration if necessary. In fact, recursion and iteration are often used as methods to compensate for each other, especially when the other one goes wrong. The technology of converting recursive algorithms into iterative algorithms is also independent of development language. The importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive. Let's review a typical recursive algorithm, such as merge sort. Implementing this algorithm in JavaScript requires the following code:
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);}//Merge sorting algorithm function mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) using recursion , left = items.slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} Call the mergeSort() function to process an array, and you can return the sorted array. Note that each time the mergeSort() function is called, there will be two recursive calls. This algorithm cannot be optimized using memoization, because each result is calculated and used only once, and even buffering the results is of no use. If you use the mergeSort() function on an array of 100 elements, there will be a total of 199 calls. An array of 1000 elements will perform 1999 calls. In this case, our solution is to convert the recursive algorithm into an iterative algorithm, which means introducing some loops (for the algorithm, you can refer to this article "List Processing: Sort Again, Naturally"):
// Use iterative implementation The 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 = (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 merge sort algorithm implementation uses a series of loops instead of recursion for sorting. Since merge sort first splits the array into several arrays with only one element, this method performs this operation more explicitly rather than implicitly using a recursive function. The work array is initialized to contain an array of one-element arrays. Each time in the loop, the two arrays are merged and the merged result is put back into the work array. When the function is executed, the sorted result will be returned through the first element in the work array. In this implementation of merge sort, the algorithm is also implemented without using any recursion. However, this introduces a large number of loops, and the number of loops is based on the number of elements in the array to be sorted, so we may need to modify it using the techniques discussed in the previous article to deal with this additional overhead.
To summarize the basic principles, you should be careful whenever using recursion. Memoization and iteration are two solutions to replace recursion. The most direct result is of course to avoid the dialog box that prompts the script to be out of control.