JavaScript 递归
什么是递归?
递归是编程中一种强大的技术,它指的是函数调用自身的过程。简单来说,递归函数就是一个会在内部调用自己的函数。这种技术允许我们用简洁的代码解决一些看似复杂的问题,尤其是那些可以分解为相似子问题的任务。
递归的两个基本要素
- 基本情况(Base Case) - 停止递归的条件
- 递归情况(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)来终止递归
- 每次递归调用应该朝着基本情况靠近
- 递归可能导致栈溢出,需谨慎处理大量递归
- 可以使用记忆化、尾递归等技术优化递归
练习题
- 编写一个递归函数计算数组所有元素的和
- 使用递归实现字符串反转
- 编写一个递归函数,判断一个字符串是否是回文
- 使用递归计算第n个斐波那契数(并尝试优化它)
- 实现一个递归函数,计算一个整数的所有数字之和
进一步学习资源
- MDN Web Docs: 递归函数
- JavaScript 数据结构与算法书籍,学习更多递归应用
- 尝试解决需要递归的算法题(如汉诺塔问题、树的深度优先搜索等)
掌握递归需要实践,所以多尝试使用它解决各种问题,并分析其优缺点和性能特性。