Javascript 高性能之递归，迭代，查表法详解

递归

概念：函数通过直接调用自身，或者两个函数之间的互相调用，来达到一定的目的，比如排序，阶乘等

简单的递归

阶乘

function factorial(n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); }}

递归实现排序

function myMerge(left, right) { // 保存最后结果的数组 var res = []; // 有一个数组结束了就结束排序，一般情况下，两个数组长度应该保持一样 while (left.length > 0 && right.length > 0) { if ( left[0] < right[0] ) { // 把left第一个成员删除，存储到新数组res中 res.push(left.shift()); } else { res.push(right.shift()); } } // 如果还有剩余直接合并到新数组 return res.concat(left).concat(right);}function recursion(items) { if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2), left = items.slice(0, middle), // 取数组前半部分 right = items.slice(middle); // 取数组后半部分 // 递归排序 return myMerge(recursion(left), recursion(right));}

迭代

每个浏览器对递归都有调用栈上限的问题，且如果不小心使用也很容易造成死循环导致程序崩溃。如果考虑到性能问题，可以使用迭代来代替递归，因为运行循环总比反复调用函数的开销少很多

function iteration(items) { if (items.length == 1) { return items; } var work = []; // 将items成员全部转化成数组，保存到数组中 for (var i = 0, len = items.length; i < len; i++) { work.push([items[i]]); } work.push([]); // 数组长度为奇数时 // 迭代 for (var lim = len; lim > 1; lim = (lim + 1) / 2) { for (var j = 0, k = 0; k < lim; j++, k+=2) { work[j] = myMerge(work[k], work[k + 1]); } work[j] = []; // 数组长度为奇数时 } return work[0];}

递归优化，查表法-Memoization(记忆): 函数可以用对象去记住先前操纵的成果，从而能避免无谓的运算

避免重复工作，将执行过的运算或操作，缓存起来，如果后续有相同的操作可直接从缓存中查找，没有则进行递归，可大大减少递归的工作量，提高性能。

var count = 0;function factorial(n) { console.log("factorial count = " + count++); if (n == 0) { return 1; } else { return n * factorial(n - 1); }}// var f1 = factorial(6);// var f2 = factorial(5);// var f3 = factorial(4);// >>>>> 结果是函数被调用了：18次function memFactorial(n) { console.log("memFactorial count = " + count++); // JS中函数即可视为一个对象，所以可以直接通过函数名＋点语法给此对象添加属性 if (!memFactorial.cache) { memFactorial.cache = { "0": 1, "1": 1 }; } // hasOwnProperty(n)可以判断对象中是否存在该属性，不会查找原型（但是"in"会先查实例再原型） if (!memFactorial.cache.hasOwnProperty(n)) { // 缓存中不存在的情况下再进行递归，并且将新数组缓存起来 memFactorial.cache[n] = n * memFactorial(n - 1); } // 最终数据都可以在缓存中找到 return memFactorial.cache[n];}var f1 = memFactorial(6);var f2 = memFactorial(5);var f3 = memFactorial(4);// >>>>> 结果是函数被调用了：只有8次，大大的减少了函数被调用的次数

Memoization通用版，但不建议使用，建议自己手动在普通版中实现函数内容

通用版需要缓存特定参数的函数调用结果，即，传入的参数不同，调用函数的时候，其结果需要缓存起来

function memoize(func, cache) { // 缓存池 cache = cache || {}; // 没有则新建 var result = function(arg) { // console.log("memoize count = " + count++); if (!cache.hasOwnProperty(arg)) { cache[arg] = func(arg); } }; return result;} // 使用// 将阶乘函数缓存起来// 只是优化了cache的通用性，但损失了一部分性能var memOpfactorial = memoize(factorial, {"0": 1, "1": 1});var f1 = memOpfactorial(6);var f2 = memOpfactorial(5);var f3 = memOpfactorial(4);// 结果次数依旧是：18次。因此不推荐使用

总结

谨慎使用递归，以防造成死循环，程序崩溃，或者调用栈溢出；

学会使用迭代来替代递归，可以避免递归调用栈或死循环问题出现；

查表法，递归的优化版：Memoization减少重复工作，提升性能。但不推荐使用通用版，相比普通版会损失部分性能。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！