递归

1. 简单的递归

function rec(x){
if(x!==1){
   console.log(x)
   rec(x-1)
   console.log(x) 
   }   
}
rec(5) //输出为5 4 3 2 2 3 4 5

执行顺序解读：

1. rec(5) 5 调用自身，欠x=5一次rec下的执行
2. rec(4) 4 调用自身，欠x=4一次 rec 下的执行
3. rec(3) 3 调用自身，欠x=3 一次 rec 下的执行
4. rec(2) 2 调用自身，欠 x=2 一次 rec 下的执行
5. rec(1) 退出，开始还第四步的帐 打印出2
6. 开始还第三步的帐打印出3
7. 开始还第二步的帐打印出4
8. 开始还第一步的帐打印出5

2. 双重递归执行顺序

Array.prototype.mergeSort = function() {
  const rec = (arr) => {
    if (arr.length === 1) { return arr};
    const mid = Math.floor(arr.length /2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = rec(left);
    const orderRight = rec(right);
    const res = [];
    while(orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res;
  }
  rec(this).forEach((n, i) => {
    this[i] = n;
  })
}
const array = [5,4,3,2,1];
array.mergeSort();

1.调用 mergeSort并加入到一个新的栈里，执行 rec([5,4,3,2,1])并加入到栈里,arr = [5,4,3,2,1]，mid = 2,left=[5,4],right=[3,2,1]，执行到
const orderLeft = rec(left) 时阻断了orderLeft 以下的执行，欠arr=[5,4,3,2,1]一次 orderLeft 以下的执行

2. 调用 const orderLeft = rec([5, 4])并加入到一个新的栈里，此时 mid = 1, left=[5],right=[4]，执行到 const orderLeft = rec(left) 时再次阻断了 orderLeft 以下的执行
   欠rec([5, 4])这个栈一次 orderLeft 以下的执行

3. 调用 const orderLeft = rec([5])并加入到一个新的栈里，此时 arr.length === 1 return [5]所以直接出栈，继续第二步的栈里还未执行完的 orderLeft 以下的执行
   const orderRight = rec([4])再次调用自身阻断了 orderRight 以下的执行，欠 rec([5,4])这个栈一次 orderRight 以下的执行

4. 调用 const orderRight = rec([4]) 并加入到一个新的栈里，此时 arr.length === 1 return [4]所以直接出栈，继续第三步里rec([5,4])这个栈里还未执行的 orderRight 以下的操作
   此时 orderLeft = [5],orderRight=[4]，进入 while 循环 res值为 [4,5] 然后 reutn res，rec([5,4])这个栈也执行完成，出栈，此时栈里只有第一步里的
   rec([5,4,3,2,1])，当前的 const orderLeft = [4,5]，然后继续执行 orderLeft 下面的操作，运行到 const orderRight = rec([3,2,1])的时候再次调用自身
   阻断了 orderRight 以下的执行，欠 rec([5,4,3,2,1])这个栈 一次 orderRight 以下的执行

5. 调用 const orderRight = rec([3,2,1])并加入到一个新的栈里，此时 mid = 1, left=[3],right=[2,1]，运行到 const orderLeft = rec([3]); 的时候再次调用自身
   阻断了 orderRight 以下的执行，欠 const orderRight = rec([3,2,1]) 这个栈一次 orderLeft 以下的执行

6. 调用 const orderLeft = rec([3]) 并加入一个新的栈里，此时 arr.length === 1 return [3]，所以直接出栈，继续第五步 rec([3,2,1]) 栈里 orderLeft 下面的操作
   运行到 const orderRight = rec([2,1])的时候再次调用自身，阻断了 orderRight 以下的执行，欠 const orderRight = rec([3,2,1]) 这个栈一次 orderRight 以下的操作

7. 调用 const orderRight = rec([2,1]) 并加入一个新的栈里，此时 mide=1,left=[2],right=[1]，执行到 const orderLeft = rec([2]) 的时候再次调用自身
   阻断了 orderLeft 以下的操作，欠 const orderRight = rec([2,1]) 这个栈一次 orderLeft 以下的执行

8. 调用 const orderLeft = rec([2]) 并加入到一个新的栈里，因为 arr.length === 1 所以直接 return [2]出栈，继续第七步 const orderRight = rec([2,1]) 栈里 orderLeft 以下
   的执行，执行到 const orderRight = rec([1]) 时调用自身，阻断了 orderRight 以下的执行，欠 const orderRight = rec([2,1]) 这个栈一次 orderRight 以下的执行

9. 调用 const orderRight = rec([1]) 并加入到一个新的栈里，因为 arr.length === 1 所以直接 return [1]出栈，继续 const orderRight = rec([2,1]) 这个栈 orderRight
   以下的操作，此时 orderLeft = [2], orderRight=[1]，进入 while 循环，最后 res=[1,2]，return [1,2] const orderRight = rec([2,1]) 这个栈执行完成，从栈里移出，继续
   const orderRight = rec([3,2,1]) 这个栈里 orderRight 以下的操作，此时 orderLeft=[3],orderRight=[1,2]，进入 while 循环，结束后 res=[1,2,3],
   const orderRight = rec([3,2,1]) 这个栈也执行完成从栈里移出，继续 rec([5,4,3,2,1]) 这个栈里 orderRight 以下的执行，此时 orderLeft=[4,5],orderRight=[1,2,3]，进入while 循环
   最后 return [1,2,3,4,5]，rec([5,4,3,2,1])这个栈也执行完成从栈里移出。