递归算法要点总结
递归是一种强大的编程技术，但对于初学者来说可能有些难以掌握。以下是递归算法需要注意的关键点：
1. 递归三要素
(1) 终止条件 (Base Case)
- 必须有一个或多个明确的递归结束条件
- 防止无限递归导致栈溢出
- 示例：计算阶乘时
n === 0返回 1
(2) 递归调用 (Recursive Case)
- 每次调用都向终止条件靠近
- 通常参数会改变（如 n-1）
- 示例：
factorial(n) = n * factorial(n-1)
(3) 问题分解
- 将大问题分解为相同结构的子问题
- 示例：斐波那契数列
fib(n) = fib(n-1) + fib(n-2)
2. 常见错误与注意事项
递归陷阱
- 忘记终止条件：导致无限递归和栈溢出
- 终止条件不正确：递归无法正常结束
- 递归调用不向终止条件靠近：如传递相同的参数
- 忽略返回值：递归调用的结果没有被使用（如你最初的 flat 函数）
性能问题
- 重复计算：如朴素斐波那契实现会重复计算相同子问题
- 栈溢出：递归太深（可用尾递归优化或改为迭代）
- 空间复杂度高：每次递归调用都会占用栈空间
3. 递归与迭代对比
| 特性 | 递归 | 迭代 |
|---|---|---|
| 代码可读性 | 高（接近数学定义） | 较低 |
| 内存使用 | 高（栈空间） | 低（固定空间） |
| 实现难度 | 简单（对适合的问题） | 较复杂 |
| 适用场景 | 树/图遍历、分治、回溯等 | 线性处理、简单循环 |
4. 递归优化技巧
(1) 尾递归优化
- 使递归调用成为函数中最后执行的操作
- 可以被编译器优化为迭代，减少栈使用
- 示例：
function factorial(n, acc = 1) {
if (n === 0) return acc;
return factorial(n - 1, n * acc); // 尾递归
}(2) 记忆化 (Memoization)
- 存储已计算的结果避免重复计算
- 示例（斐波那契数列）：
const memo = {};
function fib(n) {
if (n in memo) return memo[n];
if (n <= 2) return 1;
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}(3) 转换为迭代
- 使用栈或队列模拟递归调用
- 示例（深度优先搜索的迭代实现）：
function dfs(root) {
const stack = [root];
while (stack.length) {
const node = stack.pop();
// 处理节点
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
}5. 适合使用递归的场景
| 场景 | 例子 |
|---|---|
| 树形结构操作 | 二叉树遍历（前序、中序、后序），DOM 树操作 |
| 分治算法 | 归并排序，快速排序 |
| 回溯算法 | 八皇后问题，数独求解 |
| 数学定义递归的问题 | 斐波那契数列，阶乘计算，汉诺塔问题 |
6. 递归调试技巧
- 打印递归深度：
function recurse(depth = 0) {
console.log(`当前深度: ${depth}`);
// …递归逻辑
}-
可视化调用栈：
- 画递归树帮助理解
- 使用调试器查看调用栈
-
小规模测试：
- 先用简单小数据测试
- 逐步增加复杂度
7. 经典递归示例
阶乘计算
function factorial(n) {
if (n === 0) return 1; // 终止条件
return n * factorial(n - 1); // 递归调用
}斐波那契数列（低效版）
function fib(n) {
if (n <= 2) return 1; // 终止条件
return fib(n - 1) + fib(n - 2); // 递归调用
}数组求和
function sum(arr, index = 0) {
if (index === arr.length) return 0; // 终止条件
return arr[index] + sum(arr, index + 1); // 递归调用
}记住，理解递归需要时间和练习。从简单问题开始，逐步构建对递归思维的理解。当遇到困难时，画递归调用图通常会有很大帮助。