寒假带着学生刷蓝桥杯第一个绕不过去的坎就是递归。很多同学一看到函数自己调自己就懵觉得这是什么玄学操作还有一部分人能看懂别人的递归代码但轮到自己写就完全无从下手。我在训练课上反复强调过递归不是C语言语法问题而是思维方式的转变。如果这个坎迈不过去后面动态规划、图的深度优先搜索、树的遍历全都会卡壳因为这些统统是递归的变体和延伸。这篇东西我不敢叫教程就当一个寒假集训的实战笔记。我会把递归的调用栈原理、蓝桥杯里递归常见的几种考法、寒假一个月该怎么练、以及我实际带学生时踩过的典型坑全部讲透。文中所有代码都是C语言实现跟着敲一遍再配真题练几天递归这一块拿满分问题不大。1. 先从函数调用栈讲透递归的本质1.1 递归不是自己调用自己而是同一个函数不停生成新栈帧初学C语言时很多同学对递归的困惑源自一个错误的直觉递归是不是相当于在同一个函数体内循环执行是不是变量会被覆盖其实完全不是。要理解递归必须从函数调用机制入手。每调用一个函数系统都会在栈上申请一段内存区域叫栈帧。函数里的局部变量、参数、返回地址都存在栈帧里。普通函数之所以能嵌套调用是因为A调用B时A的栈帧还留在栈里B的栈帧压在上面B一返回B的帧被弹出A的帧重新成为栈顶。递归调用也是如此只不过被调用的函数名和当前函数一样其他方面没有任何特殊之处。int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }上面这段阶乘递归如果调用fact(4)实际发生的是fact(4)的栈帧先入栈因为它要计算4 * fact(3)于是fact(3)的栈帧压栈然后是fact(2)、fact(1)。fact(1)命中终止条件return 1栈帧弹出返回给fact(2)fact(2)算出2弹出返回给fact(3)以此类推。你看到的自己调用自己在计算机底层其实是4个互不干扰的栈帧各自持有各自的参数n。1.2 每一层的局部变量都是独立的别怕串味学生常问的一个问题fact(4)里的n和fact(3)里的n是不是同一个n答案是绝对不同。每一层调用都有自己独立的一份参数和局部变量名字虽然一样内存地址不一样。尤其要注意的是递归返回时每一层都会把计算结果返回给它的调用者而不是返回给最初的入口。如果还不能理解可以把每一层递归想象成一条流水线上的不同工位第一个工位把一部分工作交给第二个工位第二个交给第三个……最后一个工位完成后把结果往回传每经过一个工位都加工一下再继续往回传。递归的返回值就是这样逐层回溯的。写递归代码最需要练的就是这种分工思维当前这一层只做当前这一层的事剩下的交给下一层。不要试图在一层里把所有事干完。1.3 递归三要素终止条件、递推关系、层层递进我给学生总结的递归三要素任何入门题目先做这三件事再动笔终止条件什么情况下递归不再继续直接返回结果。没有终止条件的递归就是死递归最终栈溢出崩溃。递推关系当前规模的结果如何用更小规模的结果算出来。数学上叫递推式写代码就是return表达式。规模缩小递归调用时传入的参数必须朝终止条件的方向变化保证迟早能停下来。int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b); }辗转相除法的gcd是教科书级的例子终止条件是b0返回a递推关系是gcd(a,b)gcd(b,a%b)参数从(a,b)变小为(b,a%b)每递归一层b都会严格变小所以一定能在有限步内停止。写任何递归我建议按先写终止条件再写递归调用最后写return的顺序来。很多同学一上来就写return表达式结果忘记终止条件代码跑起来直接栈溢出。2. 蓝桥杯里递归的三大考法2.1 考法一公式型递归直接照搬递推式蓝桥杯的填空题和部分简单编程题会直接考斐波那契数列、阶乘、最大公约数这类数学公式即递归代码的题目。这种题表面简单实际分数必须拿稳。举一个蓝桥杯风格的例子求第n个斐波那契数n很小的时候直接用朴素递归就能过。int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }有一个点必须提醒朴素递归的斐波那契如果n超过30肉眼可见地卡顿n超过40基本等不出结果因为时间复杂度是O(2^n)。蓝桥杯如果n很大裸写必挂务必用记忆化或递推这一点后面专门展开。2.2 考法二递归回溯全排列和组合类题目的骨架蓝桥杯省赛最常出现的是基于回溯法的题目比如全排列、组合生成、n皇后、数独、填数游戏。这类题核心就是一个递归函数在每一层尝试所有可能的选择递归进入下一层失败或完成后撤销选择回溯换下一个选择。下面是最基础的全排列模板n最大为9时最稳int n; int path[10]; int used[10]; void dfs(int step) { if (step n) { for (int i 0; i n; i) { printf(%d , path[i]); } printf(\n); return; } for (int i 1; i n; i) { if (!used[i]) { used[i] 1; path[step] i; dfs(step 1); used[i] 0; // 撤销选择核心中的核心 } } }回溯的本质是深度优先搜索一步一步往下走走不通就退回去换条路。这个退回去换条路就是那行used[i] 0。很多同学第一次写的回溯代码递归能进去但永远只输出一种结果就是因为忘记撤销选择把路全堵死了。2.3 考法三递归改递推或记忆化动态规划的引子蓝桥杯中大量题目暴力的递归版本能拿部分的分数但要想全过就得在递归基础上加记忆化或者干脆改成递推。这个套路是动态规划的前身也是递归价值最大的地方。先看一道典型的走台阶问题每次能走1级或2级上n级台阶有多少种走法递归式就是f(n)f(n-1)f(n-2)终止条件f(1)1f(2)2。裸递归的问题很明显f(n-1)和f(n-2)大量重复计算f(20)还算得出f(50)直接灾难。记忆化的做法是拿一个数组保存已经算出的f(k)下次要用时直接查表long long memo[100]; long long climb(int n) { if (n 1) return 1; if (n 2) return 2; if (memo[n] ! 0) return memo[n]; return memo[n] climb(n - 1) climb(n - 2); }递归在这里从暴力穷举进化成了带备忘录的递归本质上已经是在做动态规划了只不过顺序是从上往下。蓝桥杯的填空题尤其爱考这种给你一个递归框架要求补全记忆化代码目标是让程序在给定时间内跑完。3. 寒假训练最该刷透的几类递归题目3.1 汉诺塔递归里最经典的宏观分层题目汉诺塔我每届训练都让学生写一遍。它不是什么高频考题但训练价值极高因为它能逼你理解把问题拆成递归需要的最小单元。汉诺塔的规则是三根柱子把n个盘子从A移到C每次只能动一个盘子大盘子不能压在小盘子上。递归解法极其简洁void hanoi(int n, char a, char b, char c) { if (n 1) { printf(%c - %c\n, a, c); return; } hanoi(n - 1, a, c, b); printf(%c - %c\n, a, c); hanoi(n - 1, b, a, c); }这里的核心思想要把n个盘子从a移到c先借助c把上面n-1个盘子从a移到b再把最底下的大盘子直接移到c最后借助a把n-1个盘子从b移到c。你只需要设计好这一层剩下n-1个盘子如何移动递归自己去处理。很多同学看别人代码觉得简单自己一写就不知道该传哪根柱子。这里有个笨办法参数顺序永远是发起方、中转方、目标方你只需要在脑海里认定这一步我要把盘子从哪搬到哪剩下两列就是中转。多写几遍汉诺塔就是固定套路。蓝桥杯真题中汉诺塔的变体多考移动n个盘子的最少步数答案就是2^n-1。如果是填空题直接填答案如果是编程大题注意n很大时要用数组或字符串处理大整数不然long long都不够用。3.2 全排列与组合回溯法的两块敲门砖全排列代码在上面已经给出。组合和排列的区别在于排列有顺序组合没顺序。求组合时为了不重复递归时保证从左往右选择下一层从当前元素的后一个开始取不用used数组也行int n, k; int path[10]; void dfs_com(int start, int depth) { if (depth k) { for (int i 0; i k; i) printf(%d , path[i]); printf(\n); return; } for (int i start; i n; i) { path[depth] i; dfs_com(i 1, depth 1); } }调用时dfs_com(1, 0)表示从1开始选选够k个就输出。这类题目在蓝桥杯中经常作为一个大题的预处理步骤。比如让你算某个集合有多少种排列满足条件你先用回溯生成所有排列再对每一种排列验证条件。暴力虽然笨但在数据范围小的时候拿分很稳妥。3.3 字符串反转、回文、子序列递归在字符串上的玩法蓝桥杯和C语言考级的填空题里经常出现这类题目用递归实现字符串逆序输出、判断回文、求最长公共子序列之类。字符串逆序递归极其优美void reverse_str(char *s) { if (*s \0) return; reverse_str(s 1); putchar(*s); }原理很简单先递归进去把后面的字符全部输出再输出当前字符最终效果就是把字符串倒着打印出来。这个例子能帮你理解递归调用之后还有代码的执行时机不是所有处理都在递归调用之前递归返回阶段也可以做事情。判断回文也是一个递归思路比较首尾字符如果相等递归判断去掉首尾后的子串。int is_pal(char *s, int left, int right) { if (left right) return 1; if (s[left] ! s[right]) return 0; return is_pal(s, left 1, right - 1); }这类题表面简单但训练它们能帮你建立递归参数设计的感觉——递归函数需要哪些参数参数应该如何随着递归变化。这恰恰是很多同学写不出递归的短板。3.4 矩阵迷宫和连通块递归自然延伸到DFS蓝桥杯的搜索题比如走迷宫、找岛屿数量、判断连通区域本质就是递归。以经典的矩阵连通块为例给定一个n行m列的网格有障碍物#和通路.求最大连通块里有多少个通路格。DFS遍历每个点把走过的格子标记掉递归看上下左右四个方向char map[105][105]; int vis[105][105]; int n, m; int cnt; void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; if (map[x][y] #) return; if (vis[x][y]) return; vis[x][y] 1; cnt; dfs(x 1, y); dfs(x - 1, y); dfs(x, y 1); dfs(x, y - 1); }这是一个非常典型的递归出口格式先检查越界再检查障碍物再检查重复访问然后标记访问接着递归四个方向。三个if判断的顺序不要乱先把边界条件全部挡掉再往下走。对于初次接触DFS的同学建议亲手画一张小地图把dfs每层的调用和回溯过程一步步走一遍。这条路走通之后你再去看图论、树的遍历会发现全是同一个模板。4. 递归代码的调试日志打印与栈溢出定位4.1 栈溢出的根因无限递归寒假训练最常出现的报错就是运行后程序直接崩溃或者蓝桥杯在线评测显示运行错误多半是栈溢出。栈溢出的直接原因是递归层数太多甚至无限递归把程序的调用栈空间占满了。排查方法第一条用printf打印每一层递归的参数和状态。比如汉诺塔在进入函数最前面加一行日志观察哪些参数在反复出现有没有朝终止条件前进。void hanoi(int n, char a, char b, char c) { printf(n%d, %c-%c\n, n, a, c); ... }如果看到n一直在某个值来回跳甚至根本不变化那就是递推关系写错了或参数没传对。另一种常见死因是终止条件写得太大或者太小。比如走台阶问题终止条件是n1和n2如果漏写n2的情况那么n2会调用climb(1)和climb(0)然后climb(0)调用climb(-1)和climb(-2)一直往负数跑Never停下。4.2 漏写return和返回值类型不匹配C语言里return的缺失往往不会立刻报错而是返回一个随机值导致递归结果莫名其妙。比如int bad_rec(int n) { if (n 0) return 1; bad_rec(n - 1); }这段代码在n0时不返回任何有意义的值编译器可能给你个警告但程序还能运行结果就是随机垃圾数据。我训练时要求学生只要函数声明了返回值所有分支都必须有return宁可多写也绝不漏写。尤其要注意终止条件分支的return很多错误都出在忘了给base case写返回值。递归回溯时返回值会逐层往外传导任何一层断了结果就全乱了。4.3 估算递归层数和时间复杂度蓝桥杯的编程题通常限制运行时间在1000ms左右。递归代码能不能过必须预先估算。看一下递归树斐波那契递归f(n)会调用f(n-1)和f(n-2)画成树每个节点分裂成两个树高为n总节点数约为2^n。这意味着n30时约10亿次调用肯定超时。回溯法生成全排列时递归树节点数大约是n!级别的n10是362万次勉强能跑n12是4.79亿次基本上就要超时了。所以写题前一定要先估算递归树的规模。C语言默认栈空间大概是1到8MB不同环境有差异。递归一层大概占用几十到几百字节。如果递归深度达到10万层很可能会栈溢出。遇到大深度场景不要硬递归改成显式栈模拟或者递推。5. 递归的优化与改写记忆化、剪枝、迭代化5.1 记忆化搜索给递归加一张备忘录前面提过走台阶问题的记忆化核心是用一个数组缓存子问题的解避免重复计算。记忆化搜索其实就是在递归代码里加三行判断当前参数f(n)是否已算过算完后存入数组下次再遇到同样参数直接返回结果。long long fib_memo(int n) { if (n 1) return n; if (f[n] ! -1) return f[n]; // 查备忘录 return f[n] fib_memo(n - 1) fib_memo(n - 2); // 存备忘录 }初始化时把f数组全部置-1因为FIB的值不可能为-1可以安全地用来标记未计算。记忆化能把指数级复杂度降为多项式级。斐波那契从O(2^n)降为O(n)走台阶、爬楼梯、数字三角形这类题目用记忆化搜索是蓝桥杯最稳妥的拿分手段之一。它的优点是不用费劲去想递推顺序只需写出递归公式然后加缓存代码逻辑非常贴近自然思维。5.2 剪枝提前砍掉不可能的分支回溯法在数据规模略大时很容易超时好在很多分支其实是荒谬的完全没必要继续走。剪枝就是提前判断当前状态是否还有可能得到合法解如果不可能直接return。经典例子是n皇后问题在n×n棋盘上放置n个皇后要求任意两个皇后不能在同一行、同一列、同一对角线上。回溯逐行放置皇后时每放一个就可以判断当前放置是否与之前的皇后冲突如果冲突就直接撤销不需要往下递归。这种剪枝能把巨大的递归树砍掉绝大部分分支。int col[15], diag1[30], diag2[30]; void dfs_queen(int row, int n) { if (row n) { cnt; return; } for (int c 1; c n; c) { if (col[c] || diag1[row c] || diag2[row - c n]) continue; col[c] diag1[row c] diag2[row - c n] 1; dfs_queen(row 1, n); col[c] diag1[row c] diag2[row - c n] 0; } }对角线数组的索引设计是这类题的一个小技巧同一条主对角线上的row-c是常数为避免负数加n同一条副对角线上的rowc是常数。这个细节搞明白n皇后就是固定套路。剪枝的原则是宁可多剪一些也要保证不误剪合法解。没有把握的分支不要剪剪错了答案就缺了。5.3 尾递归了解原理但别太指望C语言编译器尾递归指递归调用是函数体中最后一条执行语句且return的值直接是递归调用的返回值不再做任何加工。尾递归的好处是理论上可以复用栈帧把O(n)的栈空间压成O(1)避免栈溢出。int fact_tail(int n, int acc) { if (n 1) return acc; return fact_tail(n - 1, acc * n); }这个版本是尾递归因为return后面只有递归调用本身。但遗憾的是C语言标准并不强制编译器做尾调用优化实际测试中gcc在某些优化级别下会做但在默认级别可能不做。这意味着你不能把大型递归全部押在尾递归优化上。我的建议是知道尾递归这个概念能看懂代码就行。真正要稳定解决问题还是尽量把递归改写为循环加栈结构。递归是思维工具迭代是性能手段两者不矛盾。5.4 递归深度失控时改用显式栈寒假训练到后期学生可能会遇到一些深度很大的题目比如遍历一个1e5节点的树。C语言的函数调用栈根本扛不住1e5层递归这种时候就要用自己维护的栈来模拟递归入栈出栈的过程或者用循环解决。递归转迭代的基本思路你的调用栈里藏了什么信息显式栈里就存什么信息。比如DFS遍历一个图typedef struct { int x, y; } Point; Point stack[100005]; int top -1; void push(Point p) { stack[top] p; } Point pop() { return stack[top--]; }用数组模拟栈每遇到一个待访问节点就push访问完就pop效果等同于递归DFS但不会栈溢出。这种方法在蓝桥杯高阶题里会用到但寒假训练阶段能把递归本身写好才是第一步转换可以先了解。6. 寒假递归训练计划与日常避坑清单6.1 四个阶段的训练规划我按一个月左右的长假期排了四个阶段适合从零开始也适合基础薄弱的中学生。第一阶段约3天打牢递归三要素。每天写熟五个基础题n的阶乘、斐波那契数列、最大公约数、累加求和、汉诺塔。这些题必须做到不查资料手写全对。重点是掌握先终止条件再递推关系的写法同时验证递归调用的参数确实在逼近终止条件。第二阶段约5天专攻回溯法。全排列、组合、n皇后、迷宫求解、集合划分。这个阶段不必追求数量每道题都要做到能闭眼画递归树能解释为什么加visited数组、为什么撤销选择。回溯是蓝桥杯递归题的主战场多花时间不亏。第三阶段约5天DFS和记忆化搜索。连通块计数、岛屿数量、单源最短路迷宫类、数字三角形、走台阶记忆化。这个阶段开始接触递归加缓存的写法并且尝试把部分递归改为递推对比两者差别。第四阶段一直延续到比赛前真题训练。蓝桥杯历年省赛真题凡是递归相关全部集中刷。搜索题优先尝试用递归DFS和记忆化体会什么时候该剪枝什么时候会超时。6.2 每日训练建议每天训练时间建议控制在2到3小时。前半小时复习前一天代码不看书重新敲一遍中间一个半小时做新题最后半小时整理错题记录错误类型和改法。错题本我建议按错误类型分类不要按题目分类。统计后发现最常见的三类错误漏写终止条件、忘了撤销选择、递归参数传错。这三类错误有很强的规律性针对性地练就能大幅减少。6.3 蓝桥杯实战中的递归策略实战考试时拿到递归题我建议遵循以下策略数据范围小n≤20时间充裕直接用暴力递归或回溯正确优先。数据范围中等n≤50尝试记忆化搜索把指数级复杂度压下来。数据范围大递归明显会爆栈或超时改用递推或显式栈不要恋战。蓝桥杯的填空题补全代码先读清递归终止条件和递归调用处的上下文看看缺的是边界判断还是递归后的状态恢复。还有一点容易被忽略蓝桥杯的编程大题允许提交暴力解法拿部分分。即便一时没想出最优解用递归把暴力版本写上通常能拿到30%到60%的测试点分数这比空着强太多。我反复跟学生说考场上的第一要务是先有分再拿满分。6.4 学生最容易反复踩的几个坑最后把我在训练里看到的高频错误集中列一遍全是真实案例漏写return。写递归函数忘了给终止条件分支加return导致返回随机数值整个递归结果全错。解决写完后逐行检查所有分支是否都有return。无限递归。终止条件写在递推关系之后或者终止条件永远不会被满足。例如斐波那契终止条件写n2返回1却把n0的情况漏了导致fib(0)递归到负数。解决把终止条件写在函数最前面。修改全局变量后忘恢复。回溯法里修改了某个标记数组递归返回后没恢复原状导致后续的分支全部不可用。解决回溯模板里每次递归调用后面紧跟着撤销操作。递归顺序写反。需要先递归再处理的情形写成先处理再递归导致逻辑颠倒。比如字符串逆序输出必须先递归再putchar顺序反了就变成正序输出。解决判断当前代码是在递进阶段执行还是在回归阶段执行。参数传错。汉诺塔里柱子顺序传反全排列里step和循环变量搞混这类问题非常细节只能通过画递归树来逐步排查。解决调试时打印每层参数确认参数变化符合预期。记忆化数组没初始化或初始化错误。把memo数组初始化为0但合法结果也可能是0导致缓存失效。解决根据题目选择-1或者其他不可能的值作为未计算标记。这些坑我每学期都要帮学生排查无数遍希望看完这篇的人能少踩几个。递归不靠天赋靠的是大量手写、画递归树、读别人简洁的解法然后自己重新组织逻辑写出来。寒假一个月只要每天坚持写两三个递归题到开学时你再看蓝桥杯的搜索和动态规划题会觉得思路清楚很多。递归这道坎迈过去后面的路就顺了。