🪆 递归算法
俄罗斯套娃打开一层，里面还有一个一模一样的小套娃，再打开还有更小的……递归就是「一个函数干活干到一半，发现自己需要先解决一个一模一样的、但更小的任务，于是它调用自己」。这一页拆开套娃，学会写出口、算它有多快多占地方，再学怎么让它跑得更省。
考纲知识点：递归算法的相关概念
递归算法的时间复杂度和空间复杂度
递归的优化策略
递归算法的时间复杂度和空间复杂度
递归的优化策略
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级
- (7)掌握递归算法的基本原理，能够应用递归解决问题，能够分析递归算法的时间复杂度和空间复杂度，了解递归的优化策略。
📚
先学一学
花 5 分钟读完下面 5 课，再去闯关就不慌啦
1
🪆 递归 = 函数自己调用自己，但必须有「出口」
递归是一个函数在干活时调用自己去解决一个「更小一点」的同样问题，就像套娃里还有更小的套娃。但它绝不能无限套下去——必须有一个最小的、不用再调自己的情况，叫出口（边界条件），最小的套娃到了，就一层层往回「报答案」。
📞 生活类比：排队问数
小朋友排队，最后一名想知道自己是第几个，他问前面的人「你是第几个？」前面的人也不知道，又问再前面……一直问到队首（出口）：队首说「我是第 1 个」。然后答案一个传一个传回来，最后一名就知道自己是第几个了。问出去是「递」，传回来是「归」。
💡 口诀：递归两件宝：自己调自己 + 出口停得掉；没有出口 = 无限套娃，程序会崩。
2
🍦 递归经典：算阶乘 n!
阶乘 n! = 1×2×3×…×n。它有个漂亮的递归关系：n! = n × (n-1)!，而最小的出口是 1! = 1。想算 5!，先算 4!；算 4! 先算 3!……一路问到 1! 这个出口，再一路乘回来。
💻 读代码：递归算阶乘
看得懂就好，不用背：
int fact(int n){
if (n == 1) return 1; // 出口
return n * fact(n - 1); // 自己调用自己，问题变小一点
}
if (n == 1) return 1; // 出口
return n * fact(n - 1); // 自己调用自己，问题变小一点
}
调 fact(3)：3×fact(2) → 2×fact(1) → 出口 1 → 2×1=2 → 3×2=6。
💡 口诀：出口在最小处，返回一路乘回来；递是问下去，归是答上来。
3
⏱️ 递归的复杂度：时间数调用次数，空间数深度
🔢 时间：总共调用了多少次
算 fact(n) 会一路调 fact(n-1)、fact(n-2)……到 fact(1)，一共约 n 次调用，所以时间是 O(n)。
但有的递归每次调用自己两次（比如斐波那契：fib(n) = fib(n-1) + fib(n-2)），调用次数像树枝一样分叉：1、2、4、8……一路翻倍，时间暴涨到约 O(2ⁿ)——四级见过的指数复杂度，n 一大就跑不动。
但有的递归每次调用自己两次（比如斐波那契：fib(n) = fib(n-1) + fib(n-2)），调用次数像树枝一样分叉：1、2、4、8……一路翻倍，时间暴涨到约 O(2ⁿ)——四级见过的指数复杂度，n 一大就跑不动。
💡 口诀：时间数「总共调了几次」；调自己一次约 O(n)，每次调两个自己可能到 O(2ⁿ)。
🗄️ 空间：递归会「叠罗汉」占内存
每调一次自己，电脑都要在调用栈上放一层「还没算完的活」。算 fact(n) 时，栈里同时叠着 fact(n)、fact(n-1)……共 n 层，所以空间是 O(n)（递归深度 n）。叠太深（比如 100 万层）会把栈撑爆，叫栈溢出。
💡 口诀：递归多深，栈就叠多高；深度 = 空间复杂度，太深会爆栈。
4
⚡ 递归的优化策略：别做重复功
朴素斐波那契慢，是因为同一个 fib 被反反复复算了很多遍（fib(3) 会被算两次、fib(2) 更多次）。优化就是想办法让每个子问题只算一次：
📒 记忆化（备忘录）
准备一个「答案本」数组，算过的 fib(k) 记下来；下次再要，先翻本子，有就直接用，没有再算。这样每个 k 只算一次，O(2ⁿ) 立刻降到 O(n)。
💡 口诀：算过就记本子上，下次直接抄答案；备忘录把指数打成线性。
🔄 改递推 / 改循环
很多递归（尤其尾递归：出口前不再用返回值做更多计算）可以改写成从最小的出口往上推的递推，或用循环。这样没有层层调用，栈只占 O(1)，又快又不爆栈。四级学过的递推和递归正好是好搭档。
💡 口诀：递归从大到小问，递推从小往大推；能转循环就转循环，又省时间又省栈。
🆚 递归 vs 递推 vs 循环
· 递归：函数自己调自己，思路直观，但可能慢、占栈。
· 递推：从已知起点一步步往后推，不用调用栈。
· 循环：最朴素的重复，很多递归都能改成循环。
三者的选择：问题天生分叉（像目录套目录）用递归好懂；能从小推到大就用递推或循环更省。
· 递推：从已知起点一步步往后推，不用调用栈。
· 循环：最朴素的重复，很多递归都能改成循环。
三者的选择：问题天生分叉（像目录套目录）用递归好懂；能从小推到大就用递推或循环更省。
💡 口诀：递归好想但费栈；递推省事更亲民；循环最省，能改就改。
5
🌳 递归用在哪儿
🌲 天生「套娃」的问题最适合递归
· 文件夹里套文件夹，要列出所有文件（每层都一样结构）
· 汉诺塔：把 n 个盘子搬走，先搬 n-1 个……
· 分治算法（归并排序、快速排序）就是递归的经典搭档
· 表达式计算：括号里还有括号
· 汉诺塔：把 n 个盘子搬走，先搬 n-1 个……
· 分治算法（归并排序、快速排序）就是递归的经典搭档
· 表达式计算：括号里还有括号
💡 口诀：遇到「一层套一层」，先想想能不能用递归；出口写清楚，套娃就不怕。
🌟 行业实际
很多软件的「撤销」、编译器检查括号配对、AI 的下棋搜索树，背后都有递归或递归式的分治思路。但真实系统里工程师常把递归改写成显式栈或循环，防止数据一大就爆栈——「会写递归」和「会优化递归」都是本事。
🎯
闯关小锦囊 · 考点提醒
- 递归 = 函数调用自己解决更小的同样问题；必须有出口，否则无限套娃、程序崩掉。
- 出口写在最前面（如 if (n == 1) return 1;）。
- 时间复杂度：数总共调用几次（fact 约 O(n)，朴素斐波那契约 O(2ⁿ)）。
- 空间复杂度：看递归深度——栈叠多高就占多少（fact 深度 n，空间 O(n)）。
- 优化：记忆化（备忘录）避免重复算；能转递推/循环就转，省时间又防爆栈。
- 调用库函数（如 sin(sin(x))）只是嵌套调用，不是递归；递归一定是「自己调用自己」。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。