JavaScript尾递归的实现及应用场景

什么是尾递归

递归函数是在函数内部调用自身的函数，而尾递归则指在函数结束时递归调用自身函数，此时函数不会有任何剩余操作。
尾递归函数的实现方式可以极大地减少函数在内存中的占用，避免了栈溢出问题，是函数编写中的高级技巧。

尾递归的实现

尾递归函数不是按照标准递归方式进行运算，而是以‘一步计算出最终结果’的方式进行，每次递归将结果作为参数传递到下层函数中，直到达到递归终止条件。核心代码如下：

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

tailFactorial就是一个尾递归的实现，调用递归函数时直接把结果返回并退出函数。而factorial就是调用尾递归函数的方式，每次将结果作为参数传递给下一层函数，从而达到一次性计算阶乘的目的。

尾递归的应用场景

斐波那契数列

斐波那契数列是一组数列，数列的第(i+2)项等于第i项和第(i+1)项的和。
非尾递归实现代码如下：

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

这种实现方式，除了n=0/1两种情况外，一般都会有很多重复的计算导致程序运行效率低下。尾递归可以避免这个问题，核心代码如下：

function tailFibonacci (n, curr, next) {
  if (n === 0) return curr;
  return tailFibonacci(n - 1, next, curr + next);
}

function fibonacci (n) {
  return tailFibonacci(n, 0, 1);
}

这种实现方式中，每一项都是由前两项直接计算而来，而非通过递归累加得到。

函数式编程

开发中，函数式编程中的高阶函数常常会使用到尾递归，其中最典型的例子就是函数调用栈。

一个简单的例子代码如下：

function sum(x, y, ...rest) {
  if (rest.length === 0) {
    return x + y;
  }
  return sum(x + y, rest[0], ...rest.slice(1));
}

这个函数用于构造多个值相加的函数，使用尾递归可以极大地提高代码执行效率。

小结

在JavaScript编程中，递归函数是不可避免的。但又会导致栈溢出等问题，尾递归可以解决很多的递归问题。相比起普通递归函数，尾递归更容易理解，更容易维护。