递归

作用：递归只是让解决方案更清晰，并没有性能上的优势，如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解(但在我看来，递归有时候也很难理解)

斐波那契数列就是运用递归的想法进行计算

基线条件和递归条件

每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环

// 基线条件
if (newArr.length === 1) {
  return newArr[0];
}

1 2	// 递归条件 return newArr.pop() + sum(newArr);

上面为利用递归进行累加的函数

栈只有两种操作：压入（插入）和弹出（删除并读取）

数组的压入与弹出

1 2	array.pop() //弹出 array.push() //压入

计算机在内部使用被称为调用栈的栈

function hi() {
  console.log('hi');
}
function bye() {
  hi();
  console.log('bye');
}
bye();

下面分析调用bye()发生的事

首先会为bye分配内存控件，以及该函数所创建的变量也会放到内存

接着里面会调用另一个函数，所以会在bye上面压入另一个函数hi()，开辟新的内存，同时为其变量分配内存，最后如下图，就像压入一样的操作，根据调用顺序压入内存

接着就是函数执行，从上到下执行，先弹出最顶部的函数（对应嵌套最深的函数）进行执行，接着一步一步往下执行，最后到最底部的函数（就是最外层函数）

1
2
3

输出：
hi
bye

简单阶乘的实现使用了递归

let fact = function (x) {
  if(x == 1) {
    return 1
  } else {
    return x * fact(n-1)
  }
}

分析其调用栈如何变化