JavaScript 递归

什么是递归？

递归是编程中一种强大的技术，它指的是函数调用自身的过程。简单来说，递归函数就是一个会在内部调用自己的函数。这种技术允许我们用简洁的代码解决一些看似复杂的问题，尤其是那些可以分解为相似子问题的任务。

递归的两个基本要素

1. 基本情况(Base Case) - 停止递归的条件
2. 递归情况(Recursive Case) - 函数调用自身的部分

如果没有基本情况，递归将无限进行，导致栈溢出错误。

递归的工作原理

让我们通过一个简单的例子来理解递归是如何工作的：

javascript

function countdown(n) {
  // 基本情况
  if (n <= 0) {
    console.log("发射！");
    return;
  }
  
  // 显示当前数字
  console.log(n);
  
  // 递归情况
  countdown(n - 1);
}

// 调用递归函数
countdown(5);

输出结果：

5
4
3
2
1
发射！

在这个例子中：

• 当 n > 0 时，函数打印当前值，然后以 n-1 为参数调用自己
• 当 n <= 0 时（基本情况），函数打印"发射！"并停止递归

递归调用堆栈

当我们使用递归时，每次函数调用都会在调用堆栈上创建一个新的执行环境。让我们可视化上述 countdown(5) 的调用堆栈：

常见递归示例

1. 计算阶乘

阶乘是递归的经典应用：

javascript

function factorial(n) {
  // 基本情况
  if (n === 0 || n === 1) {
    return 1;
  }
  
  // 递归情况
  return n * factorial(n - 1);
}

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

计算过程：

• factorial(5) = 5 * factorial(4) = 5 * 24 = 120
• factorial(4) = 4 * factorial(3) = 4 * 6 = 24
• factorial(3) = 3 * factorial(2) = 3 * 2 = 6
• factorial(2) = 2 * factorial(1) = 2 * 1 = 2
• factorial(1) = 1 (基本情况)

2. 斐波那契数列

斐波那契数列是另一个递归的典型应用：

javascript

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

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

斐波那契数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

性能警告

上面的斐波那契函数实现虽然直观，但效率较低，因为它重复计算了许多子问题。对于较大的输入值，应使用动态规划或记忆化技术优化。

3. 优化的斐波那契实现（使用记忆化）

javascript

function fibonacciMemoized(n, memo = {}) {
  // 检查是否已计算过
  if (memo[n] !== undefined) {
    return memo[n];
  }
  
  // 基本情况
  if (n <= 1) {
    return n;
  }
  
  // 存储计算结果
  memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemoized(50)); // 快速计算大数值

递归的实际应用场景

1. 目录树遍历

递归非常适合处理树形结构，如文件系统：

javascript

function traverseFileSystem(directory, level = 0) {
  // 获取目录内容
  const files = getFilesInDirectory(directory); // 假设这个函数存在
  
  files.forEach(file => {
    // 打印当前文件/目录名，缩进表示层级
    console.log('  '.repeat(level) + file.name);
    
    // 如果是目录，递归遍历
    if (file.isDirectory) {
      traverseFileSystem(file.path, level + 1);
    }
  });
}

2. DOM 遍历

递归可以用来遍历和操作 DOM 树：

javascript

function traverseDOM(element, callback) {
  // 对当前元素执行操作
  callback(element);
  
  // 递归遍历所有子元素
  const children = element.children;
  for (let i = 0; i < children.length; i++) {
    traverseDOM(children[i], callback);
  }
}

// 使用示例
traverseDOM(document.body, element => {
  console.log(element.tagName);
});

3. 深拷贝对象

递归可用于创建对象的深拷贝：

javascript

function deepCopy(obj) {
  // 基本情况：如果不是对象，直接返回
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  // 创建新对象/数组
  const copy = Array.isArray(obj) ? [] : {};
  
  // 递归复制所有属性
  for (const key in obj) {
    if (Object.prototype.hasOwnProperty.call(obj, key)) {
      copy[key] = deepCopy(obj[key]);
    }
  }
  
  return copy;
}

const original = { a: 1, b: { c: 2 } };
const copied = deepCopy(original);
console.log(copied); // { a: 1, b: { c: 2 } }
copied.b.c = 3;
console.log(original.b.c); // 2 (未被修改)

递归的注意事项

1. 栈溢出风险

JavaScript 引擎对调用栈的深度有限制。过深的递归可能导致"Maximum call stack size exceeded"错误：

javascript

function infiniteRecursion() {
  infiniteRecursion(); // 无基本情况！
}

// 不要运行上面的函数，它会导致栈溢出错误

2. 尾递归优化

尾递归是递归的一种特殊形式，其中递归调用是函数执行的最后一个操作：

javascript

function factorialTailRecursive(n, accumulator = 1) {
  // 基本情况
  if (n <= 1) {
    return accumulator;
  }
  
  // 尾递归
  return factorialTailRecursive(n - 1, n * accumulator);
}

console.log(factorialTailRecursive(5)); // 120

一些编程语言的编译器可以优化尾递归，防止栈溢出。但在大多数JavaScript环境中，尾递归优化并不被广泛支持。

3. 递归 vs 迭代

很多递归问题也可以用迭代（循环）解决。例如，阶乘的迭代版本：

javascript

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialIterative(5)); // 120

选择建议

• 递归通常更清晰地表达问题的结构，特别是处理树和图这样的数据结构时
• 迭代通常更高效，不受调用栈限制
• 对性能要求高的场合，考虑使用迭代或优化的递归

总结

递归是一种优雅且强大的编程技术，通过函数调用自身来解决复杂问题。它特别适合处理具有自相似结构的问题，如树遍历、排序算法和数学运算。

关键要点：

• 递归函数必须有基本情况(Base Case)来终止递归
• 每次递归调用应该朝着基本情况靠近
• 递归可能导致栈溢出，需谨慎处理大量递归
• 可以使用记忆化、尾递归等技术优化递归

练习题

1. 编写一个递归函数计算数组所有元素的和
2. 使用递归实现字符串反转
3. 编写一个递归函数，判断一个字符串是否是回文
4. 使用递归计算第n个斐波那契数（并尝试优化它）
5. 实现一个递归函数，计算一个整数的所有数字之和

进一步学习资源

• MDN Web Docs: 递归函数
• JavaScript 数据结构与算法书籍，学习更多递归应用
• 尝试解决需要递归的算法题（如汉诺塔问题、树的深度优先搜索等）

掌握递归需要实践，所以多尝试使用它解决各种问题，并分析其优缺点和性能特性。