递归这块硬骨头我劝你别再背代码了山东理工大学SDUT的《程序设计基础Ⅱ》到了递归这一章几乎每个初学C语言的人都会卡一下。但说实话卡住的原因真的不是智商问题而是我们的大脑习惯了“从头到尾按顺序执行”的思维方式突然要你“在函数内部调用自己”一下子转不过弯来。这篇文章我打算把递归这块内容彻底讲透。不光是讲理论还会用OJ上常见的题目例子把递归的写法套路、运行机制、调试方法和选型逻辑都过一遍。不管你是刚学到函数、第一次接触递归的新手还是已经刷题刷到怀疑人生的同学这篇文章应该都能帮你把“知其然”变成“知其所以然”。顺便说一句期末考试递归必考而且往往是拉开分数的那道题所以值得你花一个小时认真看完。1. 从“函数调用函数”看递归的本质一场永不结束的套娃递归这个概念教科书上喜欢下定义“函数直接或间接调用自身”。但这句话太抽象我换一种说法递归本质上就是函数调函数只不过调用的是它自己。而“函数调函数”这件事你从学第一门课的时候就会了。1.1 你早就会函数调用了只是没反应过来想想看你在主函数里写过这样的代码printf(Hello, SDUT!);printf就是一个函数主函数调用它它执行完就返回。然后你又写过自定义函数int add(int a, int b) { return a b; } int main() { int sum add(3, 4); printf(%d, sum); return 0; }主函数调用addadd里的代码执行完把结果返回给主函数。整个过程就是调用方暂停被调方执行执行完返回调用方继续。递归就是把“被调方”换成了“自己”。比如void hello() { printf(Hello!\n); hello(); // 自己调用自己 }你运行这个程序它会把Hello!无限打印下去——因为hello执行到hello()这行时又去执行hello了永远没有返回的时候。很多人到这一步就开始懵“它怎么不往下走了”因为它根本就没走完过。caller在等callee返回而callee又在等下一个callee返回形成一个无限嵌套的等待链。1.2 用“剥洋葱”建立递归直觉我给学生讲递归时最喜欢用的类比是剥洋葱。你要把一整颗洋葱剥到最里面那层步骤是先剥掉最外面一层剥完发现还是一颗洋葱那就再剥一层重复这个过程直到剥到最里面什么都没有了。你发现没有剥洋葱的过程本身就是重复的——“剥掉一层”这个动作反复执行但剥的对象洋葱越来越小。这就是递归的核心直觉通过反复处理一个规模更小的同类问题最终到达一个不能再拆分的终点。人类理解递归的方式其实是“懒人算法”我不用关心整颗洋葱要剥多少层我只需要知道“剥一层之后剩下的还是一颗更小的洋葱重复同样的方法就行”。至于到底剥了几层那是计算机的事。1.3 运行栈递归背后的“记账本”递归能跑起来靠的是函数调用栈Call Stack。每次调用一个函数系统会在栈上分配一块区域称为栈帧Stack Frame用来存放这次调用的参数、局部变量和返回地址。函数返回时栈帧被弹出控制权交还给调用方。我画一个阶乘函数factorial(3)的调用过程你就明白了。假设代码是int factorial(int n) { if (n 1) return 1; // 边界条件 return n * factorial(n - 1); // 递归调用 }调用factorial(3)时栈上依次压入factorial(3)的栈帧: n 3等待factorial(2)的结果 factorial(2)的栈帧: n 2等待factorial(1)的结果 factorial(1)的栈帧: n 1直接返回1注意factorial(1)因为满足n 1所以不用再往下调直接返回1。然后这个结果“一层层往回送”factorial(1)返回1 → factorial(2)算出2*12 → factorial(3)算出3*26整个过程就像洋葱剥到底之后再把每一层重新粘回去。理解这个栈帧机制特别重要。因为后面你会碰到栈溢出Stack Overflow就是递归太深栈空间被用完了。到时候你就知道不是程序逻辑错而是你的递归层数超出了栈的容量。2. 手写递归的固定套路从数学归纳到代码实现“递归我能看懂但让我自己写就写不出来。”这句话我听了不下百遍。说实话写递归确实有套路而且套路非常固定。你只要按部就班地做三步大部分递归题都能写出来。2.1 三步法边界条件、递归关系、递归调用我写递归从来都是按这个顺序思考第一步找边界条件Base Case。就是“问题小到什么程度答案就显而易见了”。比如阶乘1的阶乘就是1数组求和空数组的和是0。边界条件必须有限且可到达。第二步找递归关系Recurrence Relation。就是把“n的答案”和“n-1或更小的答案”联系起来。阶乘的递归关系就是n! n * (n-1)!。第三步把递归关系写成代码。在函数体内调用自身注意调用的规模必须朝边界条件方向递减。拿阶乘来说int factorial(int n) { // 第一步边界条件 if (n 1) return 1; // 第三步递归调用规模n-1 n朝边界靠近 return n * factorial(n - 1); }三步走完代码就出来了。但这里有个很多教材没点破的细节为什么边界条件是n 1而不是n 1因为如果某人传入factorial(0)n 1就会无限递归。写成n 10的阶乘也能正确返回1。这就是我在实际写代码时的一个习惯边界条件宁可多覆盖一点也别留缝隙。2.2 从数学归纳法理解递归的正确性写递归的人本质上是在用数学归纳法思考。数学归纳法有两步证明n1时命题成立对应边界条件假设nk成立证明nk1成立对应递归关系。递归代码的正确性也是靠这两点保证的。你不需要在脑子里把factorial(500)的完整调用链条跑一遍——你只需要相信两件事边界条件是对的如果factorial(n-1)返回了正确答案那么n * factorial(n-1)也是正确答案。这就是所谓的递归信任Recursive Leap of Faith。我当年学递归的时候老师说过一句话让我记到现在“写递归的时候别想着递归的过程只想着递归的结果。”意思是你在写factorial(n)函数体时直接假设factorial(n-1)是对的函数把它当现成的工具用就行。2.3 经典入门题实战数组求和与字符串反转光说理论没用我们上手写两个OJ最常见的入门递归题。数组求和给定数组a[]和长度n返回所有元素之和。int sum(int a[], int n) { if (n 0) return 0; // 边界空数组和为0 return sum(a, n - 1) a[n - 1]; // 递归前n-1个元素的和 第n个元素 }这个写法非常典型把“求n个元素的和”转化为“求n-1个元素的和加上最后一个元素”。规模从n减到n-1一直到0。字符串反转给定字符串s反转后输出。void reverse(char s[], int start, int end) { if (start end) return; // 边界只剩0个或1个字符无需反转 char tmp s[start]; s[start] s[end]; s[end] tmp; reverse(s, start 1, end - 1); // 递归处理中间的字符串 }这里的递归思路是先把首尾字符交换然后“里面的字符串交给递归去做”。你看一旦想通了递归代码其实很简洁比循环写起来还要直观。2.4 为什么“兔子数列”是递归教学的头号陷阱说到递归必然绕不开斐波那契数列int fib(int n) { if (n 0 || n 1) return n; return fib(n - 1) fib(n - 2); }代码只有三行看起来非常完美。但你要是真去算fib(50)你会等到怀疑人生。原因很简单这个递归存在大量重复计算。fib(5)要算fib(4)和fib(3)而fib(4)又要算fib(3)和fib(2)——同一个fib(3)被算了两次。展开之后你会发现这棵递归树几乎膨胀成一棵满二叉树时间复杂度是O(2^n)。我给学生讲这个例子是想说明一个重要的道理写得出不等于写得好。你学会了递归的套路还得学会判断“这个递归值不值得写”。斐波那契用循环写只要O(n)int fib(int n) { if (n 1) return n; int a 0, b 1, c; for (int i 2; i n; i) { c a b; a b; b c; } return b; }所以在实际做题时我通常先问自己一句“这个问题用递归写会不会有严重的重复计算”如果有要么加个数组做记忆化要么直接改迭代。3. 递归和迭代的正面交锋机制差异与选型依据你肯定听说过“递归和迭代可以互相转换”这句话。没错理论上任何递归都能用循环加栈模拟出来任何循环也都能改写成递归。但理论归理论真到做题和写项目的时候选哪个是要拿实际约束说话的。3.1 从求1加到n看两种思维方式的差异先看最简单的题目求1 2 ... n。迭代写法int sum_iter(int n) { int s 0; for (int i 1; i n; i) s i; return s; }递归写法int sum_rec(int n) { if (n 0) return 0; return sum_rec(n - 1) n; }迭代的思路是“从1开始累加加到一个目标值”它维护一个不断变化的累加变量本质上是一个一个地把工作做完。递归的思路是“我先把前面n-1项的和算出来再加上最后一项”本质上是把一个大问题分解成同构的小问题。这两种思路没有高下之分但它们对应的场景不一样。迭代适合“过程明确、每个步骤都看得见”的任务递归适合“问题能自然按规模拆分”的任务。3.2 同一个功能两种实现的性能对比说个SDUT OJ上很经典的问题求最大公约数用辗转相除法。这是递归和迭代都能轻松写的题目。递归实现int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b); }迭代实现int gcd_iter(int a, int b) { while (b ! 0) { int tmp a % b; a b; b tmp; } return a; }从性能角度说递归版每次调用都要分配栈帧、保存现场开销比循环大。但请注意这里的“大”是相对于普通循环而言的。gcd的递归深度非常浅对数级别所以两者运行时间几乎无差别。真正有差别的是斐波那契那种“递归爆炸”的题目那种情况下递归版会慢到不可用。我给一个经验判断标准你直接照抄即可场景推荐方案递归深度很小1000代码简洁递归嵌套结构本身有层数概念树、图、括号匹配递归数据规模大对性能敏感可能深递归迭代 显式栈存在大量重复子问题迭代或递归 记忆化3.3 什么时候必须用递归什么时候千万别用先说“千万别用”的场景递归深度不可控的时候。比如说你要处理一个可能上万层的嵌套结构用递归写得很爽但程序一运行就爆栈。这时候你就需要把递归改成迭代自己维护一个栈。再说“最好用递归”的场景问题本身的定义就是递归的。典型的例子是二叉树的遍历。树的定义本身就是“一个节点下面挂两棵子树”用递归写出来的遍历代码干净利落void inOrder(struct TreeNode* root) { if (root NULL) return; inOrder(root-left); printf(%d , root-val); inOrder(root-right); }如果用迭代写中序遍历你得手动模拟栈代码起码翻倍还得小心入栈出栈的顺序。所以这棵树长得那么“递归”你就别非拿循环跟它硬碰。4. 递归调试与翻车现场爆栈、无限递归和边界错乱写递归最大的痛苦不是写不出来而是写出来了却不知道错在哪。循环写错了你可以单步调试递归写错了你单步调试都可能陷进去出不来。这一节我讲讲自己在LibreOJ和SDUT OJ上踩过的那些递归坑。4.1 栈溢出不是逻辑错而是层数太深先说最经典的一个错误。写这个求幂的递归int power(int x, int n) { if (n 0) return 1; return x * power(x, n - 1); }算power(2, 100000)程序崩溃。报错通常是Segmentation fault或者Stack overflow。很多人第一反应是“我代码哪里写错了”但其实逻辑完全没毛病错在递归深度超过了栈的容量。每一层递归大约消耗几十字节到上百字节的栈空间。默认栈空间在Linux下通常是8MB在Windows MSVC下通常是1MB。假设一层消耗100字节1MB栈大概能支持一万层递归。你算power(2, 100000)就是10万层不炸才怪。遇到这种情况要么把递归改成循环要么用快速幂——快速幂的递归深度是O(log n)10万次方深度只有17层左右int fastPower(int x, int n) { if (n 0) return 1; if (n % 2 1) return x * fastPower(x, n - 1); return fastPower(x * x, n / 2); }所以你看递归并非不能深层关键是深度要以对数级别增长而不是线性级别。4.2 无限递归少了那行“return”的惨痛教训写递归时最深恶痛绝的BUG忘记写边界条件或者边界条件永远达不到。比如void countDown(int n) { printf(%d , n); countDown(n - 1); }看起来没啥问题n确实一直在减。但问题是n减成负数之后呢这个递归没有任何停下来的条件它会一直减到int溢出然后变成正数继续减……无限循环。正确写法void countDown(int n) { if (n 0) return; // 边界条件 printf(%d , n); countDown(n - 1); }还有另一种隐蔽的情况递归调用时参数没变。比如int f(int n) { if (n 0) return 1; return f(n); // 参数还是n根本没变小 }这代码跑起来就是活脱脱的“死循环”而且比while(1)难排查得多——因为它披着“递归”的外衣让你总觉得哪里有点不对但说不出来。所以写递归时养成一个习惯每次写递归调用先看一眼参数是不是比原来的小。4.3 调试递归的两把斧头打印调用树和“尾递归”陷阱我在OJ上调试递归不喜欢单步跟因为跟几步就晕了。我更喜欢打印调用痕迹。例如调试汉诺塔的时候我会在函数入口打印当前参数void hanoi(int n, char from, char aux, char to) { printf(hanoi(%d, %c, %c, %c)\n, n, from, aux, to); if (n 1) { printf(move %d from %c to %c\n, n, from, to); return; } hanoi(n - 1, from, to, aux); printf(move %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, from, to); }输出一下你就能清清楚楚看到每一次调用的参数变化问题往往一眼就能看出来。顺带说说尾递归。尾递归是指递归调用是函数体里的最后一步操作不再做任何额外计算。比如int fact_tail(int n, int acc) { if (n 0) return acc; return fact_tail(n - 1, acc * n); // 最后一步是递归调用没有后续操作 }普通的阶乘递归n * factorial(n-1)在递归返回后还要做一次乘法所以它必须保留当前栈帧等递归返回后才能算乘法。尾递归不同它把中间结果通过参数往下传理论上不需要保留外层栈帧因此现代编译器在优化选项开启时可能把它优化成循环不再消耗栈空间。但要注意C语言编译器不保证一定做尾递归优化很多OJ和评测机默认不开优化。所以别仗着“我写的是尾递归”就无限递归下去。4.4 边界条件错乱一个等于号毁掉一个OJ提交说一个特别容易阴沟翻船的细节。写二分查找的递归版int binarySearch(int a[], int left, int right, int target) { if (left right) return -1; // 边界没找到 int mid (left right) / 2; if (a[mid] target) return mid; if (a[mid] target) return binarySearch(a, mid 1, right, target); return binarySearch(a, left, mid - 1, target); }注意mid的计算。(left right) / 2其实是有隐患的如果left right很大可能整数溢出。稳妥写法是left (right - left) / 2。这算是一个面试官爱考、OJ上容易踩的经典坑。更常见的边界错乱是应该返回mid还是mid1。每次递归调用区间的划分必须保证区间缩小、不遗漏元素、不无限循环。这三个条件缺一不可。我的习惯是写完之后用两个最小例子手工走一遍一个能找到目标一个找不到目标。5. 把递归用出水平汉诺塔与八皇后的设计思维学会了基本套路你还得会举一反三。程序设计基础课的期末卷子递归的大题往往不是阶乘那种送分题而是需要你设计递归结构的题目。汉诺塔和八皇后是两道必修课。5.1 汉诺塔从“三步走”理解递归抽象汉诺塔的规则我就不重复了直接说递归解法。要把n个盘子从A柱移到C柱借助B柱先把上面n-1个盘子从A移到B借助C把最底下的大盘子从A移到C再把n-1个盘子从B移到C借助A。代码就是文章前面看到的那样但这里我想让你注意一个思维转变你根本不需要去关心“n-1个盘子具体怎么移动”。你只需要相信hanoi(n-1, A, C, B)这个调用能帮你完成这件事。至于它内部怎么倒腾那是更小规模的同一个问题它自己会解决。这种“把大问题缩小到能直接解决然后把小问题的解组合成大问题的解”的思路就是递归设计的核心。汉诺塔的递归代码难住过很多人但它的核心逻辑只有这三大步——第一步移动上方n-1个盘子第二步移动底部第n个盘子第三步移动上方n-1个盘子到目标柱。这背后的思路和你在学校社团里组织人搬宿舍是一个道理我只需要安排“负责人”去做一部分事不用事必躬亲。5.2 回溯思想八皇后里的递归不止是“递”还得有“归”如果说汉诺塔让你学会了“递”那八皇后就是让你学会“归”。八皇后问题要在8x8的棋盘上放8个皇后让它们互不攻击不同行、不同列、不同对角线。我给你的思路是一行一行放皇后。每到一个新行尝试每一列如果这个位置不冲突就放下皇后然后递归去处理下一行如果下一行怎么都放不下就回到这个位置尝试下一列——这就是回溯Backtracking。核心代码框架int queens[10]; // queens[i]表示第i行皇后所在的列号 int isSafe(int row, int col) { for (int i 0; i row; i) { if (queens[i] col) return 0; // 同列 if (abs(queens[i] - col) row - i) return 0; // 对角线 } return 1; } void solve(int row, int n) { if (row n) { // 所有行都放好了找到一个解 // 输出解 return; } for (int col 0; col n; col) { if (isSafe(row, col)) { queens[row] col; solve(row 1, n); // 放这一行递归处理下一行 // 不需要显式“撤销”下一次循环会覆盖queens[row] } } }你注意观察这里的递归结构和前面阶乘完全一样有边界条件放满一行有递归调用处理下一行规模在递减行数在增加。唯一的区别是它在一个for循环里做了多次递归尝试每次尝试都代表一种可能性。这就是递归从“求值”到“搜索”的转折。5.3 为什么说“能用递归解决的题往往也能用递归深刻理解”我教了这么多年程序设计的经验是递归不只是编程技巧它更是一种对问题结构进行抽象的能力。你写递归的过程其实是逼迫自己去回答一个问题“这个问题能不能拆成更小的自己”会拆代码就自然写出来了不会拆背十遍代码也没用。像汉诺塔、八皇后、二叉树遍历、快速排序、归并排序这些都是“结构上天然递归”的问题你用递归理解它们比背代码强得多。所以我的建议是每看到一个可以用递归解决的问题先别看题解自己在纸上画一画“这个问题凭什么能拆小”。画出来了代码就是三步法的事画不出来说明你还没吃透问题本身。我自己带过的学生里有不少人就是靠这个方法从“递归恐惧症”变成“递归真香”的。他们后来刷动态规划题时往往也更快上手——因为动态规划本质上就是在递归的基础上加了一个“备忘录用”你递归底子好转DP就是顺水推舟的事。说句题外话期末考试前我会让学生专门练三道题汉诺塔、八皇后、二叉树遍历。把这三题的递归写法烂熟于心递归这一章基本就拿下了。如果你现在正被递归折磨不妨也按这个路子来——别急递归这个东西真的就是一层窗户纸捅破一次以后就再也不怕了。 递归别死记硬背：从函数调用栈到汉诺塔八皇后实战
递归这块硬骨头我劝你别再背代码了山东理工大学SDUT的《程序设计基础Ⅱ》到了递归这一章几乎每个初学C语言的人都会卡一下。但说实话卡住的原因真的不是智商问题而是我们的大脑习惯了“从头到尾按顺序执行”的思维方式突然要你“在函数内部调用自己”一下子转不过弯来。这篇文章我打算把递归这块内容彻底讲透。不光是讲理论还会用OJ上常见的题目例子把递归的写法套路、运行机制、调试方法和选型逻辑都过一遍。不管你是刚学到函数、第一次接触递归的新手还是已经刷题刷到怀疑人生的同学这篇文章应该都能帮你把“知其然”变成“知其所以然”。顺便说一句期末考试递归必考而且往往是拉开分数的那道题所以值得你花一个小时认真看完。1. 从“函数调用函数”看递归的本质一场永不结束的套娃递归这个概念教科书上喜欢下定义“函数直接或间接调用自身”。但这句话太抽象我换一种说法递归本质上就是函数调函数只不过调用的是它自己。而“函数调函数”这件事你从学第一门课的时候就会了。1.1 你早就会函数调用了只是没反应过来想想看你在主函数里写过这样的代码printf(Hello, SDUT!);printf就是一个函数主函数调用它它执行完就返回。然后你又写过自定义函数int add(int a, int b) { return a b; } int main() { int sum add(3, 4); printf(%d, sum); return 0; }主函数调用addadd里的代码执行完把结果返回给主函数。整个过程就是调用方暂停被调方执行执行完返回调用方继续。递归就是把“被调方”换成了“自己”。比如void hello() { printf(Hello!\n); hello(); // 自己调用自己 }你运行这个程序它会把Hello!无限打印下去——因为hello执行到hello()这行时又去执行hello了永远没有返回的时候。很多人到这一步就开始懵“它怎么不往下走了”因为它根本就没走完过。caller在等callee返回而callee又在等下一个callee返回形成一个无限嵌套的等待链。1.2 用“剥洋葱”建立递归直觉我给学生讲递归时最喜欢用的类比是剥洋葱。你要把一整颗洋葱剥到最里面那层步骤是先剥掉最外面一层剥完发现还是一颗洋葱那就再剥一层重复这个过程直到剥到最里面什么都没有了。你发现没有剥洋葱的过程本身就是重复的——“剥掉一层”这个动作反复执行但剥的对象洋葱越来越小。这就是递归的核心直觉通过反复处理一个规模更小的同类问题最终到达一个不能再拆分的终点。人类理解递归的方式其实是“懒人算法”我不用关心整颗洋葱要剥多少层我只需要知道“剥一层之后剩下的还是一颗更小的洋葱重复同样的方法就行”。至于到底剥了几层那是计算机的事。1.3 运行栈递归背后的“记账本”递归能跑起来靠的是函数调用栈Call Stack。每次调用一个函数系统会在栈上分配一块区域称为栈帧Stack Frame用来存放这次调用的参数、局部变量和返回地址。函数返回时栈帧被弹出控制权交还给调用方。我画一个阶乘函数factorial(3)的调用过程你就明白了。假设代码是int factorial(int n) { if (n 1) return 1; // 边界条件 return n * factorial(n - 1); // 递归调用 }调用factorial(3)时栈上依次压入factorial(3)的栈帧: n 3等待factorial(2)的结果 factorial(2)的栈帧: n 2等待factorial(1)的结果 factorial(1)的栈帧: n 1直接返回1注意factorial(1)因为满足n 1所以不用再往下调直接返回1。然后这个结果“一层层往回送”factorial(1)返回1 → factorial(2)算出2*12 → factorial(3)算出3*26整个过程就像洋葱剥到底之后再把每一层重新粘回去。理解这个栈帧机制特别重要。因为后面你会碰到栈溢出Stack Overflow就是递归太深栈空间被用完了。到时候你就知道不是程序逻辑错而是你的递归层数超出了栈的容量。2. 手写递归的固定套路从数学归纳到代码实现“递归我能看懂但让我自己写就写不出来。”这句话我听了不下百遍。说实话写递归确实有套路而且套路非常固定。你只要按部就班地做三步大部分递归题都能写出来。2.1 三步法边界条件、递归关系、递归调用我写递归从来都是按这个顺序思考第一步找边界条件Base Case。就是“问题小到什么程度答案就显而易见了”。比如阶乘1的阶乘就是1数组求和空数组的和是0。边界条件必须有限且可到达。第二步找递归关系Recurrence Relation。就是把“n的答案”和“n-1或更小的答案”联系起来。阶乘的递归关系就是n! n * (n-1)!。第三步把递归关系写成代码。在函数体内调用自身注意调用的规模必须朝边界条件方向递减。拿阶乘来说int factorial(int n) { // 第一步边界条件 if (n 1) return 1; // 第三步递归调用规模n-1 n朝边界靠近 return n * factorial(n - 1); }三步走完代码就出来了。但这里有个很多教材没点破的细节为什么边界条件是n 1而不是n 1因为如果某人传入factorial(0)n 1就会无限递归。写成n 10的阶乘也能正确返回1。这就是我在实际写代码时的一个习惯边界条件宁可多覆盖一点也别留缝隙。2.2 从数学归纳法理解递归的正确性写递归的人本质上是在用数学归纳法思考。数学归纳法有两步证明n1时命题成立对应边界条件假设nk成立证明nk1成立对应递归关系。递归代码的正确性也是靠这两点保证的。你不需要在脑子里把factorial(500)的完整调用链条跑一遍——你只需要相信两件事边界条件是对的如果factorial(n-1)返回了正确答案那么n * factorial(n-1)也是正确答案。这就是所谓的递归信任Recursive Leap of Faith。我当年学递归的时候老师说过一句话让我记到现在“写递归的时候别想着递归的过程只想着递归的结果。”意思是你在写factorial(n)函数体时直接假设factorial(n-1)是对的函数把它当现成的工具用就行。2.3 经典入门题实战数组求和与字符串反转光说理论没用我们上手写两个OJ最常见的入门递归题。数组求和给定数组a[]和长度n返回所有元素之和。int sum(int a[], int n) { if (n 0) return 0; // 边界空数组和为0 return sum(a, n - 1) a[n - 1]; // 递归前n-1个元素的和 第n个元素 }这个写法非常典型把“求n个元素的和”转化为“求n-1个元素的和加上最后一个元素”。规模从n减到n-1一直到0。字符串反转给定字符串s反转后输出。void reverse(char s[], int start, int end) { if (start end) return; // 边界只剩0个或1个字符无需反转 char tmp s[start]; s[start] s[end]; s[end] tmp; reverse(s, start 1, end - 1); // 递归处理中间的字符串 }这里的递归思路是先把首尾字符交换然后“里面的字符串交给递归去做”。你看一旦想通了递归代码其实很简洁比循环写起来还要直观。2.4 为什么“兔子数列”是递归教学的头号陷阱说到递归必然绕不开斐波那契数列int fib(int n) { if (n 0 || n 1) return n; return fib(n - 1) fib(n - 2); }代码只有三行看起来非常完美。但你要是真去算fib(50)你会等到怀疑人生。原因很简单这个递归存在大量重复计算。fib(5)要算fib(4)和fib(3)而fib(4)又要算fib(3)和fib(2)——同一个fib(3)被算了两次。展开之后你会发现这棵递归树几乎膨胀成一棵满二叉树时间复杂度是O(2^n)。我给学生讲这个例子是想说明一个重要的道理写得出不等于写得好。你学会了递归的套路还得学会判断“这个递归值不值得写”。斐波那契用循环写只要O(n)int fib(int n) { if (n 1) return n; int a 0, b 1, c; for (int i 2; i n; i) { c a b; a b; b c; } return b; }所以在实际做题时我通常先问自己一句“这个问题用递归写会不会有严重的重复计算”如果有要么加个数组做记忆化要么直接改迭代。3. 递归和迭代的正面交锋机制差异与选型依据你肯定听说过“递归和迭代可以互相转换”这句话。没错理论上任何递归都能用循环加栈模拟出来任何循环也都能改写成递归。但理论归理论真到做题和写项目的时候选哪个是要拿实际约束说话的。3.1 从求1加到n看两种思维方式的差异先看最简单的题目求1 2 ... n。迭代写法int sum_iter(int n) { int s 0; for (int i 1; i n; i) s i; return s; }递归写法int sum_rec(int n) { if (n 0) return 0; return sum_rec(n - 1) n; }迭代的思路是“从1开始累加加到一个目标值”它维护一个不断变化的累加变量本质上是一个一个地把工作做完。递归的思路是“我先把前面n-1项的和算出来再加上最后一项”本质上是把一个大问题分解成同构的小问题。这两种思路没有高下之分但它们对应的场景不一样。迭代适合“过程明确、每个步骤都看得见”的任务递归适合“问题能自然按规模拆分”的任务。3.2 同一个功能两种实现的性能对比说个SDUT OJ上很经典的问题求最大公约数用辗转相除法。这是递归和迭代都能轻松写的题目。递归实现int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b); }迭代实现int gcd_iter(int a, int b) { while (b ! 0) { int tmp a % b; a b; b tmp; } return a; }从性能角度说递归版每次调用都要分配栈帧、保存现场开销比循环大。但请注意这里的“大”是相对于普通循环而言的。gcd的递归深度非常浅对数级别所以两者运行时间几乎无差别。真正有差别的是斐波那契那种“递归爆炸”的题目那种情况下递归版会慢到不可用。我给一个经验判断标准你直接照抄即可场景推荐方案递归深度很小1000代码简洁递归嵌套结构本身有层数概念树、图、括号匹配递归数据规模大对性能敏感可能深递归迭代 显式栈存在大量重复子问题迭代或递归 记忆化3.3 什么时候必须用递归什么时候千万别用先说“千万别用”的场景递归深度不可控的时候。比如说你要处理一个可能上万层的嵌套结构用递归写得很爽但程序一运行就爆栈。这时候你就需要把递归改成迭代自己维护一个栈。再说“最好用递归”的场景问题本身的定义就是递归的。典型的例子是二叉树的遍历。树的定义本身就是“一个节点下面挂两棵子树”用递归写出来的遍历代码干净利落void inOrder(struct TreeNode* root) { if (root NULL) return; inOrder(root-left); printf(%d , root-val); inOrder(root-right); }如果用迭代写中序遍历你得手动模拟栈代码起码翻倍还得小心入栈出栈的顺序。所以这棵树长得那么“递归”你就别非拿循环跟它硬碰。4. 递归调试与翻车现场爆栈、无限递归和边界错乱写递归最大的痛苦不是写不出来而是写出来了却不知道错在哪。循环写错了你可以单步调试递归写错了你单步调试都可能陷进去出不来。这一节我讲讲自己在LibreOJ和SDUT OJ上踩过的那些递归坑。4.1 栈溢出不是逻辑错而是层数太深先说最经典的一个错误。写这个求幂的递归int power(int x, int n) { if (n 0) return 1; return x * power(x, n - 1); }算power(2, 100000)程序崩溃。报错通常是Segmentation fault或者Stack overflow。很多人第一反应是“我代码哪里写错了”但其实逻辑完全没毛病错在递归深度超过了栈的容量。每一层递归大约消耗几十字节到上百字节的栈空间。默认栈空间在Linux下通常是8MB在Windows MSVC下通常是1MB。假设一层消耗100字节1MB栈大概能支持一万层递归。你算power(2, 100000)就是10万层不炸才怪。遇到这种情况要么把递归改成循环要么用快速幂——快速幂的递归深度是O(log n)10万次方深度只有17层左右int fastPower(int x, int n) { if (n 0) return 1; if (n % 2 1) return x * fastPower(x, n - 1); return fastPower(x * x, n / 2); }所以你看递归并非不能深层关键是深度要以对数级别增长而不是线性级别。4.2 无限递归少了那行“return”的惨痛教训写递归时最深恶痛绝的BUG忘记写边界条件或者边界条件永远达不到。比如void countDown(int n) { printf(%d , n); countDown(n - 1); }看起来没啥问题n确实一直在减。但问题是n减成负数之后呢这个递归没有任何停下来的条件它会一直减到int溢出然后变成正数继续减……无限循环。正确写法void countDown(int n) { if (n 0) return; // 边界条件 printf(%d , n); countDown(n - 1); }还有另一种隐蔽的情况递归调用时参数没变。比如int f(int n) { if (n 0) return 1; return f(n); // 参数还是n根本没变小 }这代码跑起来就是活脱脱的“死循环”而且比while(1)难排查得多——因为它披着“递归”的外衣让你总觉得哪里有点不对但说不出来。所以写递归时养成一个习惯每次写递归调用先看一眼参数是不是比原来的小。4.3 调试递归的两把斧头打印调用树和“尾递归”陷阱我在OJ上调试递归不喜欢单步跟因为跟几步就晕了。我更喜欢打印调用痕迹。例如调试汉诺塔的时候我会在函数入口打印当前参数void hanoi(int n, char from, char aux, char to) { printf(hanoi(%d, %c, %c, %c)\n, n, from, aux, to); if (n 1) { printf(move %d from %c to %c\n, n, from, to); return; } hanoi(n - 1, from, to, aux); printf(move %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, from, to); }输出一下你就能清清楚楚看到每一次调用的参数变化问题往往一眼就能看出来。顺带说说尾递归。尾递归是指递归调用是函数体里的最后一步操作不再做任何额外计算。比如int fact_tail(int n, int acc) { if (n 0) return acc; return fact_tail(n - 1, acc * n); // 最后一步是递归调用没有后续操作 }普通的阶乘递归n * factorial(n-1)在递归返回后还要做一次乘法所以它必须保留当前栈帧等递归返回后才能算乘法。尾递归不同它把中间结果通过参数往下传理论上不需要保留外层栈帧因此现代编译器在优化选项开启时可能把它优化成循环不再消耗栈空间。但要注意C语言编译器不保证一定做尾递归优化很多OJ和评测机默认不开优化。所以别仗着“我写的是尾递归”就无限递归下去。4.4 边界条件错乱一个等于号毁掉一个OJ提交说一个特别容易阴沟翻船的细节。写二分查找的递归版int binarySearch(int a[], int left, int right, int target) { if (left right) return -1; // 边界没找到 int mid (left right) / 2; if (a[mid] target) return mid; if (a[mid] target) return binarySearch(a, mid 1, right, target); return binarySearch(a, left, mid - 1, target); }注意mid的计算。(left right) / 2其实是有隐患的如果left right很大可能整数溢出。稳妥写法是left (right - left) / 2。这算是一个面试官爱考、OJ上容易踩的经典坑。更常见的边界错乱是应该返回mid还是mid1。每次递归调用区间的划分必须保证区间缩小、不遗漏元素、不无限循环。这三个条件缺一不可。我的习惯是写完之后用两个最小例子手工走一遍一个能找到目标一个找不到目标。5. 把递归用出水平汉诺塔与八皇后的设计思维学会了基本套路你还得会举一反三。程序设计基础课的期末卷子递归的大题往往不是阶乘那种送分题而是需要你设计递归结构的题目。汉诺塔和八皇后是两道必修课。5.1 汉诺塔从“三步走”理解递归抽象汉诺塔的规则我就不重复了直接说递归解法。要把n个盘子从A柱移到C柱借助B柱先把上面n-1个盘子从A移到B借助C把最底下的大盘子从A移到C再把n-1个盘子从B移到C借助A。代码就是文章前面看到的那样但这里我想让你注意一个思维转变你根本不需要去关心“n-1个盘子具体怎么移动”。你只需要相信hanoi(n-1, A, C, B)这个调用能帮你完成这件事。至于它内部怎么倒腾那是更小规模的同一个问题它自己会解决。这种“把大问题缩小到能直接解决然后把小问题的解组合成大问题的解”的思路就是递归设计的核心。汉诺塔的递归代码难住过很多人但它的核心逻辑只有这三大步——第一步移动上方n-1个盘子第二步移动底部第n个盘子第三步移动上方n-1个盘子到目标柱。这背后的思路和你在学校社团里组织人搬宿舍是一个道理我只需要安排“负责人”去做一部分事不用事必躬亲。5.2 回溯思想八皇后里的递归不止是“递”还得有“归”如果说汉诺塔让你学会了“递”那八皇后就是让你学会“归”。八皇后问题要在8x8的棋盘上放8个皇后让它们互不攻击不同行、不同列、不同对角线。我给你的思路是一行一行放皇后。每到一个新行尝试每一列如果这个位置不冲突就放下皇后然后递归去处理下一行如果下一行怎么都放不下就回到这个位置尝试下一列——这就是回溯Backtracking。核心代码框架int queens[10]; // queens[i]表示第i行皇后所在的列号 int isSafe(int row, int col) { for (int i 0; i row; i) { if (queens[i] col) return 0; // 同列 if (abs(queens[i] - col) row - i) return 0; // 对角线 } return 1; } void solve(int row, int n) { if (row n) { // 所有行都放好了找到一个解 // 输出解 return; } for (int col 0; col n; col) { if (isSafe(row, col)) { queens[row] col; solve(row 1, n); // 放这一行递归处理下一行 // 不需要显式“撤销”下一次循环会覆盖queens[row] } } }你注意观察这里的递归结构和前面阶乘完全一样有边界条件放满一行有递归调用处理下一行规模在递减行数在增加。唯一的区别是它在一个for循环里做了多次递归尝试每次尝试都代表一种可能性。这就是递归从“求值”到“搜索”的转折。5.3 为什么说“能用递归解决的题往往也能用递归深刻理解”我教了这么多年程序设计的经验是递归不只是编程技巧它更是一种对问题结构进行抽象的能力。你写递归的过程其实是逼迫自己去回答一个问题“这个问题能不能拆成更小的自己”会拆代码就自然写出来了不会拆背十遍代码也没用。像汉诺塔、八皇后、二叉树遍历、快速排序、归并排序这些都是“结构上天然递归”的问题你用递归理解它们比背代码强得多。所以我的建议是每看到一个可以用递归解决的问题先别看题解自己在纸上画一画“这个问题凭什么能拆小”。画出来了代码就是三步法的事画不出来说明你还没吃透问题本身。我自己带过的学生里有不少人就是靠这个方法从“递归恐惧症”变成“递归真香”的。他们后来刷动态规划题时往往也更快上手——因为动态规划本质上就是在递归的基础上加了一个“备忘录用”你递归底子好转DP就是顺水推舟的事。说句题外话期末考试前我会让学生专门练三道题汉诺塔、八皇后、二叉树遍历。把这三题的递归写法烂熟于心递归这一章基本就拿下了。如果你现在正被递归折磨不妨也按这个路子来——别急递归这个东西真的就是一层窗户纸捅破一次以后就再也不怕了。