跳到主要内容

JavaScript 递归

什么是递归？​

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

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

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

递归的工作原理​

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

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. 计算阶乘​

阶乘是递归的经典应用：

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. 斐波那契数列​

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

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. 优化的斐波那契实现（使用记忆化）​

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. 目录树遍历​

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

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 树：

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. 深拷贝对象​

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

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"错误：

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

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

2. 尾递归优化​

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

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

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

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

3. 递归 vs 迭代​

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

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 数据结构与算法书籍，学习更多递归应用
  • 尝试解决需要递归的算法题（如汉诺塔问题、树的深度优先搜索等）

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