js - js 函数递归 - 《public》

函数直接或间接调用自身，这就是递归（recursion）。下面就是通过递归，计算斐波那契数列的代码。

function fib(num) {
  if (num === 0) return 0;
  if (num === 1) return 1;
  return fib(num - 2) + fib(num - 1);
}
fib(6) // 8

上面代码中，fib函数内部又调用了fib，计算得到斐波那契数列的第 6 个元素是 8。

无限递归将会导致栈溢出，应该避免无限递归。

无限递归 vs 死循环

无限递归会导致栈溢出，会报错。

死循环不会报错，也不会导致栈溢出，但是会导致程序不断执行，可能会出现死机的情况。

任何代码的执行都必须有一个执行环境，执行环境为代码的执行提供支持。执行环境是放到执行栈中的。

每个函数的调用，都需要创建（入栈）一个函数的执行环境，只有在函数调用结束，对应的执行环境才会被销毁（出栈）。

执行栈有相对固定的大小，如果执行环境太多，执行栈无法容纳，会报错。

如果一个函数最后一条语句是调用函数，并且调用函数不是表达式的一部分，则该语句称为尾调用。

function test() {
  // => ...
  // a(); // 函数 a 就是尾调用
}

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

function test() {
  // => ...
  // test(); // 函数 test 就是尾递归
}

某些语言或执行环境会对尾调用进行优化，它们会立即销毁当前函数，避免执行栈空间被占用。

在浏览器执行环境中，尾调用没有优化。但在 nodejs 环境中有优化。