先声明一下这篇不是竞赛大佬的炫技帖就是一个普通刷题人把洛谷递归题单啃完之后的笔记。我自己学递归的时候卡了很久尤其是“明明能看懂题解一自己写就懵”这种状态。后来发现递归这东西光看没有用必须靠几道典型题目把“分治思维”和“函数调用栈”这两个底层观念焊死在脑子里。洛谷上汉诺塔、占卜DIY、FBI树这三道题恰好分别对应了递归的三种常见形态纯分治递归、模拟型递归、区间递归。把这三题彻底吃透递归初阶基本就稳了。这篇文章我会把每一题的思路拆开、代码讲透、坑点列全适合正在刷洛谷递归题单、或者刚学完递归但做题总卡壳的朋友。1. 先想清楚一件事递归到底在“递归”什么1.1 递归不是“函数调用自己”这么简单很多人对递归的理解停留在“函数里面调用自己”但一写就出事因为根本不知道函数调用自己之后会发生什么。我建议把递归理解成两个东西的组合递和归。“递”是沿着问题规模不断缩小往下走“归”是到达最小规模后开始一层层返回结果。整个过程依赖的是系统栈——每一次函数调用都会把当前参数、局部变量、返回地址压入栈中等内层调用返回后再弹栈继续执行。用生活化的例子说递归就像你在一排排队的人里问“你前面是谁”。你问第一个人他不知道最终答案但他可以问第二个人第二个人问第三个人……直到最后一个人说“我前面没人了”这个答案再一层层传回来。中间每个人做的事其实一模一样区别只是“问的位置”不同。递归函数也是这样同一份代码每次用不同的参数去执行最终通过最小规模的情况递归出口结束链条。所以写递归之前你至少得回答三个问题这个函数要完成什么任务参数怎么设计才能表达“规模”规模小到什么程度可以直接给出答案这三件事想不清楚代码写出来一定是错的。先说结论洛谷递归题单里的三道题恰好就是这三种设计思路的典型示范——汉诺塔靠“移动方式”定义递归占卜DIY靠“状态流转”定义递归FBI树靠“区间划分”定义递归。1.2 分治思维把“大问题”翻译成“更小的同类型问题”递归和分治是天生一对。分治的意思是一个大问题可以拆成几个互不重叠、结构相同的子问题子问题解决了大问题就解决了。递归代码只不过是分治思想的一种落地方式。所以你做题的时候不要急着写代码先在纸上把“拆法”写出来大问题怎么拆最小的不可拆分问题是什么拆出来的子问题和原问题是不是同一类汉诺塔就是一个教科书级例子。要把 n 个盘子从 A 柱移到 C 柱你不需要真的去想“第 3 个盘子怎么动、第 5 个盘子怎么动”只需要抓住最高层的拆法先把上面 n-1 个盘子从 A 移到 B这是一个规模为 n-1 的汉诺塔问题再把第 n 个盘子从 A 移到 C最后把 B 上的 n-1 个盘子从 B 移到 C这又是一个规模为 n-1 的汉诺塔问题。每一次递归调用都是同一个函数在处理规模更小的问题当规模变成 1 时直接移动即可。这就是分治思维的核心。FBI 树的分治逻辑更直观一个长度为 2^n 的 01 串先看整个串是什么类型再把串对半分成两个子串分别递归处理。子串的规模不断折半直到长度为 1。整个过程就是一棵天然的二叉树而递归天然适合处理这种“左右分叉”的结构。占卜DIY 稍微特殊一点它看起来是循环模拟但翻牌规则本身就是“从某一堆翻出一张牌放到另一堆再继续从后半堆翻牌”这个“继续”的动作可以直接表达成递归调用相当于用递归来描述一个持续流转的状态。2. 汉诺塔最经典的“三步拆解法”吃透它递归就入门了2.1 问题描述与递归模型汉诺塔问题在洛谷上属于递归入门必刷题。题面很简单有三根柱子 A、B、CA 柱上有 n 个圆盘从上到下半径依次增大初始时小盘在上、大盘在下。要求把所有盘子移到 C 柱移动过程中始终保持大盘不压小盘一次只能移动一个盘子输出移动步骤。这个问题的递归模型如果不建立好代码很容易写成“凭感觉递归”。正确的模型就是三个步骤第一步借助 C 柱把 A 柱上面的 n-1 个盘子移到 B 柱第二步把 A 柱上剩下的那个最大的盘子直接移到 C 柱第三步借助 A 柱把 B 柱上的 n-1 个盘子移到 C 柱。每一步都是独立完整的汉诺塔子问题区别只是“起始柱、目标柱、辅助柱”的角色在交换。很多第一次写的人会卡在柱子角色上。你只要记住move(n, from, to, aux) 表示“把 n 个盘子从 from 柱借助 aux 柱移到 to 柱”那么第一步就是 move(n-1, from, aux, to)第二步输出 from - to第三步是 move(n-1, aux, to, from)。函数签名里柱子的顺序非常容易写错我当年就在这上面翻过车把辅助柱和目标柱写反输出结果乱七八糟。写的时候可以给自己定个规则四个参数永远是“数量、起点、终点、辅助点”然后严格按照三步来填。2.2 代码实现递归出口别漏输出格式要看清下面给出经典 C 递归实现。这里的重点是 n1 作为递归出口——只有一个盘子的时候根本不需要借助辅助柱直接移过去就行。这个出口是整个递归链的终点没有它函数就会无限调用直到栈溢出。#include iostream using namespace std; // 把 n 个盘子从 from 借助 aux 移到 to void hanoi(int n, char from, char to, char aux) { if (n 1) { cout from - to endl; return; } // 第一步把上面 n-1 个盘子从 from 借助 to 移到 aux hanoi(n - 1, from, aux, to); // 第二步把最下面的盘子从 from 移到 to cout from - to endl; // 第三步把 aux 上的 n-1 个盘子借助 from 移到 to hanoi(n - 1, aux, to, from); } int main() { int n; cin n; hanoi(n, A, C, B); return 0; }代码只有十几行但信息量很大。拿 n3 手动推一遍你会发现调用顺序是hanoi(3, A, C, B)hanoi(2, A, B, C)hanoi(1, A, C, B)输出 A - C输出 A - Bhanoi(1, C, B, A)输出 C - B输出 A - Chanoi(2, B, C, A)hanoi(1, B, A, C)输出 B - A输出 B - Chanoi(1, A, C, B)输出 A - C最终输出 7 行正好是 2^3 - 1。这个“2^n - 1”是汉诺塔的最小移动次数也是判断你的递归拆法是否正确的一条硬指标。如果你输出的步数不是 2^n - 1基本可以断定递归结构有问题。函数调用栈的层次也会告诉你每调用一次 hanoi栈上会多一层函数帧n3 时最深会走到第 4 层左右肉眼勉强能跟住n5 以上就建议直接在纸上画递归树了。2.3 注意三个坑参数顺序、步数溢出、递归深度第一个坑是参数顺序。如果你把 hanoi(n, from, aux, to) 写成 hanoi(n, from, to, aux)第一步就错了——辅助柱和目标柱搞反整个步骤全乱。建议把函数签名固定成“(数量, 起点, 辅助, 终点)”或者“(数量, 起点, 终点, 辅助)”都行关键是全篇统一不要一会这顺序一会那顺序。第二个坑是步数溢出。n20 时 2^20-1 是 1048575打印没问题n31 时 2^31-1 已经逼近 int 上限n 更大时用 int 存步数会直接溢出成负数。如果题目要求输出步数务必先看看数据范围必要的时候用 long long。我在洛谷上见过有人 n 只给到 20结果他推了一个斐波那契数列式的错误递推公式白白浪费一晚上最后发现是最基础的公式没记牢。第三个坑是递归深度。虽然汉诺塔递归深度大约是 nn 不超过 20 时完全没事但如果你在递归里又写了别的递归调用深度会成倍增加。养成一个习惯遇到递归题先估算最大递归深度心里有数才不会爆栈。洛谷的评测环境一般不会太苛刻但自己的电脑上跑 n30 的汉诺塔可能已经要等一会儿这不是死循环是步数真的多。3. 占卜DIY用递归改写循环理解“状态流转”3.1 这道题到底在考什么占卜DIY 是洛谷递归题单里很有意思的一道题。它表面上看是一道大型模拟题桌面上有若干堆扑克牌按规则从某一堆开始翻牌每翻出一张牌就把它放到指定数字的那一堆底部然后从那一堆的顶部再翻一张一直翻到翻出 K 为止。题面细节以洛谷原题为准我这边想重点说的是为什么它会被归到“递归”题单里因为翻牌这个动作本身就是一个可以自我调用的过程。你从第 x 堆翻出一张牌假设牌面是 y那么下一步就是“从第 y 堆翻一张牌”。这个“下一步”和“当前步”执行的是完全相同的规则只是操作的堆编号变了。这就是一个标准的递归结构递归函数接收一个参数表示“当前要翻哪一堆”函数体里根据翻出来的牌决定下一次调用谁。意识到这一点你就能把一段看起来很啰嗦的 while 循环改写成一个干净利落的递归函数。这题的第二个考点是数据结构的选择。13 堆牌每堆内部要“从顶部取牌”和“往底部放牌”天然适合用队列queue来维护。但洛谷上有不少人用双端队列 deque或者干脆用数组加头尾指针也都行。我的建议是初学阶段直接用 STL 的 queue 就好先把递归逻辑理清楚再考虑优化。递归函数里的状态参数就是“当前翻牌的堆编号”而每翻一张牌就更新统计数组直到翻出 K 结束。3.2 怎么把“翻牌过程”写成递归伪代码思路大概是这样的int cnt[14]; // cnt[i] 记录数字 i 的牌被翻开的次数 queueint piles[14]; // piles[i] 存储第 i 堆牌队首是顶部 void dfs(int from) { if (piles[from].empty()) return; // 安全出口防止越界 int card piles[from].front(); piles[from].pop(); cnt[card]; if (card 13) return; // 翻到 KK 对应 13结束这条翻牌链 piles[card].push(card); // 放到对应数字的堆底部 dfs(card); // 从那一堆继续翻 }我第一次看这个递归函数的时候最大的疑惑是它递归的“规模”是什么答案是规模不是数字而是“从哪一堆开始翻”这个状态。每次递归调用都会把状态更新成新的堆编号而翻牌的总次数是有限的所以递归一定会终止。这种“用状态变化表示问题推进”的递归和汉诺塔那种“用盘子数量表示问题规模”的递归完全不同但它同样可以用递归来写。关键点在于递归出口必须放在递归调用之前而且要仔细考虑。这里的出口有两个第一个是“当前堆为空”的防御性出口主要防止数据错误导致越界第二个是“翻到 K”的正常出口对应题目要求的结束条件。初学者很容易漏掉第二个出口结果递归链条永远停不下来。3.3 一个超级容易踩的坑先放牌还是先递归我见过很多人在写这道题的时候把“放到对应堆底部”和“继续从该堆翻牌”的顺序搞反。正确的逻辑是先翻出一张牌如果它不是 K就把它放到对应堆的底部然后从对应堆继续翻。如果你先把牌放到底部然后又从同一堆顶部取牌顺序就错了——因为放到底部的牌并不会有影响但下一步要翻的是“对应堆”的顶部而不是当前堆的顶部。这个“对应”关系是题目规则的核心一定要在代码里体现清楚。还有一个容易忽略的细节如果用 queue 维护每堆牌那么“放到对应堆底部”就是piles[card].push(card)“从顶部翻牌”就是piles[from].front()和piles[from].pop()。这两个操作要分开写别合并成一次操作。我自己调试时就把这两行写反过结果翻出来的牌一直不对排查了半天才发现是顺序问题。这道题给我的启发是递归不一定都是“把大问题拆小”有时候它只是“把重复过程用函数调用的方式表达出来”。这两种递归在代码形式上没有本质区别但思考方式不一样。前者叫分治递归后者更像迭代递归或者说尾递归。后面你遇到很多模拟题都可以尝试用递归来写虽然不一定更快但逻辑会清爽很多。4. FBI树二叉树与后序遍历理解“区间递归”4.1 题目回顾与递归结构分析洛谷 P1087 的 FBI 树是一道把递归、二叉树、后序遍历三者结合在一起的经典题。题面大概是这样给你一个长度为 2^n 的 01 串构建一棵 FBI 树。规则是如果一段字符串全为 0该节点类型为 B全为 1类型为 I有 0 也有 1类型为 F。然后不断把字符串对半分分别构建左子树和右子树直到区间长度为 1。最后要求输出这棵树的后序遍历结果。这题的递归结构非常清晰递归函数的参数就是当前要处理的区间 [l, r]根据这个区间内的字符情况决定当前节点是什么类型然后递归处理左半区间 [l, mid] 和右半区间 [mid1, r]。递归出口就是 l r区间里只有一个字符直接判断是 B 还是 I。如果你对二叉树还不熟可以先把这个递归想成“在字符串上画一棵树”的过程整串是根左半串是左子树右半串是右子树不断二分。很多同学会觉得这题难在“怎么输出后序”。其实后序遍历的定义是先遍历左子树再遍历右子树最后访问根节点。放到递归代码里就是先递归左区间再递归右区间最后输出当前节点的类型。这个顺序和你“判断当前节点类型”的代码位置无关只和“cout 放在哪里”有关。如果你想输出前序就把 cout 放在两次递归之前想输出中序就把 cout 放在两次递归之间想输出后序就把 cout 放在两次递归之后。就这么简单。4.2 代码实现在递归中边建树边输出本题可以不用真的把二叉树结构建出来直接在递归函数里输出节点类型因为递归调用的天然顺序就是一棵树的遍历顺序。如果你非要建树再后序遍历反而绕远了。下面是直接后序输出的 C 实现#include iostream #include string using namespace std; string s; void build(int l, int r) { if (l r) { // 区间长度为 1直接判断叶子节点 if (s[l] 0) cout B; else cout I; return; } int mid (l r) / 2; // 先递归左子树 build(l, mid); // 再递归右子树 build(mid 1, r); // 最后输出当前节点类型需要统计整个 [l, r] 区间 bool has0 false, has1 false; for (int i l; i r; i) { if (s[i] 0) has0 true; else has1 true; } if (has0 has1) cout F; else if (has0) cout B; else cout I; } int main() { int n; cin n; cin s; build(0, (1 n) - 1); return 0; }注意(1 n) - 1这里因为字符串总长度是 2^n下标从 0 开始所以最后一个下标是 2^n - 1。如果你直接写s.length() - 1也可以但用移位运算更能体现这道题“二分”的背景。代码里判断当前节点类型时我用了一个 for 循环扫描整个区间。这个写法在 n 很大的时候会有一点效率浪费但洛谷本题的 n 一般在 10 以内完全没问题而且逻辑直白初学者更容易看懂。4.3 一个重要的优化不用每次扫描整个区间上面代码有个小问题每个节点都要扫描它对应的整个区间来判断类型总体复杂度是 O(n * 2^n)。n 小时无所谓但如果你以后遇到更大数据这个写法可能就不够看了。可以换一种思路每次递归不是“扫描一遍区间”而是“根据左右子树的返回信息合并出当前节点类型”。比如定义递归函数返回这个区间是否有 0、是否有 1或者干脆返回区间类型父节点根据左右子树类型直接判断不需要再遍历字符串。思路是这样的// 返回 0 表示全 0返回 1 表示全 1返回 2 表示混合 int dfs(int l, int r) { if (l r) { if (s[l] 0) { cout B; return 0; } else { cout I; return 1; } } int mid (l r) / 2; int leftType dfs(l, mid); int rightType dfs(mid 1, r); int curType; if (leftType 0 rightType 0) { cout B; curType 0; } else if (leftType 1 rightType 1) { cout I; curType 1; } else { cout F; curType 2; } return curType; }这个版本里每个节点只做常数次判断总复杂度 O(2^n)和节点数成正比。它也更接近“递归分治”的本质左右子树先解决问题把答案汇总给父节点。如果你以后学线段树、树状数组这类数据结构会发现同样的思路到处都在用。所以这道 FBI 树的价值不仅仅是练递归更是帮你理解“信息如何在递归过程中向上传递”。4.4 后序输出顺序不能搞反再强调一遍后序遍历输出顺序是“左、右、根”所以代码里一定是先 build(l, mid)再 build(mid1, r)最后才 cout。我见过有的同学把 cout 放在两次递归之前结果输出了前序遍历还纳闷为什么答案不对。这种情况要排查的就是你的输出语句到底放在哪里是不是按照题目要求的遍历顺序放的。另外一个小技巧如果担心自己当前写的递归顺序不对可以先改成中序或前序输出和题目样例对比一下。如果前序输出能和样例对得上说明你的递归结构没问题只是输出位置放错了。如果前序输出也对不上那大概率是区间划分出了问题比如 mid 算错了或者左右区间的边界重复/遗漏。区间递归题最容易错的三个地方就是边界条件、mid 的计算、递归调用的区间范围。每写一个递归区间题我都建议你用“长度很小”的例子比如 n2字符串长度为 4手动走一遍确保区间二分没有缝隙也没有重叠。5. 三道题横向对比递归能力的“三块拼图”5.1 用一张表看懂三种递归形态做完三道题之后我建议你把它们放在一起对比因为这三道题正好代表了递归的三种主流形态题目递归的“规模”体现在哪递归出口主要考点时间复杂度汉诺塔盘子数量 nn 1分治拆解、柱子角色转换O(2^n)占卜DIY当前操作的堆编号翻到 K状态流转、递归模拟循环约 O(总牌数)FBI树字符串区间 [l, r]l r区间二分、后序遍历基础版 O(n * 2^n)汉诺塔考的是“问题规模能不能一层层变小”你不需要关心每个盘子的具体命运只需要把 n-1 的问题抛给递归。占卜DIY 考的是“规则能不能直接翻译成递归调用”它没有明显的问题规模但状态的转移本身构成了递归链。FBI 树考的是“数据结构的结构能不能用递归定义”树本身就是递归定义的每个节点的左右子树都是更小的树。如果你能把这三种形态都吃透后面遇到更多递归题就不会觉得“每道题都是新题”。你会发现绝大多数递归题都可以归入这三类要么是规模递减的纯分治要么是状态流转的模拟递归要么是区间/树状结构的递归。思路对了代码写起来就顺了。5.2 递归深度、时间复杂度与数据范围的关系做题还要留意数据范围不同递归题对递归深度和时间复杂度的容忍度完全不同。汉诺塔虽然递归深度只有 n但总步数是 2^n - 1所以 n 一大肯定超时题目一般不会让你真的输出所有步骤。占卜DIY 的递归深度最多是牌的总数比如 52 张牌那递归最多调用 52 层完全不怕爆栈。FBI 树如果字符串长度是 2^n递归深度是 n节点数大约是 2^(n1)-1所以 n 通常不会太大否则输出就超长了。我的建议是每次拿到递归题先在草稿纸上算出三样东西——最大递归深度、函数调用总次数、每层递归的工作量。这三样数据决定了你的代码能不能过。很多人写递归题超时不是思路错了而是每层递归里做了一大堆重复计算。比如 FBI 树的基础版每次扫描区间本质上就是在浪费时间改成返回类型后立刻高效很多。5.3 递归初阶之后怎么进阶如果你这三道题都刷明白了我建议按这个顺序往下走先刷几道更纯粹的递归练习题比如“数的计算”“火星人”这类巩固“状态参数递归出口”的基本功然后开始接触记忆化搜索你会发现很多递归状态被重复计算用数组把结果存起来就是动态规划的雏形再往后就是回溯法递归的作用变成“在搜索树上尝试所有可能路径”这是排列组合、八皇后这类题的核心。不过这些都是后话递归初阶阶段最重要的不是刷量大而是把每一道题的递归树画出来理解系统栈的压入和弹出。我的亲身体验是如果在学习递归初期能坚持手动画五到十张递归调用图后面所有递归题都会轻松很多。画图的过程不是在浪费时间而是在给你的大脑建立直觉。6. 实战中常见的报错与排查技巧6.1 无限递归导致栈溢出Runtime Error / Segmentation Fault递归题最常见的报错就是无限递归。排查方法很直接检查递归出口是否真的能被执行到。比如汉诺塔的出口是n 1如果你把代码写成if (n 0)那么 n 会一直减到负数永远不会等于 0直接爆栈。占卜DIY 的出口是“翻到 K”如果你判断错了牌面数字比如把 K 对应的 13 写成了 12也会导致递归停不下来。一个非常实用的排查技巧在递归函数最前面加一个“进入函数”的打印语句在 return 之前加一个“退出函数”的打印语句然后跑一个小规模数据看调用顺序。比如汉诺塔你直接打印当前 n 和 from/to/aux递归结构是否正确一目了然。FBI 树你可以打印当前 l、r检查区间划分是否按预期折半。void hanoi(int n, char from, char to, char aux) { cout enter: n n from - to aux aux endl; if (n 1) { cout base case endl; cout from - to endl; return; } hanoi(n - 1, from, aux, to); cout move bottom: from - to endl; hanoi(n - 1, aux, to, from); }跑一跑 n2 或 n3你会清楚地看到递归的“递”和“归”是怎么发生的。这种方法比盯死代码好用太多了所有递归题都可以这样排查。调完再把打印注释掉即可不影响提交。6.2 答案错误WA但逻辑看起来没问题从哪查如果递归没有爆栈输出也有结果但答案不对优先查三件事第一参数传递顺序。汉诺塔的 from/to/aux 三个柱子顺序错位占卜DIY 的“从哪一堆翻牌”写错FBI 树的左右区间边界算错都是经典的 WA 来源。我建议把递归函数的参数名起得长一点、清楚一点不要用 n、a、b、c 这种含义不明的缩写。宁可打字多一点也别让 bug 藏在短变量名里。第二输出顺序。FBI 树考察后序遍历如果你把 cout 的位置放错输出顺序就会从前序变成中序或者后序。洛谷题目要求什么遍历顺序你就把输出语句放在相应的位置。建议先输出样例数据看和题目给的结果是否一致不一致就调整 cout 的位置而不是重新写递归结构。第三边界数据。用 n0、n1、长度为 1 的字符串、翻牌第一张就是 K 等极端数据去测。初学者很容易忽略边界比如 FBI 树如果输入长度是 1递归函数必须能直接处理汉诺塔如果 n1不能多输出一行“用辅助柱移动”这种多余操作占卜DIY 如果一开始就翻到 K递归应该立刻结束而不是继续翻下去。边界测试是排查递归题最有效的手段没有之一。6.3 递归题调试的通用建议先画图再写码后验证我自己的做题习惯是三步走先在纸上画出递归树或者状态转移图然后用小规模数据写代码并手动走一遍最后再用题目样例或者自己构造的边界数据验证。很多人一上来直接写代码写完了再对着样例猜 bug效率非常低。递归题的 bug 不是“猜”出来的是“推”出来的。你只有清楚每一层递归做了什么才能判断哪一层出了问题。另外调试递归还有一个小技巧用一个全局计数器统计递归函数被调用的次数。比如汉诺塔你可以在进入函数时cnt最终输出的 cnt 应该等于 2^n - 1。如果对不上说明递归分支有问题。占卜DIY 里也可以统计翻牌次数翻牌总数应该符合题目的约束。这个技巧在应对“看起来没有死循环但结果明显不对”的情况时特别管用。7. 写在最后递归学习的一点个人体会这三道题刷完之后我对递归最大的感悟是递归不是一个“高深”的技巧而是一种“偷懒”的思维——我只负责把当前这一步想清楚剩下的交给下一层递归。写代码的时候不要试图在脑子里模拟整个递归全过程那样只会把自己绕晕。你要做的是相信“子问题的递归调用会正确返回结果”就像你调用一个库函数一样自然。刚开始这种“信任感”很难建立但一旦建立起来递归题就变成了一种套路找到出口找到拆法把子问题的返回值拼成父问题的答案。汉诺塔教会我拆解问题占卜DIY教会我用状态驱动递归FBI树教会我让信息从下层向上层汇总。这三件事不仅是递归的核心也是很多算法的基础。如果你现在还在递归门口徘徊别着急静下心来把这三道题各写三遍每一次都试着不看题解独立完成。写完之后你再看其他递归题会发现它们突然都变得亲切了不少。