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即原數組長度的一半，作為內循環終止的條件*/

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次，大大的減少了函數被調用的次數

/*  遞歸優化通用版，性能不如普通版，需要緩存每次調用結果, 即內部函數   */ 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次。因此不推薦使用