递归入门不再怕：从调用栈到回溯的算法竞赛通关指南

递归这玩意儿说邪门也真邪门。我带过不少准备打算法竞赛的新人前几周做循环、数组、排序还都挺顺利一到递归就集体卡壳。有人照着模板能写出阶乘换汉诺塔就懵了有人勉强理解了斐波那契一遇到“输出所有方案”的题又不知道从哪下手。但递归又是躲不开的坎后面只要跟搜索、树、图、动态规划沾边它几乎无处不在。这篇文章就按竞赛选手的训练思路把递归初阶讲透——先弄明白递归在计算机里到底是怎么跑的再用几道入门经典题逐个过一遍最后把新手最容易踩的坑全部摊开给你看。如果你是刚接触算法竞赛的小白或者已经刷过一些题但递归始终隔着一层窗户纸这篇文章应该能帮你省不少力气。我的建议是别只盯着代码抄跟着每一段思路走把“函数自己调自己”这件事从底层理解到位。竞赛这条路递归这一关早晚要过过了它后面很多算法你都会有豁然开朗的感觉。1. 算法竞赛里的递归到底在考什么1.1 递归不是“玄学”是调用栈的视觉化很多新手觉得递归难是因为习惯把代码当作“顺序执行的命令列表”于是看到函数里又调用自己脑子里就会陷入死循环“它调用自己然后再次调用自己然后又调用自己……那什么时候结束”这种恐惧是正常的因为你的思考方式还是循环式的没有切换到“栈”的视角。计算机执行函数的底层机制是调用栈call stack。每次调用一个函数系统会在栈上压入一个“栈帧”里面保存了这个函数的局部变量、参数、以及执行完之后要返回的地址。函数结束栈帧弹出程序回到上一个调用点继续执行。递归其实就是函数重复调用自己导致栈上出现一串相似的栈帧。比如递归第5层时栈上可能有5个同名函数的不同栈帧它们的参数、局部变量各不相同。这里得插一句我带选手时经常发现只要把“栈”这个概念讲清楚绝大多数递归问题就迎刃而解了。你可以把递归想象成嵌套包装盒要打开最外层盒子发现里面还有盒子打开第二层还有第三层……直到某层只有一个很小的盒子直接打开就行。然后你开始倒着往外收拾。递归的“递”就是不断拆外层盒子压栈“归”就是打开最小盒子后逐层返回出栈。从竞赛角度讲你需要做到三件事第一看清递归每次调用时参数如何变化第二明确终止条件在什么情况下被触发第三理解返回值如何一层层传回去。做到这三点递归代码在你眼中就不再是一团乱线了。1.2 竞赛考递归考的是“阶梯能力”初级竞赛题里递归会直接出现比如算阶乘、算斐波那契、输出汉诺塔步骤。但这些只是“开胃菜”。再往后递归会和回溯结合变成深度优先搜索会和分治结合变成归并排序、快速排序会和记忆化数组结合变成动态规划的雏形。你甚至可以说递归是算法竞赛底层思维里最基础的一块积木。所以入门阶段我不是很建议直接背“递归模板”。模板只能帮你混过最简单的一题一旦题目套了个壳你就不知道怎么用了。你需要理解的是递归的“通用结构”终止条件、当前层处理、递归调用、返回值/状态传递。这四个部分拆清楚了任何递归题都能往里面填。另外竞赛里经常考复杂度分析。比如斐波那契数列的朴素递归为什么那么慢这就要会看递归调用树。竞赛题和业务代码不一样运行时间卡得很死一个指数级复杂度的递归能直接让你超时。所以入门递归时就要养成“顺手算复杂度”的习惯。2. 递归三要素写之前先想清楚这三件事2.1 三要素分别是边界条件、递归表达式、规模递减我刚开始带新人时喜欢让他们在写任何递归函数前先回答三个问题什么时候结束——边界条件。当前问题怎么变成更小的同类问题——递归表达式。每次调用后问题规模是否在缩小——规模递减。这三个问题对应着递归代码的主干。以阶乘为例n!的定义是n! n × (n-1)!而且0! 1。这里的边界条件是 n0 或 n1 时返回1递归表达式是 factorial(n) n * factorial(n-1)规模递减是因为n每次减少1最终必然到达边界。为什么一定要强调第三个问题因为很多新手写的递归边界和表达式都对但每次调用传入的参数根本没变化比如int f(int n) { if (n 0) return 1; return n * f(n); // 传入的还是n规模没变 }这就是死递归。每次调用参数不缩小永远到不了边界最后栈空间耗尽程序崩溃。竞赛评测系统里这通常表现为“运行错误段错误”或“内存溢出”。这个问题看着低级在实际训练中出现频率高得惊人。写完后养成一个习惯盯着递归调用语句确认每传下去的参数确实是在朝边界靠近。还有一个容易忽略的点边界条件不一定只有一个。有些题目里递归可能有多个出口。比如二叉树的递归遍历当节点为空时返回一个值当节点是叶子时返回另一个值。写的时候要分清楚不同边界返回的东西是不是符合题意。2.2 参数设计和返回值设计决定代码的“顺手程度”递归函数的签名新手往往随便写反正能跑就行。但等题目的规模一上来参数设计不合理代码就会变成一锅粥。我的经验是递归参数通常分几类一是当前处理的位置或状态比如当前层数、当前下标二是已经累积的结果或路径比如已经选出的数字三是辅助标志比如某个元素是否被使用过。返回值则要回答一个问题这个函数执行完后需要向上层提供什么信息一个值一个布尔判断还是一组方案举个例子。如果让你统计一个数组的所有子集个数你当然可以直接用公式 2^n。但如果你想用递归去实现“枚举所有子集”的过程就需要把“当前处理到第几个元素”和“当前已选集合”作为参数传下去。此时返回值往往不是关键关键在于路径的传递和状态的回溯。等你做到全排列、八皇后这类题就会明白“参数怎么设计”直接决定了递归函数的可写性和可读性。返回值还有一个常见坑类型选错。递归函数计算的中间结果可能非常大比如斐波那契第50项远超过int能表示的2^31-1。竞赛中一旦做数学相关的递归题先看数据范围返回值开 long long 通常是起步操作。不然看似正确的代码提交一大半测试点全是负数这种教训我见得太多了。3. 四道经典入门递归题手把手过一遍3.1 阶乘最小、最干净的递归演示阶乘作为递归入门第一题优点是代码短、逻辑直观。代码可以写成这样long long factorial(int n) { if (n 0 || n 1) return 1; // 边界 return n * factorial(n - 1); // 递归 }调用 factorial(4) 时发生了什么我建议新手一定要亲手在纸上画一遍factorial(4) 发现 n ! 0/1于是计算 4 * factorial(3)先挂起factorial(3) 计算 3 * factorial(2)挂起factorial(2) 计算 2 * factorial(1)挂起factorial(1) 直接返回 1然后逐层返回factorial(2) 返回 212factorial(3) 返回 326factorial(4) 返回 4*624。整个调用过程在栈上形成了4层帧归的过程就是一层层出栈。这一步手推非常重要画完一遍你就真的理解了“函数自己调用自己”是怎么落地的。时间复杂度 O(n)空间复杂度 O(n)这里的空间复杂度计数的是递归过程中栈的最大深度。3.2 斐波那契数列第一个“性能杀手”斐波那契数列的定义是 f(n) f(n-1) f(n-2)边界 f(1)1、f(2)1。新手通常接触到的第一个递归坑就在这里。long long fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); }这段代码逻辑完全正确但它慢得令人绝望。为什么因为 fib(6) 会调用 fib(5) 和 fib(4)而 fib(5) 又会调用 fib(4) 和 fib(3)。我没让你用代码去证明了自己手动画一下调用树就会发现同一层里 fib(4)、fib(3)、fib(2) 被重复调用了许多次。f(3) 在 f(6) 的递归树里就被调用了整整 3 次数据规模一大重复量呈指数爆炸。严格算一下朴素递归的复杂度大约是 O(2^n)。这意味着 n40 时某些评测环境已经明显卡顿n50 时基本跑不出结果。很多新手第一反应是“我的电脑太慢”其实不是电脑问题是指数复杂度本身的威力。竞赛中有个思路叫“暴力骗分”数据范围小的时候朴素递归也能通过部分测试点先拿分再说。但这只是权宜之计。后面我们在第5节会讲记忆化搜索那是解决这类重叠子问题的最经典手段。斐波那契数列是个绝佳的范本务必吃透。3.3 汉诺塔把复杂流程交给递归去办汉诺塔的题目描述大家应该都听过三根柱子A、B、CA柱上按大小顺序套着n个盘子要把所有盘子移到C柱每次只能移动一个盘子大盘子永远不能压在小盘子上。很多新手一上来就试图“手动模拟移动过程”然后发现超过3个盘子就晕了。汉诺塔的正确打开方式是只关心“把问题降一级”。要把n个盘子从A移到C整体分为三大步把上面n-1个盘子从A经过C移到B把最下面最大的盘子从A直接移到C把B上的n-1个盘子经过A移到C。中间那个大盘子的移动是单步操作两边是两个规模为n-1的同型子问题。于是代码很简洁void hanoi(int n, char a, char b, char c) { if (n 1) { cout a - c endl; return; } hanoi(n - 1, a, c, b); cout a - c endl; hanoi(n - 1, b, a, c); }这个递归的精髓在于你不要去追究“n-1个盘子具体怎么移动”而是相信递归会把子问题解决。每次调用时三根柱子的角色切换了——原本的辅助柱变成了目标柱原本的目标柱变成了辅助柱。这种“角色语义切换”就是递归抽象能力的核心体现。汉诺塔还有一个迷人的地方就是步数是 2^n - 1。n64时步数是18446744073709551615这和我们常说的“世界末日”传说有关。竞赛里有时会要求输出步数或者判断某一步移动哪个盘子本质上都是在考察你有没有真正理解递归的分治结构。3.4 全排列递归回溯搜索的雏形全排列生成是入门阶段最重要的一题没有之一。因为它把递归、枚举、状态记录、回溯撤销全部串起来了也是后面深度优先搜索的雏形。题目输入 n输出 1 到 n 的所有排列。比如 n3输出 123、132、213、231、312、321。思路是第一个位置可以放1到n任意一个数放完后第二个位置再放“还没被用过”的某个数依次往下。直到所有位置都填满就得到一种排列。这天然就是一个递归结构。int n; vectorint path; bool used[10]; void dfs(int depth) { if (depth n) { for (int x : path) cout x ; cout endl; return; } for (int i 1; i n; i) { if (used[i]) continue; used[i] true; path.push_back(i); dfs(depth 1); path.pop_back(); used[i] false; } }很多新手第一次看到这份代码会纳闷为什么递归之后还要 path.pop_back() 和 used[i] false这一步就是“回溯撤销”。你想在第一层选了 i1 之后程序会递归把剩下位置的排列全部枚举完。枚举完回来第一层还要尝试 i2。如果当初 i1 时没有把 used[1] 改回 false也不把 path 里的1弹掉那么第二层就会认为1已经被用过整个算法就废了。所以回溯的通俗理解是进到下一层之前把状态修改掉从下一层回来之后把状态恢复原样。这样每一层的尝试都在“同一张干净的状态表”上进行。全排列这题一定要手推 画递归树。你把 n3 的整个过程画一遍理解“深度优先”四个字是什么意思递归和回溯的配合也就彻底想明白了。4. 递归实战的四大翻车现场与排查手册4.1 忘记终止条件死递归到底死在哪最常见的运行时错误是“段错误”十有八九是栈溢出其中又有一大半是因为终止条件漏了或者写错。现象是程序运行后卡顿一下然后崩溃退出。原因就是递归无限深入栈空间被耗尽。排查方法很简单。第一检查边界条件是否书写正确第二检查递归调用传入的参数是否在逐渐逼近边界第三实在找不到可以加一个“递归深度计数器”int depth 0; void dfs(int x) { depth; if (depth 10000) { cout 递归过深疑似死递归 endl; return; } // 原逻辑 }这个技巧在调试时很管用。我建议你写完递归后心里默算一遍最坏情况下递归会调用到多少层如果这个数字远大于预期说明边界或规模递减出了问题。4.2 递归深度爆炸即使不是死递归也可能爆栈代码没有死递归但依然爆栈这种情况也很常见。递归深度 最大栈帧数每个栈帧虽然不大但架不住深。比如你写一个递归函数每层只分配一个int变量递归10万层在默认栈空间下大概率直接崩溃。竞赛环境下栈空间通常有限一般在几十到几百MB但系统栈到底多大不同评测平台不一样。更稳妥的做法是在写递归之前先估算最大递归深度。如果深度超过十万级别就要考虑是否应该改用迭代或者手动维护栈。不是所有递归都能轻易改迭代但很多可以。比如用一个 stack 结构模拟递归过程这在处理深度优先搜索时是常用手段。入门阶段你先意识到“递归有深度上限”这件事就行真到需要优化时再学手写栈。4.3 全局变量污染回溯时忘了“还回去”全排列代码里如果你把 used[i] false 这行注释掉程序会输出什么通常只会输出一两个不完整的排列因为第一层选了1之后used[1]永远为true后面的排列全被堵死了。这就是“全局变量污染”的典型症状。类似问题还出现在网格搜索、八皇后等题中。搜索过程里你修改了某个全局标记比如当前格子已经走过、当前皇后已经放在某列递归返回时必须恢复原状。否则后续的分支会看到“被别人改脏”的状态产生错误答案。排查这类问题的方法检查所有在递归调用前被修改的变量确认递归返回后是否都被还原。一个简单的经验是在递归代码里任何“修改”都要有对应的“恢复”成对出现。你可以把这种操作称为“借了就要还”。4.4 返回值与递归关系不匹配还有一种错误很隐蔽就是递归函数的返回值和实际想表达的意义对不上。比如你想判断棋盘上从起点能否走到终点写了一个返回 bool 的递归函数但里面递归调用时直接写了 dfs(...) 而没有 return结果上层拿到的是一个不确定的值。编译器有时只是警告一下运行起来逻辑已经错了。解决方案是在写递归前先明确“这个函数返回什么”。如果返回 bool那递归里几乎都要写成 return dfs(...)如果返回 int递归里就应该是若干个子问题返回值的运算如果返回 void那信息通常靠参数或全局变量传递。竞赛中还有一种常见错误取模问题。题目要求结果对某个大质数取模递归表达式里每一步乘法/加法都要取模但新手经常只在最后一步取模导致中间结果溢出。递归和递推一样中间过程的每个计算点都要检查数据范围。下面我把上面这些问题整理成一个速查表方便你以后排查症状可能原因检查方向段错误/崩溃栈溢出或死递归边界条件、参数递减、递归深度输出少/输出重复回溯未还原状态used/visit数组是否成对修改答案错误但能运行返回值类型不匹配是否漏写return、返回类型是否合理结果溢出为负中间计算超范围换成long long、及时取模超时重复计算过多考虑记忆化搜索5. 从入门递归到竞赛常用技巧记忆化与剪枝初探5.1 记忆化搜索给递归加个“缓存”斐波那契朴素递归慢是因为同一个子问题被反复算。解决思路很朴素把已经算过的结果存起来下次用到直接取不再算第二遍。这就是记忆化搜索。在斐波那契的基础上加一个 memo 数组long long memo[100]; long long fib(int n) { if (n 1 || n 2) return 1; if (memo[n] ! 0) return memo[n]; return memo[n] fib(n - 1) fib(n - 2); }只需要加两行复杂度就从 O(2^n) 降到了 O(n)。速度提升是跨越式的。我见过很多新手第一次看到这个对比时非常震撼这就是“算法优化”最直观的一课。记忆化搜索的适用条件很明确递归过程中存在重叠子问题也就是同一个参数会被反复计算。判断方法也简单画递归树看有没有重复的节点。一旦有就可以上 memo。在竞赛题里记忆化搜索是很多动态规划题的另一个写法虽然不总是最优解但理解起来比状态转移方程直观得多。5.2 剪枝提前中止不可能的分支剪枝的思想更简单既然某些递归分支注定得不到正确答案那就不用继续往深处走了。比如八皇后问题中如果你已经在前两行放了两个互相攻击的皇后那后面的分支全部无效直接 return不再枚举。这能够让搜索空间大幅缩小。剪枝和递归的结合在入门阶段最常见的题目是“有重复元素的排列”以及“给定目标和找子集”这类题。你可以在递归入口加一个判断如果当前累积值已经超过目标值就提前返回。这就是最基础的“可行性剪枝”。剪枝的判断条件不能写错否则会把正确分支也剪掉。入门阶段我的建议是先写出不带剪枝的正确递归通过小数据验证再考虑加剪枝。否则排查时你会分不清是搜索逻辑错了还是剪枝条件错了。5.3 递归转迭代的时机递归代码可读性好但有两个硬伤调用栈有深度限制而且函数调用本身有额外开销。所以竞赛里当你发现递归爆栈或超时又无法通过记忆化解决时就得考虑转成迭代。最简单的例子是斐波那契。用递归 记忆化已经不错了但如果你只需要当前一项用循环递推更稳long long fib_iter(int n) { if (n 1 || n 2) return 1; long long a 1, b 1; for (int i 3; i n; i) { long long c a b; a b; b c; } return b; }递归转迭代最粗暴的方式是用 stack 手动模拟函数调用栈。这个技巧在解析表达式、遍历树、做非递归深搜时都会用到。新手不用急着掌握但要明白“递归不是唯一实现方式”遇到瓶颈时有这条路可走。6. 入门阶段训练路线与心得体会6.1 刷题顺序建议从复现到应用再到变形如果你刚开始学递归我建议按下面的顺序刷题第一阶段手写阶乘、斐波那契、汉诺塔。这三个不要只写代码还要手工画出调用过程把每一个返回值都标出来。第二阶段递归分治。自己实现一遍归并排序、二分查找的递归版体会“把区间分成两半分别处理再合并”的套路。第三阶段递归回溯。做全排列、组合生成、八皇后这类搜索题重点理解“状态标记”与“撤销”的成对关系。第四阶段递归记忆化。做一些带重叠子问题的题目先写朴素递归验证正确性再加上 memo 看性能变化。每个阶段之间建议留出时间把上一阶段的习题重新默写一遍。竞赛学习最大的误区是“看懂了就以为自己会了”实际一关编辑器就大脑空白。递归尤其如此因为它考验的是思维过程不是背代码能力。6.2 调试递归的独家技巧打印递归树我调试递归题有一个老办法在函数入口和出口各加一条打印语句用缩进表示当前递归深度。这是理解递归流程最直接的手段。可以设计一个简单的缩进显示void dfs(int depth, int x) { for (int i 0; i depth; i) cout ; cout 进入第 depth 层参数 x endl; // 递归逻辑 for (int i 0; i depth; i) cout ; cout 离开第 depth 层返回 endl; }跑一遍之后你会看到完整的分层结构什么时候进入子调用什么时候回到上一层参数是怎么变化的。这和画递归树的效果一样却不需要你手动去画。遇到逻辑错乱的递归用这个办法定位特别快。另一个技巧是全局变量记录“当前路径”。全排列这类题调试时把 path 数组打出来就能看出来回溯时是否正确地删除了元素。如果你发现某一路径长得不合常理那基本就是撤销漏写了。6.3 给新手的几句大实话递归是这个系列入门篇里的一道分水岭。我观察到一种普遍情况有些选手递归学得很快是因为他愿意花一个晚上反复手推同一个汉诺塔有些选手学得慢不是笨是急着刷题从来没停下来画过调用树。所以这一节我想说点掏心窝的话。不要试图背递归模板竞赛的题千变万化模板只能帮你应付“看起来一模一样”的题。真正要掌握的是“把大问题拆成小问题”的意识。这种意识一旦建立后面学树、学图、学动态规划你会感觉自己一直在用同一套思维方式只是换了不同的数据结构而已。我也建议你在训练初期把递归、回溯、记忆化这三样尽量练熟。它们其实是递进的关系先学会递归的框架再通过回溯探索所有可能最后用记忆化砍掉重复计算。这套组合拳在竞赛里非常能打。哪怕后面你接触了更高级的算法递归功底扎实的人在看别人的题解时也会快得多。在时间分配上入门阶段递归题不要贪多。我的经验是一天吃透一道题好过一天囫囵吞枣刷十道。递归需要“想明白”不是“见过”。你花两个小时画一棵递归树看起来效率低但这棵树的形状会留在你脑子里以后遇到类似结构直接就能套。我把这个系列的递归初阶部分就讲到这里。如果你正在递归的门口犹豫别急拿起笔从阶乘开始画调用栈画完阶乘画斐波那契再画汉诺塔。只要自己亲手走完这几条递归路径那种“顿悟”的感觉很快就会出现。递归这条路慢一点反而是最快的走法。