Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to improve the recursive efficiency of JavaScript. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

Recursion is one of the biggest enemies that slow down scripts. Too much recursion will make browsers slower and slower until they die or exit automatically for no reason, so we must solve this series of performance problems in JavaScript.

We can use memoization technology to replace too many recursive calls in the function. Memoization is a technique that caches the results of previous operations so that we don't have to recalculate the results that have already been calculated.

Memoization is simply too useful for functions that are evaluated by recursion. The memoizer I use now is 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 generic memoizer () function to handle more types of recursive functions.

Function memoizer (fundamental, cache) {cachecache = 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 a little different from the one written by Crockford. First of all, the order of the parameters is reversed, the original function is set to * * parameters, and the second parameter is the cache object, which is optional, because not all recursive functions contain initial information. Inside the function, I convert the type of the cached object from an array to an object so that this version can accommodate recursive functions that do not return integers. In the shell function, I use the in operator to determine whether the parameter is already in the cache. This is safer than if the test type is not undefined, because undefined is a valid return value. Let's use the Fibonacci series mentioned earlier to illustrate:

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

Similarly, executing the fibonacci (40) function will only call the original function 40 times, rather than the exaggerated 331160280 times. Memoization is great for recursive algorithms with well-defined result sets. However, there are many recursive algorithms that are not suitable for optimization using the memoization method.

Some argue that any use of recursion, if necessary, can be replaced by iteration. In fact, recursion and iteration are often used as ways to make up for each other, especially in another case where something goes wrong. The technique of converting recursive algorithms into iterative algorithms is also independent of the development language. This is important for JavaScript because many things are limited in the execution environment. Let's review a typical recursive algorithm, such as merge sorting, which requires the following code to implement in JavaScript:

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); } //采用递归实现的归并排序算法 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)); } 调用mergeSort()函数处理一个数组，就可以返回经过排序的数组。注意每次调用mergeSort()函数，都会有两次递归调用。这个算法不可以使用memoization来进行优化，因为每个结果都只计算并使用一次，就算缓冲了结果也没有什么用。如果你使用mergeSort()函数来处理一个包含100个元素的数组，总共会有199次调用。1000个元素的数组将会执行1999次调用。在这种情况下，我们的解决方案是将递归算法转换为迭代算法，也就是说要引入一些循环： // 采用迭代实现的归并排序算法 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; jacks, k + = 2) {work [j] = merge (work [k], work [k + 1]);} work [j] = []; / / in case of odd number of items} return work [0];}

The implementation of this merge sorting algorithm uses a series of loops instead of recursion for sorting. Since merge sorting first splits the array into arrays with only one element, this method performs this operation more explicitly, rather than vaguely through recursive functions. The work array is initialized to contain an array with a single array of elements.

Two arrays are merged each time in the loop, and the merged results are put back into the work array. When the function is executed, the sorted result is returned through the * elements in the work array. In this implementation of merge sorting, no recursion is used, and the algorithm is also implemented.

This is the end of the article on "how to improve the recursive efficiency of JavaScript". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.