登录你真的懂递归吗？没那么复杂，但也没那么简单
大家好，我是大华。 很多初学者都觉得简单的递归还可以看得懂，稍微复杂些的复杂就觉得很难，甚至有些工作几年的同事也对其避而远之。 其实，只要掌握了正确的方法，递归并没有那么可怕！
一、什么是递归？
打个比方：想象一下，你站在一排长长的队伍里，你想知道你前面有几个人。 但你只能看到你前面那个人，看不到更前面的人。怎么办？ 你问前面那个人：“兄弟，你前面有几个人？” 他也不知道，于是他又问更前面的人：“兄弟，你前面有几个人？” 就这样一直往前问…… 直到问到排在最前面的那个人，他说：“我前面没人，是0个。” 然后，这个答案开始往回传：
最前面的人说：“0个” 他后面的人说：“我前面有1个（就是他）” 再后面的人说：“我前面有2个”… 最后传到你这里：“你前面有 N 个” 这个过程，就是递归！
递归的本质就是： 把一个大问题，拆解成相同的小问题，直到遇到最简单的情况（边界），然后从最简单的情况开始，一层层把结果返回回去，最终解决大问题。
二、递归的两大核心要素
任何正确的递归函数，都必须包含两个关键部分：
1. 递归终止条件（Base Case）
这是递归的“刹车”，防止无限循环。
当问题小到不能再拆时，直接返回结果。
没有它，程序就会无限调用自己，最终导致栈的溢出（Stack Overflow）。
2. 递归调用（Recursive Case）
函数调用自己，但传入的参数是更小规模的问题。
每次调用都在向终止条件靠近。
三、从经典例子开始：计算阶乘
先看最简单的阶乘：5! = 5 × 4 × 3 × 2 × 1
/**
* 计算阶乘的递归函数
* @param {number} n - 要计算阶乘的数字
* @returns {number} - n的阶乘结果
*/
function factorial(n) {
// 1. 基准条件：0的阶乘是1，1的阶乘也是1
if (n === 0 || n === 1) {
console.log(`到达基准条件：factorial(${n}) = 1`);
return 1;
}
// 2. 递归条件：n! = n × (n-1)!
// 3. 递归调用：问题规模从n变成n-1
console.log(`计算 factorial(${n}) = ${n} × factorial(${n - 1})`);
const result = n * factorial(n - 1);
console.log(`得到结果：factorial(${n}) = ${result}`);
return result;
}
// 测试
console.log("最终结果：5的阶乘 =", factorial(5));
运行结果：
计算 factorial(5) = 5 × factorial(4)
计算 factorial(4) = 4 × factorial(3)
计算 factorial(3) = 3 × factorial(2)
计算 factorial(2) = 2 × factorial(1)
到达基准条件：factorial(1) = 1
得到结果：factorial(2) = 2
得到结果：factorial(3) = 6
得到结果：factorial(4) = 24
得到结果：factorial(5) = 120
最终结果：5的阶乘 = 120
看到这个调用过程，是不是对递归有了直观感受？
四、理解递归的关键：调用栈
要真正理解递归，必须明白调用栈的概念。
调用栈就像叠汉堡：每次函数调用就加一片面包，函数返回就拿走一片。
/**
* 演示递归调用栈
*/
function understandCallStack() {
function recursiveDemo(level, maxLevel) {
// 打印当前栈深度
const indent = " ".repeat(level);
console.log(`${indent}进入第 ${level} 层`);
// 基准条件：达到最大深度时停止
if (level >= maxLevel) {
console.log(`${indent}第 ${level} 层：到达基准条件，开始返回`);
return;
}
// 递归调用
recursiveDemo(level + 1, maxLevel);
console.log(`${indent}离开第 ${level} 层`);
}
console.log("=== 递归调用栈演示 ===");
recursiveDemo(0, 3);
}
understandCallStack();
运行结果：
=== 递归调用栈演示 ===
进入第 0 层
进入第 1 层
进入第 2 层
进入第 3 层
第 3 层：到达基准条件，开始返回
离开第 2 层
离开第 1 层
离开第 0 层
这就是为什么递归深度太大会"栈溢出"——汉堡叠得太高，倒掉了！
五、实际应用：文件系统遍历
递归在实际开发中非常实用，比如遍历文件夹：
/**
* 模拟文件系统结构
*/
const fileSystem = {
name: "根目录",
type: "folder",
children: [
{
name: "文档",
type: "folder",
children: [
{ name: "简历.pdf", type: "file" },
{ name: "报告.docx", type: "file" }
]
},
{
name: "图片",
type: "folder",
children: [
{
name: "旅行照片",
type: "folder",
children: [
{ name: "海滩.jpg", type: "file" }
]
},
{ name: "头像.png", type: "file" }
]
},
{ name: "README.txt", type: "file" }
]
};
/**
* 递归遍历文件系统
* @param {object} node - 当前节点
* @param {string} indent - 缩进字符串
*/
function traverseFileSystem(node, indent = "") {
// 基准条件：空节点直接返回
if (!node) return;
// 打印当前节点
const icon = node.type === 'folder' ? '📁' : '📄';
console.log(`${indent}${icon} ${node.name}`);
// 递归条件：如果是文件夹且有子节点，递归遍历
if (node.type === 'folder' && node.children) {
node.children.forEach(child => {
traverseFileSystem(child, indent + " ");
});
}
}
console.log("=== 文件系统遍历 ===");
traverseFileSystem(fileSystem);
运行结果：
=== 文件系统遍历 ===
📁 根目录
📁 文档
📄 简历.pdf
📄 报告.docx
📁 图片
📁 旅行照片
📄 海滩.jpg
📄 头像.png
📄 README.txt
六、递归的适用场景
1. 树形结构操作
- 文件系统遍历
- DOM树操作
- 组织架构图
- 菜单导航
2. 数学问题
- 阶乘计算
- 斐波那契数列
- 汉诺塔问题
3. 分治算法
- 归并排序
- 快速排序
4. 回溯算法
- 迷宫求解
- 数独解题
七、递归的优缺点
优点：
- 代码简洁：复杂问题简单化
- 思路清晰：符合人类思维方式
- 数学表达直接：数学公式容易转换
缺点：
- 性能开销：函数调用有成本
- 栈溢出风险：递归太深会崩溃
- 调试困难：调用链长难跟踪
八、重要改进：避免重复计算
我们来看斐波那契数列的例子，并解决性能问题：
/**
* 斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13...
* 规律：每个数是前两个数之和
*/
// 原始版本：性能很差，有大量重复计算
function fibonacciSlow(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
}
// 优化版本：使用备忘录避免重复计算
function fibonacciMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n === 0) return 0;
if (n === 1) return 1;
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
// 迭代版本：性能最好，不会栈溢出
function fibonacciIterative(n) {
if (n === 0) return 0;
if (n === 1) return 1;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// 性能测试
console.log("斐波那契数列第10项：");
console.log("慢速版本:", fibonacciSlow(10));
console.log("备忘录版本:", fibonacciMemo(10));
console.log("迭代版本:", fibonacciIterative(10));
九、常见错误和解决方案
错误1：忘记基准条件
// 错误：无限递归！
function infiniteRecursion(n) {
return n * infiniteRecursion(n - 1); // 没有停止条件！
}
// 正确：必须有基准条件
function correctRecursion(n) {
if (n <= 1) return 1; // 基准条件
return n * correctRecursion(n - 1);
}
错误2：问题规模没有减小
// 错误：问题规模没有变小
function wrongRecursion(n) {
if (n <= 1) return 1;
return n * wrongRecursion(n); // 还是n，没有减小！
}
// 正确：每次递归问题规模都要减小
function correctRecursion(n) {
if (n <= 1) return 1;
return n * correctRecursion(n - 1); // n-1，问题规模减小
}
十、调试技巧：
- 打印日志：跟踪递归过程
- 使用调试器：观察调用栈变化
- 先写基准条件：确保不会无限递归
- 小数据测试：先用小数据验证正确性
十一、什么时候该用递归？
适合用递归的情况：
- 问题可以分解为相似的子问题
- 数据结构本身是递归的（如树、图）
- 解决方案需要回溯
不适合用递归的情况：
- 性能要求极高
- 递归深度可能很大
- 可以用简单循环解决
十二、实际例子：计算数组深度
让我们用递归解决一个实际问题：
/**
* 计算嵌套数组的深度
* 例如：[1, [2, [3, [4]]]] 的深度是4
*/
function calculateDepth(arr) {
// 基准条件：如果不是数组，深度为0
if (!Array.isArray(arr)) {
return 0;
}
// 基准条件：空数组深度为1
if (arr.length === 0) {
return 1;
}
// 递归条件：深度 = 1 + 子元素的最大深度
let maxChildDepth = 0;
for (const item of arr) {
const childDepth = calculateDepth(item);
if (childDepth > maxChildDepth) {
maxChildDepth = childDepth;
}
}
return 1 + maxChildDepth;
}
// 测试
const testArrays = [
[1, 2, 3], // 深度1
[1, [2, 3]], // 深度2
[1, [2, [3, [4]]]], // 深度4
[] // 深度1
];
testArrays.forEach((arr, index) => {
console.log(`数组${index + 1}:`, JSON.stringify(arr));
console.log(`深度:`, calculateDepth(arr));
console.log("---");
});
总结
递归的核心思想：把大问题分解成相似的小问题
三个关键点：
- 基准条件 - 知道什么时候停止
- 递归条件 - 知道如何分解问题
- 递归调用 - 自己调用自己
使用建议：
- 先确定基准条件
- 确保每次递归问题规模都减小
- 注意性能，必要时改用迭代
- 复杂递归考虑使用备忘录优化
递归就像剥洋葱，一层一层往里剥，直到找到核心。掌握了这个方法，你就能优雅地解决很多复杂问题了！
本文首发于公众号：程序员刘大华，专注分享前后端开发的实战笔记。关注我，少走弯路，一起进步！
📌往期精彩
《SpringBoot+Vue3 整合 SSE 实现实时消息推送》
