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

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];}/* 迭代过程分析  假设： var test = [1, 3, 9, 7, 4, 8, 6, 5, 0, 2]; // len == 10  work = [[1], [3], [9], [7], [4], [8], [6], [5], [0], [2], []]; // len == 11;  // 迭代(二分法)  a) lim: 11 > 1    1) k = 0, work[0] = myMerge([1], [3]) ==> work[0] = [1, 3]    2) k = 2, work[1] = myMerge([9], [7]) ==> work[1] = [7, 9]    3) k = 4, work[2] = myMerge([4], [8]) ==> work[2] = [4, 8]    4) k = 6, work[3] = myMerge([6], [5]) ==> work[3] = [5, 6]    5) k = 8, work[4] = myMerge([0], [2]) ==> work[4] = [0, 2]    > 在后面添加个空数组是为了数组长度为奇数时的情况，能有个对象做比较，否则会出现越界错误  b) lim: 6 > 1, work = [[1,3], [7,9], [4,8], [5,6], [0,2], []];    1) k = 0, work[0] = myMerge([1,3], [7,9]) ==> work[0] = [1, 3, 7, 9]    2) k = 2, work[1] = myMerge([4,8], [5,6]) ==> work[1] = [4, 5, 6, 8]    3) k = 4, work[2] = myMerge([0,2], [])  ==> work[2] = [0,2]    > 最后一个[]会被myMerge函数给合并，所以不用担心添加的空数组对后续产生影响  c) lim: 3 > 1, work = [[1, 3, 7, 9], [4, 5, 6, 8], [0, 2], []];    1) k = 0, work[0] = myMerge([1, 3, 7, 9], [4, 5, 6, 8]) ==> work[0] = [1,3,4,5,6,7,8,9]    2) k = 2, work[1] = myMerge([0, 2], []) ==> work[1] = [0, 2]  d) lim: 2, work = [[1,3,4,5,6,7,8,9], [0,2], []];    1) k = 0, work[0] = myMerge([1,3,4,5,6,7,8,9], [0,2]) ==> work[0] = [0,1,2,3,4,5,6,7,8,9]    > 至此排序整个过程全部完成  // 关键点  a) 将数组中的每个元素数组化，以便后续存放已经排好序的元素  b) k的取值，k+=2, 每次取两个数组进行比较，形成一个新的数组  c) 一定要在比较完之后附加空数组，否则会在数组个数为奇数个的时候出现访问越界错误  d) 最外层循环的lim的取值, lim = (lim + 1) / 2即原数组长度的一半，作为内循环终止的条件*/