你真的懂递归吗？没那么复杂，但也没那么简单

大家好，我是大华。 很多初学者都觉得简单的递归还可以看得懂，稍微复杂些的复杂就觉得很难，甚至有些工作几年的同事也对其避而远之。其实，只要掌握了正确的方法，递归并没有那么可怕！

一、什么是递归？

打个比方：想象一下，你站在一排长长的队伍里，你想知道你前面有几个人。 但你只能看到你前面那个人，看不到更前面的人。怎么办？ 你问前面那个人：“兄弟，你前面有几个人？” 他也不知道，于是他又问更前面的人：“兄弟，你前面有几个人？” 就这样一直往前问…… 直到问到排在最前面的那个人，他说：“我前面没人，是0个。” 然后，这个答案开始往回传：

最前面的人说：“0个” 他后面的人说：“我前面有1个（就是他）” 再后面的人说：“我前面有2个”… 最后传到你这里：“你前面有 N 个”这个过程，就是递归！

递归的本质就是：把一个大问题，拆解成相同的小问题，直到遇到最简单的情况（边界），然后从最简单的情况开始，一层层把结果返回回去，最终解决大问题。

二、递归的两大核心要素

任何正确的递归函数，都必须包含两个关键部分：

1. 递归终止条件（Base Case）

这是递归的“刹车”，防止无限循环。

当问题小到不能再拆时，直接返回结果。

没有它，程序就会无限调用自己，最终导致栈的溢出（Stack Overflow）。

2. 递归调用（Recursive Case）

函数调用自己，但传入的参数是更小规模的问题。

每次调用都在向终止条件靠近。

三、从经典例子开始：计算阶乘

先看最简单的阶乘：5! = 5 × 4 × 3 × 2 × 1

1/**
2 * 计算阶乘的递归函数
3 * @param {number} n - 要计算阶乘的数字
4 * @returns {number} - n的阶乘结果
5 */
6function factorial(n) {
7    // 1. 基准条件：0的阶乘是1，1的阶乘也是1
8    if (n === 0 || n === 1) {
9        console.log(`到达基准条件：factorial(${n}) = 1`);
10        return 1;
11    }
12    
13    // 2. 递归条件：n! = n × (n-1)!
14    // 3. 递归调用：问题规模从n变成n-1
15    console.log(`计算 factorial(${n}) = ${n} × factorial(${n - 1})`);
16    const result = n * factorial(n - 1);
17    console.log(`得到结果：factorial(${n}) = ${result}`);
18    
19    return result;
20}
21
22// 测试
23console.log("最终结果：5的阶乘 =", factorial(5));
24

运行结果：

1计算 factorial(5) = 5 × factorial(4)
2计算 factorial(4) = 4 × factorial(3)
3计算 factorial(3) = 3 × factorial(2)
4计算 factorial(2) = 2 × factorial(1)
5到达基准条件：factorial(1) = 1
6得到结果：factorial(2) = 2
7得到结果：factorial(3) = 6
8得到结果：factorial(4) = 24
9得到结果：factorial(5) = 120
10最终结果：5的阶乘 = 120
11

看到这个调用过程，是不是对递归有了直观感受？

四、理解递归的关键：调用栈

要真正理解递归，必须明白调用栈的概念。

调用栈就像叠汉堡：每次函数调用就加一片面包，函数返回就拿走一片。

1/**
2 * 演示递归调用栈
3 */
4function understandCallStack() {
5    function recursiveDemo(level, maxLevel) {
6        // 打印当前栈深度
7        const indent = "  ".repeat(level);
8        console.log(`${indent}进入第 ${level} 层`);
9        
10        // 基准条件：达到最大深度时停止
11        if (level >= maxLevel) {
12            console.log(`${indent}第 ${level} 层：到达基准条件，开始返回`);
13            return;
14        }
15        
16        // 递归调用
17        recursiveDemo(level + 1, maxLevel);
18        
19        console.log(`${indent}离开第 ${level} 层`);
20    }
21    
22    console.log("=== 递归调用栈演示 ===");
23    recursiveDemo(0, 3);
24}
25
26understandCallStack();
27

运行结果：

1=== 递归调用栈演示 ===
2进入第 0 层
3  进入第 1 层
4    进入第 2 层
5      进入第 3 层
6      第 3 层：到达基准条件，开始返回
7    离开第 2 层
8  离开第 1 层
9离开第 0 层
10

这就是为什么递归深度太大会"栈溢出"——汉堡叠得太高，倒掉了！

五、实际应用：文件系统遍历

递归在实际开发中非常实用，比如遍历文件夹：

1/**
2 * 模拟文件系统结构
3 */
4const fileSystem = {
5    name: "根目录",
6    type: "folder",
7    children: [
8        {
9            name: "文档",
10            type: "folder",
11            children: [
12                { name: "简历.pdf", type: "file" },
13                { name: "报告.docx", type: "file" }
14            ]
15        },
16        {
17            name: "图片", 
18            type: "folder",
19            children: [
20                { 
21                    name: "旅行照片", 
22                    type: "folder", 
23                    children: [
24                        { name: "海滩.jpg", type: "file" }
25                    ]
26                },
27                { name: "头像.png", type: "file" }
28            ]
29        },
30        { name: "README.txt", type: "file" }
31    ]
32};
33
34/**
35 * 递归遍历文件系统
36 * @param {object} node - 当前节点
37 * @param {string} indent - 缩进字符串
38 */
39function traverseFileSystem(node, indent = "") {
40    // 基准条件：空节点直接返回
41    if (!node) return;
42    
43    // 打印当前节点
44    const icon = node.type === 'folder' ? '📁' : '📄';
45    console.log(`${indent}${icon} ${node.name}`);
46    
47    // 递归条件：如果是文件夹且有子节点，递归遍历
48    if (node.type === 'folder' && node.children) {
49        node.children.forEach(child => {
50            traverseFileSystem(child, indent + "  ");
51        });
52    }
53}
54
55console.log("=== 文件系统遍历 ===");
56traverseFileSystem(fileSystem);
57

运行结果：

1=== 文件系统遍历 ===
2📁 根目录
3  📁 文档
4    📄 简历.pdf
5    📄 报告.docx
6  📁 图片
7    📁 旅行照片
8      📄 海滩.jpg
9    📄 头像.png
10  📄 README.txt
11

六、递归的适用场景

1. 树形结构操作

• 文件系统遍历
• DOM树操作
• 组织架构图
• 菜单导航

2. 数学问题

• 阶乘计算
• 斐波那契数列
• 汉诺塔问题

3. 分治算法

• 归并排序
• 快速排序

4. 回溯算法

• 迷宫求解
• 数独解题

七、递归的优缺点

优点：

• 代码简洁：复杂问题简单化
• 思路清晰：符合人类思维方式
• 数学表达直接：数学公式容易转换

缺点：

• 性能开销：函数调用有成本
• 栈溢出风险：递归太深会崩溃
• 调试困难：调用链长难跟踪

八、重要改进：避免重复计算

我们来看斐波那契数列的例子，并解决性能问题：

1/**
2 * 斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13...
3 * 规律：每个数是前两个数之和
4 */
5
6// 原始版本：性能很差，有大量重复计算
7function fibonacciSlow(n) {
8    if (n === 0) return 0;
9    if (n === 1) return 1;
10    return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
11}
12
13// 优化版本：使用备忘录避免重复计算
14function fibonacciMemo(n, memo = {}) {
15    if (n in memo) return memo[n];
16    if (n === 0) return 0;
17    if (n === 1) return 1;
18    
19    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
20    return memo[n];
21}
22
23// 迭代版本：性能最好，不会栈溢出
24function fibonacciIterative(n) {
25    if (n === 0) return 0;
26    if (n === 1) return 1;
27    
28    let prev = 0;
29    let curr = 1;
30    
31    for (let i = 2; i <= n; i++) {
32        const next = prev + curr;
33        prev = curr;
34        curr = next;
35    }
36    
37    return curr;
38}
39
40// 性能测试
41console.log("斐波那契数列第10项：");
42console.log("慢速版本:", fibonacciSlow(10));
43console.log("备忘录版本:", fibonacciMemo(10));
44console.log("迭代版本:", fibonacciIterative(10));
45

九、常见错误和解决方案

错误1：忘记基准条件

1// 错误：无限递归！
2function infiniteRecursion(n) {
3    return n * infiniteRecursion(n - 1); // 没有停止条件！
4}
5
6// 正确：必须有基准条件
7function correctRecursion(n) {
8    if (n <= 1) return 1; // 基准条件
9    return n * correctRecursion(n - 1);
10}
11

错误2：问题规模没有减小

1// 错误：问题规模没有变小
2function wrongRecursion(n) {
3    if (n <= 1) return 1;
4    return n * wrongRecursion(n); // 还是n，没有减小！
5}
6
7//  正确：每次递归问题规模都要减小
8function correctRecursion(n) {
9    if (n <= 1) return 1;
10    return n * correctRecursion(n - 1); // n-1，问题规模减小
11}
12

十、调试技巧：

1. 打印日志：跟踪递归过程
2. 使用调试器：观察调用栈变化
3. 先写基准条件：确保不会无限递归
4. 小数据测试：先用小数据验证正确性

十一、什么时候该用递归？

适合用递归的情况：

• 问题可以分解为相似的子问题
• 数据结构本身是递归的（如树、图）
• 解决方案需要回溯

不适合用递归的情况：

• 性能要求极高
• 递归深度可能很大
• 可以用简单循环解决

十二、实际例子：计算数组深度

让我们用递归解决一个实际问题：

1/**
2 * 计算嵌套数组的深度
3 * 例如：[1, [2, [3, [4]]]] 的深度是4
4 */
5function calculateDepth(arr) {
6    // 基准条件：如果不是数组，深度为0
7    if (!Array.isArray(arr)) {
8        return 0;
9    }
10    
11    // 基准条件：空数组深度为1
12    if (arr.length === 0) {
13        return 1;
14    }
15    
16    // 递归条件：深度 = 1 + 子元素的最大深度
17    let maxChildDepth = 0;
18    for (const item of arr) {
19        const childDepth = calculateDepth(item);
20        if (childDepth > maxChildDepth) {
21            maxChildDepth = childDepth;
22        }
23    }
24    
25    return 1 + maxChildDepth;
26}
27
28// 测试
29const testArrays = [
30    [1, 2, 3],                   // 深度1
31    [1, [2, 3]],                 // 深度2  
32    [1, [2, [3, [4]]]],          // 深度4
33    []                           // 深度1
34];
35
36testArrays.forEach((arr, index) => {
37    console.log(`数组${index + 1}:`, JSON.stringify(arr));
38    console.log(`深度:`, calculateDepth(arr));
39    console.log("---");
40});
41

总结

递归的核心思想：把大问题分解成相似的小问题

三个关键点：

1. 基准条件 - 知道什么时候停止
2. 递归条件 - 知道如何分解问题
3. 递归调用 - 自己调用自己

使用建议：

• 先确定基准条件
• 确保每次递归问题规模都减小
• 注意性能，必要时改用迭代
• 复杂递归考虑使用备忘录优化

递归就像剥洋葱，一层一层往里剥，直到找到核心。掌握了这个方法，你就能优雅地解决很多复杂问题了！

本文首发于公众号：程序员刘大华，专注分享前后端开发的实战笔记。关注我，少走弯路，一起进步！

📌往期精彩

《SpringBoot+Vue3 整合 SSE 实现实时消息推送》

《这20条SQL优化方案，让你的数据库查询速度提升10倍》

《SpringBoot 动态菜单权限系统设计的企业级解决方案》

《Vue3 + ElementPlus 动态菜单实现：一套代码完美适配多角色权限系统》

《你真的懂递归吗？没那么复杂，但也没那么简单》 是转载文章，点击查看原文。