递归并不总代表低效率，有些场景中，递归的效率反而更高，比如计算x的m次幂，常规算法，需要m次乘法运算，下面的算法，却将时间复杂度降到了O(logn)
//计算x的m次幂（递归实现） //时间复杂度O(logn) function expRec(x, m) { if (m == 0) { return 1; } var y = expRec(x, Math.floor(m / 2)); y = y * y; if (m % 2 != 0) { y = x * y } return y; }
当然，这其中并不光是递归的功劳，其效率的改进 主要依赖于一个数学常识： x^m = [x^(m/2)]^2，关于这个问题，还有一个思路很独特的非递归解法，巧妙的利用了二进制的特点
//将10进制数转化成2进制 function toBin(dec) { var bits = []; var dividend = dec; var remainder = 0; while (dividend >= 2) { remainder = dividend % 2; bits.push(remainder); dividend = (dividend - remainder) / 2; } bits.push(dividend); bits.reverse(); return bits.join(""); } //计算x的m次幂（非递归实现） //很独特的一种解法 function exp(x, m) { var y = 1; var bin = toBin(m).split(''); //先将m转化成2进制形式 for (var j = 0; j < bin.length; j++) { y = y * 2; //如果2进制的第j位是1，则再*x if (bin[j] == "1") { y = x * y } } return y; } //println(expRec(2, 5)); //println(exp(2, 5));
再来看看经典的多项式求值问题：
给定一串实数An，An-1，...，A1，A0 和一个实数X，计算多项式Pn(x)的值
著名的Horner公式：
已经如何计算：
显然有：
这样只需要 N次乘法+N次加法
//多项式求值 //N次乘法+N次加法搞定，伟大的改进！ function horner(A, x) { var n = A.length - 1 var p = A[n]; for (var j = 0; j < n; j++) { p = x * p + A[n - j - 1]; } return p; } //计算: y(2) = 3x^3 + 2x^2 + x -1; var A = [-1, 1, 2, 3]; var y = horner(A, 2); alert(y);//33
多数问题：
一个元素个数为n的数组，希望快速找出其中大于出现次数>n/2的元素（该元素也称为多数元素）。通常可用于选票系统，快速判定某个候选人的票数是否过半。最优算法如下：
//找出数组A中“可能存在”的多数元素 function candidate(A, m) { var count = 1, c = A[m], n = A.length - 1; while (m < n && count > 0) { m++; if (A[m] == c) { count++; } else { count--; } } if (m == n) { return c; } else { return candidate(A, m + 1); } } //寻找多数元素 //时间复杂度O(n) function majority(A) { var c = candidate(A, 0); var count = 0; //找出的c，可能是多数元素，也可能不是， //必须再数一遍，以确保结果正确 for (var i = 0; i < A.length; i++) { if (A[i] == c) { count++; } } //如果过半，则确定为多数元素 if (count > Math.floor(A.length / 2)) { return c; } return null; } var m = majority([3, 2, 3, 3, 4, 3]); alert(m);
以上算法基于这样一个结论：在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新序列中还是多数元素
证明如下：
如果原序列的元素个数为n，多数元素出现的次数为x，则 x/n > 1/2
去掉二个不同的元素后，
a)如果去掉的元素中不包括多数元素，则新序列中 ，原先的多数元素个数/新序列元素总数 = x/(n-2) ，因为x/n > 1/2 ，所以 x/(n-2) 也必然>1/2
b)如果去掉的元素中包含多数元素，则新序列中 ，原先的多数元素个数/新序列元素总数 = (x-1)/(n-2) ，因为x/n > 1/2 =》 x>n/2 代入 (x-1)/(n-2) 中，
有 (x-1)/(n-2) > (n/2 -1)/(n-2) = 2(n-2)/(n-2) = 1/2
下一个问题：全排列
function swap(A, i, j) { var t = A[i]; A[i] = A[j]; A[j] = t; } function println(msg) { document.write(msg + "<br/>"); } //全排列算法 function perm(P, m) { var n = P.length - 1; if (m == n) { //完成一个新排列时，输出 println(P); return; } for (var j = m; j <= n; j++) { //将起始元素与后面的每个元素交换 swap(P, j, m); //在前m个元素已经排好的基础上 //再加一个元素进行新排列 perm(P, m + 1); //把j与m换回来，恢复递归调用前的“现场"， //否则因为递归调用前，swap已经将原顺序破坏了， //导致后面生成排序时，可能生成重复 swap(P, j, m); } } perm([1, 2, 3], 0); //1,2,3 //1,3,2 //2,1,3 //2,3,1 //3,2,1 //3,1,2
分治法：
要点：将问题划分成二个子问题时，尽量让子问题的规模大致相等。这样才能最大程度的体现一分为二，将问题规模以对数折半缩小的优势。