跳到主要内容

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

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