JavaScript 递归

递归是编程中一个重要的概念，指的是函数直接或间接调用自身的过程。在 JavaScript 中，递归可以优雅地解决许多问题，特别是那些具有自相似性质的问题。

基本递归示例

最简单的递归例子是计算阶乘：

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;  // 基本情况（终止条件）
  }
  return n * factorial(n - 1);  // 递归调用
}

console.log(factorial(5)); // 输出: 120

递归的组成部分

1. 基本情况（Base Case）：停止递归的条件，防止无限递归
2. 递归情况（Recursive Case）：函数调用自身的部分，通常问题规模会减小

另一个常见例子：斐波那契数列

function fibonacci(n) {
  if (n <= 1) {
    return n;  // 基本情况
  }
  return fibonacci(n - 1) + fibonacci(n - 2);  // 递归调用
}

console.log(fibonacci(6)); // 输出: 8

递归与迭代的比较

递归的优点：

• 代码通常更简洁、更易读
• 更自然地表达某些算法（如树遍历、分治算法）

递归的缺点：

• 可能产生更高的内存开销（调用栈）
• 在某些情况下性能不如迭代版本

尾递归优化

ES6 引入了尾调用优化（TCO），可以优化特定形式的递归（尾递归）：

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  }
  return factorial(n - 1, n * acc);  // 尾递归调用
}

注意：目前大多数 JavaScript 引擎尚未实现 TCO。

常见递归应用场景

1. 树和图的遍历
2. 分治算法（如快速排序、归并排序）
3. 解析嵌套数据结构（如 JSON 处理）
4. 解决数学问题（如汉诺塔问题）

递归陷阱

1. 无限递归：忘记设置或错误设置基本情况

   function infinite() {
     infinite();  // 无限递归！
   }
   

2. 栈溢出：递归深度太大导致调用栈溢出

3. 重复计算：如朴素斐波那契实现会重复计算很多子问题

递归与异步编程

递归也可以用于异步操作，例如：

function asyncRecursion(count) {
  if (count <= 0) return Promise.resolve();
  
  return someAsyncOperation()
    .then(() => asyncRecursion(count - 1));
}

总结

递归是 JavaScript 中强大的编程技术，适合解决可以分解为相似子问题的问题。使用时要注意设置正确的终止条件，并考虑性能影响。对于深度递归或性能敏感的场景，可能需要考虑使用迭代或其他优化方法。