程序调用自身的编程技巧称为递归（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 都是边界条件。

递归特点：

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

执行上下文

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

如果对阶乘函数分析的话，会发现阶乘会不断地压栈。

如果压栈的数量比较大的话就会有可能出现爆栈的情况。

如何优化？

尾调用

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

例子

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

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

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

这两者的区别是执行上下文栈变化不一样。

为了模拟执行上下文栈的行为，定义执行上下文栈是一个数组。

ESCtack = [];

第一段代码执行上下文栈变化：

// 伪代码
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 factorial(n, res) {
  if (n === 1) {
    debugger
    return res;
  }
  return factorial(n - 1, n * res);
}
console.log(factorial(5, 1)); // 120

斐波那契数列

function fibonacci(n, sum1 = 1, sum2 = 1) {
  if (n <= 2) return sum2;
  return fibonacci(n - 1, sum2, sum1 + sum2);
}
console.log(fibonacci(5)); // 15

求和

function sum(n, res = 0) {
  if (n < 1) return res;
  return sum(n - 1, n + res);
}
console.log(sum(5)); // 5

理论上只用一个执行上下文，但是 Chrome 的 v8 没有做尾调用优化，所以还是会压栈。

参考：

[1] JavaScript专题之递归

Programing learning note

javascript 递归

阶乘

斐波那契数列

递归条件

执行上下文

尾调用

优化例子