尾递归

尾递归，即在函数尾位置调用自身，尾递归是递归的一种特殊情况,也是一种特殊的尾调用。

特点

尾递归在普通的尾调用的基础上多了 2 个特征：

• 在尾部调用的函数自身（self-called）
• 可通过优化，使得计算仅占常量栈空间（stack space）

在递归调用的过程中，系统为每一层的返回点、局部量等开辟了栈来存储，递归次数多了容易造成栈溢出。

我们可以使用尾递归，即在一个函数中所有递归形式的调用都出现在函数末尾，对应尾递归来说，由于只存在一个调用记录，所以永远不会发生“栈溢出”。尾递归优化则使原本 O(n) 的调用栈空间只需要 O(1)。

例子

我们使用常用的阶乘举例

普通的递归函数如下：

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

factorial(5); // 120

如果 n 等于 5，这个方法要执行 5 次，才返回最终的计算表达式，这样每次都要保存这个方法，就容易造成栈溢出，复杂度为 O(n)。

使用尾递归：

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

factorial(5); // 120

每一次返回的就是一个新的函数，不带上一个函数的参数，也就不需要储存上一个函数了。尾递归只需要保存一个调用栈，复杂度 O(1)

更多例子

斐波那契数列

function fibonacci(n) {
  if (n === 1 || n === 2) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

使用尾递归优化：

function fibonacci(n, pre = 1, cur = 1) {
  if (n <= 1) return cur;
  return fibonacci(n - 1, cur, pre + cur);
}

参考链接

• WiKi: 尾调用