递归

# 定义

递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明

简而言之：程序调用自身的编程技巧称为递归(recursion)。

通过一个简单的例子来说明一下：

// 以阶乘为例：

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}
console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

再看看一个斐波那契数列；

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)) // 1 1 2 3 5

# 递归条件

从这两个例子中，我们可以看出：

构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。

总结一下递归的特点：

• 子问题须与原始问题为同样的事，且更为简单；
• 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

了解这些特点可以帮助我们更好的编写递归函数。

# 执行上下文栈

当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。

试着对阶乘函数分析执行的过程，我们会发现，JavaScript 会不停的创建执行上下文压入执行上下文栈，对于内存而言，维护这么多的执行上下文也是一笔不小的开销呐！那么，我们该如何优化呢？

答案就是尾调用(尾递归)。

# 尾调用

尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。

举个例子：

// 尾调用
function f(x){
    return g(x);
}

然而

// 非尾调用
function f(x){
    return g(x) + 1;
}

并不是尾调用，因为 g(x) 的返回值还需要跟 1 进行计算后，f(x)才会返回值。

两者又有什么区别呢？答案就是执行上下文栈的变化不一样。

为了模拟执行上下文栈的行为，让我们定义执行上下文栈是一个数组：

ECStack = [];

我们模拟下第一个尾调用函数执行时的执行上下文栈变化：

// 伪代码
ECStack.push(<f> functionContext);

ECStack.pop();

ECStack.push(<g> functionContext);

ECStack.pop();

我们再来模拟一下第二个非尾调用函数执行时的执行上下文栈变化：

ECStack.push(<f> functionContext);

ECStack.push(<g> functionContext);

ECStack.pop();

ECStack.pop();

也就说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

所以我们只用把阶乘函数改造成一个尾递归形式，就可以避免创建那么多的执行上下文。尾调用是我们平时实现递归操作的一种方式, 通过在函数末尾调用另一个函数， 来抹除上一个函数的堆栈记录， 可以理解为是一种任务承接的方式，但是我们该怎么做呢？

function f(index, total) {
  if(index-- === 1) {
    return total
  }
  g(index, total + index)
}

function g( index, total ) {
  f( index, total )
}

尾递归和普通递归的区别就是， 尾递归的递归方式是在函数最后一步操作调用自身， 并将本轮计算结果以参数形式传入

function loop(index, total) {
  if(index-- === 1) {
    return total
  }
  return loop(index, total + index)
}

loop(100, 0)

# 阶乘函数优化

我们需要做的就是把所有用到的内部变量改写成函数的参数，以阶乘函数为例：

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

console.log(factorial(4, 1)) // 24

# 尾调用优化

在ES6中， 我们将迎来尾递归优化， 通过尾递归优化， javascript代码在解释成机器码的时候， 将会向while看齐， 也就是说， 同时拥有数学表达能力和while的效能。

ES6的“尾调用优化”的原理就是覆盖掉自身的函数执行记录， 也就是将递归变为循环， 只保存一个调用记录，这样就不会发生爆栈的情况了

# 浏览器的实现情况

虽然是ES6的规范， 浏览器也实现了， 但实际上平时使用时“尾调用优化”是默认关闭的。 为什么！因为浏览器不敢开哦。 因为一旦开了尾调用优化， 就等于放弃了存留函数的堆栈信息， 当开发者调错时会十分困难， 找不到正确的堆栈信息， 当然可以利用js的元编程强行开启

# 其他避免爆栈手段

• 使用蹦床函数， 将递归拉平
• 直接将递归改写成循环
• 使用元编程强行开启浏览器的“尾递归优化”