尾递归的理解与应用

问题

什么是尾递归？它与普通递归有什么区别？有哪些实际应用场景？

解答

递归基础

递归是指在函数定义中调用函数自身的方法。它将复杂问题转化为规模较小的相似问题来求解。

以计算 x 的 n 次方为例，普通递归实现：

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

计算 pow(2, 4) 的执行过程：

pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2

每次调用都需要保存上一层的状态，递归次数过多会造成栈溢出。

尾递归优化

尾递归是在函数尾部直接调用自身的递归形式。由于只存在一个调用记录，不会发生栈溢出。

对比普通递归和尾递归实现阶乘：

普通递归（复杂度 O(n)）：

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

factorial(5) // 120

尾递归（复杂度 O(1)）：

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

factorial(5) // 120

尾递归每次返回的是新函数调用，不携带上一个函数的参数，因此只需保存一个调用栈。

应用场景

数组求和：

function sumArray(arr, total = 0) {
  if (arr.length === 0) {
    return total;
  }
  return sumArray(arr.slice(1), total + arr[0]);
}

斐波那契数列：

function fibonacci(n, start = 1, total = 1) {
  if (n <= 2) {
    return total;
  }
  return fibonacci(n - 1, total, total + start);
}

数组扁平化：

function flat(arr = [], result = []) {
  arr.forEach(v => {
    if (Array.isArray(v)) {
      result = result.concat(flat(v, []));
    } else {
      result.push(v);
    }
  });
  return result;
}

let a = [1, 2, 3, [1, 2, 3, [1, 2, 3]]];
flat(a); // [1, 2, 3, 1, 2, 3, 1, 2, 3]

关键点

• 尾递归是在函数尾部调用自身，每次返回新函数调用而不保存上层状态
• 尾递归只需保存一个调用栈，空间复杂度为 O(1)，避免栈溢出
• 通过累加器参数（如 total）将中间结果传递给下一次调用
• 适用于数组求和、斐波那契数列、数组扁平化等递归场景
• JavaScript 引擎需要支持尾调用优化（TCO）才能真正实现优化效果