1. 递归到底是个什么东西很多人在学C语言的时候学到函数这块就卡住了尤其是递归。数组、指针、结构体好歹能看到实实在在的数据在内存里怎么摆但递归这东西代码看起来就那么几行执行起来却像变魔术一样让人摸不着头脑。先给一个粗暴但准确的定义递归就是函数自己调用自己。不是函数的拷贝是同一个函数在执行的过程中又调用了自己。这句话看起来简单但很多初学者第一个疑惑就是它调用自己那不就无限循环了吗程序不得爆掉问得好这正是递归的核心问题。答案在于递归必须满足两个关键条件递归出口和递推公式。没有出口的递归就是死循环迟早把栈空间耗尽导致程序崩溃没有递推关系的递归就是原地打转毫无意义。举个例子计算n的阶乘int factorial(int n) { if (n 1) { return 1; // 递归出口 } return n * factorial(n - 1); // 递推公式 }你执行factorial(5)的时候函数并不会立刻算出结果。它会先变成5 * factorial(4)然后变成5 * 4 * factorial(3)层层递进一直到5 * 4 * 3 * 2 * factorial(1)碰到出口条件n 1返回1然后再一层层归回来5*4*3*2*1。整个过程可以想象成查字典你要查久字发现解释里有个遥字不认识于是去查遥结果遥的解释里又有远字不认识再去查远……直到查到一个所有字都认识的字条才能一层层倒回去最终弄明白久是什么意思。这个从入口一路问到出口再从出口一路带回答案的过程就是递归最核心的逻辑。那什么样的问题适合用递归理论上只要一个问题能被拆成规模更小但结构相同的子问题就适合递归。最典型的就在两个经典问题上汉诺塔和青蛙跳台阶。这篇文章就把这两个问题从头到尾拆开揉碎讲清楚顺带把递归的底层机制、性能陷阱、调试技巧一网打尽。2. 递归背后的执行机制在动手写代码之前必须先把递归的底层执行机制搞明白否则你写出来的递归就是碰运气对了不知道为什么对错了也不知道怎么改。2.1 栈帧函数调用的真相C语言里每次函数调用系统都会在内存的栈区stack分配一块空间叫栈帧stack frame。这个栈帧里保存了三个关键信息函数的局部变量、参数值以及返回地址——也就是调用完这个函数后该回到哪里继续执行。每次调用新函数就压入一个新栈帧每次函数返回就弹出栈顶帧。这和我们平时摞盘子一模一样后放上去的先拿下来这叫后进先出。重点是递归调用时每次调用同一个函数会创建不同的栈帧。你以为它们在同一个函数里其实每一层的局部变量都独立存在互不干扰。比如上面阶乘的例子递归第5层的那个n和第4层的n虽然名字都叫n但它们住的是不同的房间。这就能解释一个很多新手都会犯的错在递归函数里用了全局变量或静态变量来保存中间结果。这些变量是全函数共享的不是每层独立的。你这一层的修改下一层看得见下一层改了上一层也会受影响最后结果全乱套。所以写递归优先用参数和返回值传递数据别依赖全局状态这是第一条铁律。2.2 递归的递与归递归的执行过程可以拆成两个阶段递——一层层调用下去直到碰到出口归——出口返回结果结果一层层倒着传回来。还是看阶乘factorial(5)的完整过程递factorial(5) → 5 * factorial(4) 递factorial(4) → 4 * factorial(3) 递factorial(3) → 3 * factorial(2) 递factorial(2) → 2 * factorial(1) 递factorial(1) → 1 // 到达出口 归factorial(1) 返回 1 归factorial(2) 返回 2 * 1 2 归factorial(3) 返回 3 * 2 6 归factorial(4) 返回 4 * 6 24 归factorial(5) 返回 5 * 24 120看到没有递的时候从大到小归的时候从小到大后调用的先返回。一句话先深入再回溯这就是递归的本质节奏。很多同学看完递就晕了其实真正计算发生在归的阶段。你想factorial(5)里的那个* factorial(4)要等factorial(4)算出结果才能执行乘法运算所以真正干活的时机是归的过程。递归的代码写在调用自己之前是递的时候干活写在自己之后是归的时候干活。这个理解对后面的汉诺塔特别关键——它的输出语句放在两次递归调用的中间执行顺序非常反直觉。2.3 递归深度和栈溢出栈区空间是有限的不同平台不一样常见默认在1MB~8MB。每次函数调用占用多少栈帧取决于局部变量大小几十到几百字节很正常。所以一个递归能深入多少层是有上限的。如果递归深度太大栈帧不断压入最终超出栈的容量就会触发栈溢出stack overflow程序直接崩溃。我在Linux上试过一个不带额外局部变量的空递归函数深度大概到几十万层就会段错误。实操里我一般给你一个经验红线递归深度在1万层以内比较安全超过就要考虑改写成迭代或者深度优先搜索配显式栈。刷题网站上经常有斐波那契那种记忆化递归突然爆栈的问题十有八九就是这个深度问题不是你的逻辑错了。3. 汉诺塔问题全拆解汉诺塔Hanoi Tower应该是最能体现递归魅力的题目了没有之一。初见时觉得巨难无比搞懂之后会觉得递归真他妈优雅。3.1 问题描述有3根柱子分别叫A起始柱、B辅助柱、C目标柱。A柱上从下往上按大小顺序摞着n个圆盘。要求把所有圆盘从A移到C规则有两条每次只能移动一个圆盘任何时候大盘不能压在小盘上面问n个圆盘时最少需要移动多少次每一步怎么移3.2 从最小的规模开始找感觉面对这种问题不要一上来就想着n个盘子。我们先从最简单的开始推。n1一个盘子直接从A移到C完成。共1步。n2两个盘子小盘1号在大盘2号上面。1号盘A → B先把小的挪开2号盘A → C大的直接去目标位1号盘B → C小的再挪到大的上面共3步。n3三个盘子的时候情况就开始复杂了但核心思路是先把上面2个盘子从A移到B借助C——这一步怎么移就是上面n2的过程只是目标柱从C换成了B再把最大的3号盘从A移到C最后把B上的2个盘子移到C借助A——这又是一次n2的移动你发现规律了吗不管多少个盘子移动n个盘子的问题总是可以拆成三步把上面的 n-1 个盘子从 A 移到 B借助 C把最底下的第 n 个盘子从 A 移到 C把 B 上的 n-1 个盘子从 C 移到目标 C借助 A而把n-1个盘子从某根柱移到另一根柱又是一个规模更小、规则完全相同的汉诺塔问题。这不就是递归吗3.3 代码实现#include stdio.h void hanoi(int n, char from, char tmp, char to) { if (n 1) { // 只有一个盘子直接移动 printf(第1个盘: %c - %c\n, from, to); return; } // 第一步把上面n-1个盘子从from移到tmp借助to hanoi(n - 1, from, to, tmp); // 第二步把第n个盘子从from移到to printf(第%d个盘: %c - %c\n, n, from, to); // 第三步把tmp上的n-1个盘子从tmp移到to借助from hanoi(n - 1, tmp, from, to); } int main() { int n 3; printf(移动 %d 个盘子的步骤:\n, n); hanoi(n, A, B, C); return 0; }运行结果移动 3 个盘子的步骤: 第1个盘: A - C 第2个盘: A - B 第1个盘: C - B 第3个盘: A - C 第1个盘: B - A 第2个盘: B - C 第1个盘: A - C正好7步。你可以拿纸和笔拿三个硬币模拟一下每一步都对得上。这个函数的参数设计有一个细节需要注意from、tmp、to三个参数表示的是角色不是固定某根柱子。同一根柱子在这一层调用里可能是from在下一层调用里就变成了tmp。很多同学看递归看晕就是没转过这个弯来——函数参数的含义是现场的、临时的A/B/C是具体的角色是会变化的。3.4 为什么这个代码是对的很多人第一次看到这个代码最大的困惑是不就三行调用吗凭什么它能算出正确的移动步骤我们一层层看。假设hanoi(3, A, B, C)第一步调用hanoi(2, A, C, B)意思是我要把2个盘子从A移到B用C做辅助。这本身就是一个子问题。它内部先调用hanoi(1, A, B, C)输出A→C第1号盘先挪走输出2号盘A→B再调用hanoi(1, C, A, B)输出C→B回到外层输出3号盘A→C再调用hanoi(2, B, A, C)把2个盘子从B移到C用A做辅助。内部先输出B→A输出2号盘B→C输出A→C关键在于每一层都只关心怎么把当前这堆盘子当成一个整体来挪至于挪的过程中内部怎么折腾完全交给下一层递归处理。你不需要在脑子里把每一层每一步都展开你只需要相信只要子问题能被正确解决那组合起来整个问题就解决了。这就是递归里的相信过程。这种大事化小、小事化了的思路在算法上有个正式名字叫分治法把一个大问题分解成若干个独立的、规模更小的同类子问题分别求解再合并结果。3.5 最少移动次数推导汉诺塔问题还有一个经典变体问n个盘子最少需要移多少次。设f(n)表示n个盘子的最少移动次数根据前面拆解的三步移走上面n-1个盘子f(n-1)次移最下面的大盘1次再把n-1个盘子移回来f(n-1)次所以递推关系是f(n) 2 * f(n-1) 1 f(1) 1展开一下f(1) 1 f(2) 2*1 1 3 f(3) 2*3 1 7 f(4) 2*7 1 15看出规律没有f(n) 2^n - 1。64个盘子的传说需要的次数是2^64 - 1按一秒移一次得5849亿年比宇宙年龄还长这就是指数爆炸的威力。这个推导过程也完美体现了递归思维的另一层用法用递推公式描述问题规模的增长规律。很多时候你不需要真的去模拟每一步用一个递推式就能分析出复杂度。3.6 汉诺塔的常见变体和坑变体1目标柱不同的汉诺塔。比如要求从A移到BC是辅助那么调用hanoi(n, A, C, B)就行逻辑不用改。变体2返回步数。不改打印功能加一个返回值int hanoi_count(int n, char from, char tmp, char to) { if (n 1) { printf(第1个盘: %c - %c\n, from, to); return 1; } int count 0; count hanoi_count(n - 1, from, to, tmp); printf(第%d个盘: %c - %c\n, n, from, to); count; count hanoi_count(n - 1, tmp, from, to); return count; }坑1打印语句的顺序。汉诺塔的打印语句夹在两个递归调用中间这意味着归的时候先执行完第一个递归打印当前层再执行第二个递归。这个顺序一旦写反整个移动步骤就是错的。正确逻辑必须是先把小的移到辅助柱再动大盘最后把小的移到目标柱。三大步的顺序绝不能乱。坑2递归出口必须最先判。很多人喜欢把if (n1)写到最后面或者不写出口直接写if (n0) return;也能跑但容易在传0的时候出问题。我建议统一n1作为出口逻辑最直观。4. 青蛙跳台阶问题精解如果说汉诺塔是递归的形那青蛙跳台阶就是递归的神——它背后藏着动态规划和斐波那契数列是面试场上出现频率极高的题目。4.1 问题描述一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。请问它跳上n级台阶总共有多少种跳法注意这里问的是多少种跳法不是具体每一步怎么跳。这是个计数问题最怕的就是一上来就在脑子里枚举所有路径很快就会乱。正确姿势是把问题递推化。4.2 递推思路推导假设f(n)表示跳上n级台阶的跳法数。先看最简单的f(1)只有1级台阶只能跳1级1种跳法。f(2)可以11跳两次也可以直接跳2级2种跳法。现在跳到关键的n了。青蛙在第一跳只有两种选择跳1级或者跳2级。如果第一跳跳1级那剩余n-1级台阶的跳法就是f(n-1)种。如果第一跳跳2级那剩余n-2级台阶的跳法就是f(n-2)种。这两种情况互斥且完备不可能同时发生也不会漏掉任何情况所以f(n) f(n-1) f(n-2) f(1) 1 f(2) 2看到这个递推式熟悉斐波那契数列的同学应该已经反应过来了这不就是斐波那契吗标准的斐波那契是F(1)1, F(2)1, F(n)F(n-1)F(n-2)青蛙跳台阶只是把第二项从1改成了2。用表格列一下n123456f(n)1235813验证一下n3跳法为 111、12、21正好3种。n41111、112、121、211、22正好5种。没问题。4.3 朴素递归实现#include stdio.h int jump(int n) { if (n 1) { return 1; } if (n 2) { return 2; } return jump(n - 1) jump(n - 2); } int main() { for (int i 1; i 10; i) { printf(jump(%d) %d\n, i, jump(i)); } return 0; }这段代码逻辑完全正确但你拿它跑jump(45)会发现越来越慢跑jump(50)可能就要等好久。问题出在哪4.4 递归的性能陷阱把jump(5)的调用关系画出来jump(5) ├── jump(4) │ ├── jump(3) │ │ ├── jump(2) │ │ └── jump(1) │ └── jump(2) └── jump(3) ├── jump(2) └── jump(1)看到没有jump(3)被算了2次jump(2)被算了3次。n越大重复计算的次数呈指数增长。jump(50)需要计算的次数大约是2^50级别这谁扛得住这就是递归最典型的性能坑当一个递归会把同一个子问题重复计算很多次的时候它的时间复杂度是指数级的。斐波那契的朴素递归时间复杂度是O(2^n)听起来就吓人。解决思路有两条记忆化搜索把算过的结果存起来和改成迭代从底部往上算。这两个方案下面各写一段。4.5 优化方案一记忆化递归思路很简单第一次算出jump(3)之后把结果存在一个数组里后面再要jump(3)直接查表返回不重复递归。#include stdio.h #define MAX 100 long long memo[MAX] {0}; long long jump_memo(int n) { if (n 1) { return 1; } if (n 2) { return 2; } if (memo[n] ! 0) { return memo[n]; } memo[n] jump_memo(n - 1) jump_memo(n - 2); return memo[n]; } int main() { for (int i 1; i 50; i) { printf(jump(%d) %lld\n, i, jump_memo(i)); } return 0; }加了一个memo数组每个子问题只算一次时间复杂度直接从O(2^n)降到O(n)。我实测跑jump(50)瞬间出结果。注意我用了long long因为jump(50)的结果超过int的范围了——这是另一个容易踩的坑算到后面数字涨得飞快int根本装不下。4.6 优化方案二迭代递推既然有了递推公式f(n) f(n-1) f(n-2)那就完全没必要用递归。直接用两个变量滚着算#include stdio.h long long jump_iter(int n) { if (n 1) { return 1; } if (n 2) { return 2; } long long a 1; // f(n-2) long long b 2; // f(n-1) long long c 0; for (int i 3; i n; i) { c a b; a b; b c; } return c; } int main() { for (int i 1; i 50; i) { printf(jump(%d) %lld\n, i, jump_iter(i)); } return 0; }迭代版本连递归调用都没了更不会爆栈空间是O(1)时间还是O(n)。如果你被问到青蛙跳台阶面试官大概率会追一句能不能不用递归实现你直接把这个版本甩出来印象分拉满。4.7 问题变体一次能跳n级同一道题的经典变体如果青蛙一次可以跳1级、2级、……甚至n级那跳到第n级有多少种跳法推理稍微绕一点。设f(n)为跳法数。第一跳可以跳k级1 k n跳完k级后剩下n-k级的跳法数是f(n-k)所以f(n) f(n-1) f(n-2) ... f(1) f(0)其中f(0)表示一次直接跳完看作1种。展开这个式子f(n-1) f(n-2) f(n-3) ... f(1) f(0)两个式子相减得到f(n) 2 * f(n-1)结合f(1) 1所以f(n) 2^(n-1)。这个拓展版本的核心思想是递推关系的归纳与消元如果你把前面的f(n)f(n-1)f(n-2)理解透了这个变形其实不难推导。面试遇到这种变体能现场推出2^(n-1)这个结论说明你的递推思维已经过关了。5. 递归实战的进阶技巧理论吃透了代码也会写了接下来聊聊真正写工程代码、刷题、做笔试时用得上的实战技巧。5.1 什么时候用递归什么时候别用我的建议是递归用在问题天然有递归结构的场景比如树的遍历、目录遍历、分治排序快速排序、归并排序、动态规划的记忆化搜索。这些问题的数据结构树、图本身就是递归定义的用递归顺手得不得了。反过来如果问题本质是线性的能一眼看出循环能解决就别硬递归。比如求和、求最大值、逐行处理文件用循环简单明了非要递归反而把简单问题搞复杂还增加栈溢出风险。至于递归和迭代怎么选给个参考场景推荐方案原因树/图遍历递归结构天然递归代码极简分治算法递归分解合并逻辑清晰大深度搜索如数独迭代显式栈避免栈溢出线性计算求和/阶乘迭代性能更好更安全递推关系斐波那契迭代/记忆化避免重复计算5.2 写递归的三个固定步骤我自己带人的时候都会教他们一个固定套路按这个顺序想递归就不会乱定义函数签名明确这个函数输入什么、输出什么。比如jump(int n)输入台阶数输出跳法数。找递推关系想清楚当前问题和子问题之间的联系。这一步往往需要你手动推几个小规模case找到规律。确定递归出口最小的规模直接返回。注意出口必须覆盖所有可能走到最小规模的情况不缺不漏。三步走完再翻译成代码。绝大部分写不出递归的人都是卡在第二步——连递推关系都没想明白就急着写代码全凭感觉瞎试当然写不出来。5.3 递归调试打印大法很多初学者调试递归有个坏习惯一看到结果不对就开始在脑子里模拟整个递归过程恨不得把每一个栈帧推演一遍。这不是人类干的事。正确的做法是在关键位置加打印语句看每一层的参数进来是什么、返回值是什么int jump_dbg(int n, int depth) { for (int i 0; i depth; i) { printf( ); } printf([%d] enter, n%d\n, depth, n); if (n 1) { printf([%d] return 1\n, depth); return 1; } if (n 2) { printf([%d] return 2\n, depth); return 2; } int res jump_dbg(n - 1, depth 1) jump_dbg(n - 2, depth 1); printf([%d] return %d\n, depth, res); return res; }用depth参数控制缩进每一层的日志一眼就能对上。看到哪一层的返回值不对问题就出在哪一层的递推关系或出口上。不要用眼睛追踪递归要让计算机帮你把过程打印出来这是区分新手和老手的一个重要习惯。5.4 常见错误清单日常写递归集齐这六种错误就能召唤神龙了。我一个个说你们一个个记。错误1递归出口缺失或永远到达不了。函数一直在递归调用没有停下来的条件最后栈溢出。典型代码int f(int n) { return f(n - 1); // 没有出口 }错误2出口条件写错导致提前返回。比如n0和n1的出口返回值给搞混结果整个递推全错。多检查边界值。错误3递推公式写错。比如汉诺塔写成了hanoi(n-1, from, to, tmp)却把参数顺序传错或者青蛙跳台阶写成f(n-1) f(n)——后者就永远递归不完这种错误往往在参数多的时候特别隐蔽。错误4忽略了递归的返回值。有些人喜欢在递归调用外面包一层却忘了把返回值返回给上层void hanoi(int n, char from, char tmp, char to) { if (n 1) { printf(...); return; } hanoi(n - 1, from, to, tmp); // 如果这个函数需要有返回值你却没接收信息就丢了 ... }这个在C语言里特别邪门因为编译器往往只给warning不给error程序能编译能运行但结果就是不对。错误5重复计算导致超时。就是你写的朴素斐波那契n一大就卡死。已经讲过了上记忆化或者循环。错误6int溢出。递归算到后面数字很大int不够用。之前那个青蛙跳台阶算到46就超int了。习惯性用long long必要时上unsigned long long或者大数库。6. 从递归到工程思维的升华递归学到最后你会发现它不只是C语言的一个语法技巧而是一种思维方式。它逼着你把大问题拆成小问题小问题拆成更小的问题直到每个问题都能直接求解。这个过程就是工程里常说的分而治之。6.1 递归思想在算法里的延伸掌握了递归的基础你去看后面这些算法会特别顺畅归并排序把数组对半分分别排序再合并。分治思想的教科书级应用。快速排序选一个基准把数组分成左右两半递归排序。树的遍历二叉树的前序/中序/后序遍历代码极其优雅基本就是三行递归。回溯算法八皇后、数独、全排列核心框架就是递归撤销选择。深度优先搜索走迷宫、图的连通性判断一个DFS函数递归调用自己配上visited数组标记就能走遍整张图。很多人学算法觉得难一个很重要的原因是递归思维没建立起来。因为算法世界里到处都是递归结构你不会递归看啥都像天书你会了很多东西就一通百通了。6.2 C语言递归性能的几个优化细节如果你在写性能敏感的程序比如嵌入式、游戏服务器递归有这几个锦上添花的点尾递归优化。如果递归调用是函数的最后一个操作并且结果直接返回这种叫尾递归。现代编译器一般能把它优化成循环避免栈深度增长。C语言标准本身不强制要求尾调用优化但GCC在优化级别-O2以上通常能做。想确认可以反汇编看生成的代码里还有没有call指令。// 尾递归版本的写法 int factorial_tail(int n, int acc) { if (n 1) { return acc; } return factorial_tail(n - 1, acc * n); }内联函数。在C99或C11里用inline关键字提示编译器把短小的函数体直接嵌入到调用处省去函数调用开销。但递归函数通常不建议内联因为无法完全展开而且代码体积会膨胀。小递归函数可以试试大递归别碰。善用静态/动态规划。递归只是手段不是目的。一个问题能递推就不要纯递归能用迭代就用迭代。最经典的反例就是斐波那契纯递归的时间复杂度是O(2^n)迭代是O(n)差了天和地。递归的价值在于清晰如果清晰和高效发生冲突工程里优先保证清晰但如果你发现复杂度已经不是常数级别的差距那必须考虑优化方案来做折中。6.3 从面试角度聊聊这两道题面试官问汉诺塔、青蛙跳台阶其实想考察的是三件事第一你能不能建模。给你一个具体问题你能不能抽象出递推关系。很多人卡在这一步是因为脑子里没有假设子问题已解决这个概念。你得敢说假设我已经知道怎么移n-1个盘子了然后在此基础上推导n个盘子。第二你知不知道边界条件。也就是递归出口。出口写不对或者写不全代码就跑不对。第三你了不了解性能边界。青蛙跳台阶问完之后面试官多半会追问你的递归有什么问题怎么优化。能主动说出重复计算、记忆化、迭代三个优化方向基本就是加分项。我见过太多人去面试青蛙跳台阶的递归代码写出来了结果问一句这个时间复杂度是多少直接卡壳再问怎么优化就抓瞎。所以这里再强调一遍题目能AC只是及格能分析复杂度、能优化、能变体扩展才是面试官真正想看的。6.4 我的一些个人体会写递归写了这么多年最大的感悟是递归的核心不是代码而是信任。你要相信只要递推关系和出口都是对的计算机一定能给你跑出正确结果。初学者最怕的是不信任递归的自我修复能力总想手动干预中间过程结果越改越乱。第二个感悟是递归这东西光看是真的看不懂的必须动手推。我教过很多学生最快的入门方式就是拿3个、4个硬币照着汉诺塔的打印结果一行一行模拟亲手把每步移动摆出来。摆过3遍你就再也不会忘记汉诺塔为什么是那样写的了。最后如果你现在正在为C语言里某个递归题目抓狂我给你一个可执行的建议别盯着屏幕发呆拿支笔把调用树一层一层展开在纸上把每一层的参数和返回值标出来。展开到第三层你基本就能看清整个逻辑了。这个方法土但百分之百管用。