递归这个名词很多学C语言的同学一听就头大。课本上说递归就是函数调用自己看起来只有几个字可真到自己写代码的时候要么编译通过却跑不起来要么运行起来直接卡死要么就是栈溢出。C语言100篇系列写到这里第17篇《函数嵌套与递归递归思想与终止条件》正好是整个系列里一个分水岭。函数嵌套是基础递归思想是进阶终止条件是防止程序失控的刹车片——这三块搞明白了你会突然觉得很多复杂问题树的遍历、快速排序、表达式求值都变得豁然开朗。这篇文章不讲虚的直接带你把函数嵌套、递归思想、终止条件这三件事从原理到实践全部走一遍。内容适合已经掌握C语言基本语法函数、判断、循环但还没真正理解递归的读者也适合想复习递归思想的老手。我会穿插一些我在实际写代码和带新人过程中踩过的坑、总结的经验帮你少走弯路。1. 函数嵌套先搞懂C语言里函数之间是怎么传话的1.1 什么是函数嵌套调用在C语言里函数是一个独立的代码块有输入、有输出、有自己要干的事。一个函数可以调用另一个函数被调用的函数还可以继续调用下一个函数这样就形成了嵌套调用链。一个典型的例子是main函数调用某个业务函数业务函数内部再调用一个日志函数日志函数内部可能又调用一个格式化函数。看一个最简单的示例#include stdio.h void alpha() { printf(alpha 被调用了\n); } void beta() { printf(beta 开始执行\n); alpha(); printf(beta 执行结束\n); } int main() { beta(); return 0; }运行结果beta 开始执行 alpha 被调用了 beta 执行结束注意执行顺序main调用beta之后beta先打印第一行再调用alphaalpha执行完返回beta再打印最后一行。这个先进入后退出的调用顺序不是C语言特有的——几乎所有的过程式语言都遵循同样的栈模型。在这个例子里函数调用是一层套一层main → beta → alpha。这就是嵌套调用调用路径是单向的、顺序的一层层进去又一层层退出来。很多初学者刚接触这个概念时不太理解返回的含义——被调用的函数执行完了控制权一定会交还给调用它的那个函数然后从调用点继续往下执行而不是直接退出整个程序。理解这一点对后面理解递归至关重要。1.2 嵌套调用和递归的本质区别嵌套调用里每个函数都是别人比如alpha和beta是两个不同函数。而递归呢是同一个函数在内部又调用了自身。再强调一遍递归的本质是嵌套但嵌套的不是不同的函数而是同一个函数的多重实例。这句话要认真体会。举个例子下面这段代码是递归int countdown(int n) { if (n 0) return 0; printf(%d\n, n); return countdown(n - 1); }你可以看到countdown在return语句里调用了countdown自己。同一个函数代码块被反复执行但是每次执行时变量n的值是不同的——第一次是入口参数第二次传给下一层的是n-1。这里有一个非常重要的基础概念函数每次被调用都会在内存的栈区分配一份新的栈帧stack frame用于存放这一层的局部变量、参数和返回地址。我们平时说某个变量是局部变量意思是它归属于某一次特定的函数调用而不是归属于函数代码本身。递归调用同一个函数100次内存里就有100份独立的局部变量n互不干扰。用生活类比嵌套调用像公司流程审批你找部门A的甲甲签完字再找部门B的乙乙签完字再找部门C的丙这是一条串起来的审批链。递归呢像剥洋葱——你剥开一层里面还是一层洋葱剥到最里面那颗核心之后你再一层层把洋葱皮装回去。剥的过程是递装回去的过程是归。把这个逻辑打通之后你再去理解递归就不会只看到一个函数无限调用自己那些画面了。2. 递归思想把大问题拆成同构的小问题2.1 递归的数学基础数学归纳法的编程翻译递归思想的底层其实就是数学归纳法。初中我们证明一个命题对所有正整数成立只需要两步证明n1时命题成立基础步骤假设nk时命题成立证明nk1成立归纳步骤递归的写法完全对应写出问题规模最小时的直接答案基准情形假定子问题能解决利用子问题的结果组装当前问题的结果递归步骤以阶乘为例。阶乘的定义是 n! n × (n-1) × (n-2) × ... × 1。用递推观点看n! n × (n-1)!这个等式里面有自变量n和它的同类型但更小的问题(n-1)!。只要告诉你0! 1你就能计算出任意非负整数的阶乘。这就是递归。写成C语言int factorial(int n) { if (n 0) { return 1; } return n * factorial(n - 1); }很多人看到 return n * factorial(n - 1);脑海里会自动开始无限展开先算factorial(2)再算factorial(1)再算factorial(0)…… 然后整个人就陷入递归的深渊。但在写代码的时候你不需要做这件事。你只需要做两件事确认基准情形正确确认递归步骤的逻辑正确。至于子问题factorial(n-1)到底怎么算出来的把它当黑盒就行。我在教学时经常打个比方你写factorial时不需要知道factorial(n-1)怎么实现你只需要聘用一个能计算阶乘的同事然后告诉他算(n-1)!他从某个地方其实就是同一份代码把答案给你你在它基础上乘上n就行了。递归代码写出来之所以绕就是因为这个同事其实就是你自己。你先无条件信任自己才写得出这段代码。2.2 递归的两个要素一次都不能少每个严谨的递归函数都必须同时拥有两个部分基准情形base case不需要递归就能直接返回结果的分支递归步骤recursive step把当前问题拆成一个或多个规模更小的同类问题两个部分缺一不可。缺了基准情形递归会一直拆永远拆不完最终栈空间耗尽程序崩溃缺了递归步骤函数就只能处理规模最小的情况面对稍微大一点的问题就直接摆烂。这就像电影里反复穿越时间线的剧情没有出口的时间循环是恐怖片没有时间循环的穿越是普通日记。递归步骤里还藏着一个容易被忽略的要求每次递归调用都必须在朝基准情形靠近。一个很常见的问题是有人觉得我调用n-2n-3不也是调用吗但如果基准情形是n0而你每次都n-2从n1开始就永远碰不到0了。所以写递归前花十秒钟想一想下一次调用传进去的参数会不会比现在更接近终止条件如果不会那这个递归就是死循环的变体。补充一点基准情形可能不止一个。比如在判断字符串回文的递归函数里基准情形可能是长度为0和长度为1。在二叉树遍历里基准情形可能是节点为空。设计递归时建议把所有不需要递归就能直接回答的情况列出来确保没有遗漏。3. 终止条件递归的刹车系统也是最容易翻车的环节3.1 终止条件的设计原则总结成三句话要覆盖全部基准情形要能检验输入合法性要让递归参数单调趋向基准。先说说覆盖全部基准情形。以阶乘为例很多人写 if (n 1) return 1;然后调用factorial(0)就会出问题因为0 ! 1递归会变成factorial(-1) → factorial(-2) → 无限展开。虽然很多场景不会有人传0进去但程序设计的严谨性在于函数契约里如果写了非负整数你就要把0这个边界处理掉。用 if (n 1) return 1; 可以把0和1通吃更稳。再说说输入合法性。递归函数的参数在入口就要被检查。比如上面的阶乘如果实参是负数必须在函数最开头直接处理要么返回一个错误标志要么使用断言要么约定调用方只传合法值。我见过一个真实事故案例——某同事写文件路径递归清理函数入口没检查路径是否为空恰巧拿到一个NULL路径递归直接崩了。别觉得这是基础问题线上崩溃往往就是这种小地方。最后说说单调趋向。设计递归时要明确问题规模是什么。在阶乘里是n本身在二叉搜索里是区间长度在链表反转里是已处理的节点数量。递归每一次传递都必须让这个规模严格变小。如果规模不变或变大终止条件永远不可能触发。3.2 递归深度与栈溢出你可能从没见过这么直白的崩溃函数每被调用一次系统就在栈上分配一个新的栈帧。栈帧里存放局部变量、函数参数、返回地址等。递归越深栈上叠的栈帧就越多。操作系统给程序分配的栈空间是有限的最常见的规格是几MB级别。我实测过一个场景一个普通的递归函数在64位系统下每个栈帧大概占用几十字节到一百字节出头取决于局部变量和平台结构大致估算一下几MB的栈空间最多也就支持几万层递归。而你在学习阶段写的朴素递归几千层就可能触发栈溢出Segmentation Fault / Stack overflow。递归不是想多深就多深它是有物理上限的。如何判断自己的递归会不会爆栈我建议养成两个习惯写递归前先估算问题规模。比如深度优先搜索遍历一个深度可能是十万层的树这时候纯递归基本必爆直接考虑迭代或显式栈。给递归函数设计一个深度上限判断如果超过某个阈值及时返回出错信息。在一些工程代码里递归前会检查剩余栈空间虽然不常用但确实是更稳妥的做法。补充一个知识点C语言的递归和编译器的栈帧布局有关。优化选项开启后某些递归可能被优化成循环那是因为编译器通过尾递归优化或者内联等手段调整了栈的消耗但这不是语言保证的行为不能依赖它来处理超深层递归。3.3 终止条件写错的三个典型症状症状一程序运行了一两秒后崩溃而且每次崩溃的位置类似。这通常是无限递归导致栈溢出。排查方法很简单在递归函数第一行打印参数值看看有没有在某个值之间反复横跳。症状二程序能算但结果不对。比如算斐波那契fib(2)返回了1fib(3)返回了2fib(4)突然变成3而不是3这种往往是基准情形写错或者返回值组合错。要仔细对照每个基准返回值。症状三程序性能奇差fib(50)跑不完了。注意如果递归过程中大量重复计算同一个子问题复杂度会爆炸。这个问题我们紧接着讲。4. 经典案例拆解三棵树带我穿过递归入门4.1 阶乘最干净的递归入门代码阶乘递归代码前面已经给出这里不重复。我只说说手工推导一次的方法——这个方法真的值得试一次。假设调用factorial(4)factorial(4) 需要计算 4 × factorial(3)factorial(3) 需要计算 3 × factorial(2)factorial(2) 需要计算 2 × factorial(1)factorial(1) 需要计算 1 × factorial(0)factorial(0) 命中基准情形直接返回1然后开始归factorial(1) 返回 1 × 1 1factorial(2) 返回 2 × 1 2factorial(3) 返回 3 × 2 6factorial(4) 返回 4 × 6 24你在草稿纸上把这个过程画一遍后就能直观看到递展开和归收束两个阶段。注意递阶段只负责调用更深层的函数真正的计算大多数发生在归阶段。分析递归代码时把注意力放在函数返回之后还要做什么非常关键。以factorial为例return n * factorial(n - 1); 中factorial(n-1)返回之后当前层还要做一次乘法。因此每一层的栈帧必须保留直到它的递归调用返回为止。这一点直接对应了前面的栈空间问题——只要父层在子层返回后还有事可做栈帧就不能释放。4.2 斐波那契数列千万别用朴素递归算大数斐波那契数列教科书定义f(0)0f(1)1f(n)f(n-1)f(n-2)。写成C语言long long fib(int n) { if (n 0) return 0; if (n 1) return 1; return fib(n - 1) fib(n - 2); }这段代码正确性没问题跑fib(10)、fib(20)都很快但你试一下fib(50)我保证你怀疑人生。原因在于朴素递归没有任何缓存。求fib(50)会先求fib(49)和fib(48)fib(49)又要再求fib(48)和fib(47)。看到没有——fib(48)被重复计算了。整个调用树是指数膨胀的节点数大约等于斐波那契数本身所以复杂度大约是O(2^n)。实测下来哪怕是很小的n例如n40朴素递归也要算数十亿次函数调用几秒钟起步。n50直接让普通机器卡到无法接受。怎么改两种推荐方式方式一迭代。用两个变量滚动前进时间复杂度O(n)空间O(1)。long long fib_iter(int n) { if (n 0) return 0; long long a 0, b 1; for (int i 2; i n; i) { long long next a b; a b; b next; } return b; }方式二记忆化搜索。用一个数组保存算过的子结果遇到直接返回避免重复计算。long long fib_memo(int n, long long memo[]) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo); return memo[n]; }我从小就被教育递归是最终兵器但过来人说话递归是表达思想的工具性能设计是另一回事。当递归存在大量重叠子问题时请立刻想到记忆化或迭代。4.3 汉诺塔递归思想的巅峰之作汉诺塔的规则有三根柱子A、B、CA上从小到大叠放了n个盘子目标是全部移到C每次只能移动一个盘子且大圆盘不能叠在小圆盘上。你要是用迭代思维去硬模拟每一步n稍大就会疯掉。但用递归几行核心逻辑就能解决void hanoi(int n, char from, char via, char to) { if (n 1) { printf(把盘子 1 从 %c 移到 %c\n, from, to); return; } hanoi(n - 1, from, to, via); printf(把盘子 %d 从 %c 移到 %c\n, n, from, to); hanoi(n - 1, via, from, to); }这里有人会问为什么可以在不理解全过程的情况下直接写递归 因为递归把问题简化成了三步先把上面的n-1个盘子借助目标柱从起始柱整体搬到中间柱递归完成把第n个最大的盘子直接移到目标柱把那n-1个盘子借助起始柱从中间柱整体搬到目标柱递归完成关键洞察上面的n-1个盘子无论具体怎么移动都不影响把最大盘从from移到to这一操作的合法性只要它们不待在to柱上面。所以逻辑上可以整体看待这n-1个盘子——这正是递归的价值所在。汉诺塔的时间复杂度是O(2^n)所以n64的黄金传说靠纯递归计算基本不可能即便每秒移动一个盘子也需要约5849亿年。这也是递归能解决但未必高效的典型教材案例。5. 递归 vs 迭代什么时候该用哪个5.1 两种思路的对比对比维度递归迭代代码可读性高接近数学定义中需要维护循环状态变量空间复杂度O(递归深度)栈占用O(1)通常性能有函数调用开销无额外调用开销适用场景树、图、分治、表达式解析线性遍历、数值累乘累加隐患栈溢出、重复计算状态维护容易出错递归最亮眼的地方是可读性强。人在描述树的每一层往下找时逻辑上就是在递归。如果当前节点为空返回否则先遍历左子树再处理当前节点再遍历右子树——这种中序遍历用递归写出来几乎是自然语言的翻译。你换成迭代去维护栈代码又长又容易出错可读性反差很大。迭代最亮眼的地方是稳定可控。没有栈溢出风险性能损耗也低。一个简单的for循环算阶乘性能、空间、可读性都不差int factorial_iter(int n) { int result 1; for (int i 1; i n; i) { result * i; } return result; }个人建议能用迭代解决的问题优先迭代如果题目考点明确要求考察递归理解再考虑递归。这不是说递归不好而是说工程场景里稳定性优先。真正复杂的数据结构问题树/图遍历大部分情况递归依旧是最优表达此时果断用递归。5.2 尾递归优化递归和迭代的中间地带尾递归是递归的一种特殊形式递归调用是函数的最后一步且函数在递归调用返回后没有任何后续操作。普通阶乘int factorial_normal(int n) { if (n 0) return 1; return n * factorial_normal(n - 1); }尾递归版int factorial_tail(int n, int acc) { if (n 0) { return acc; } return factorial_tail(n - 1, n * acc); } // 入口factorial_tail(5, 1)注意到差别没有普通版本在递归返回后还要做n乘以结果的操作尾递归版本把当前层已经算好的部分结果acc直接传给下一层递归返回后什么都不用做。因此如果编译器做了尾递归优化当前栈帧可以被回收递归深度就不会无限增长了。C语言标准并没有强制要求编译器做尾递归优化。GCC开优化等级时一般能处理简单的尾递归但不保证所有情况都能优化。所以把尾递归当作一种编码风格和自控思想来学但不能完全依赖编译器。实际工程中当递归深度实在大时我更喜欢显式栈循环在堆上模拟递归调用栈。这样既保留了递归的表达思路又不会发生栈溢出。代价是代码稍微繁琐一些。比如把遍历二叉树递归版改写成显式栈版void traverse_iter(struct Node *root) { struct Node *stack[1024]; int top -1; struct Node *cur root; while (cur ! NULL || top 0) { while (cur ! NULL) { stack[top] cur; cur cur-left; } cur stack[top--]; printf(%d\n, cur-value); cur cur-right; } }这段代码和递归版行为完全一致但栈空间由我们自己控制避免了系统栈溢出。6. 常见问题与调试技巧递归翻车自救指南6.1 排查递归时我常用的五个方法方法一打印进出顺序。在递归函数入口打印 enter: n%d在出口或递归调用返回后打印 exit: n%d立刻能看到调用树的全貌。我之前调试一个递归走迷宫的程序程序一直不返回本来以为是死循环加了两行打印才发现原来递归深度到了几千层基准情形在前面被漏掉了。方法二把递归参数当哨兵。递归每进入一层参数必须比上一层更接近终止条件。如果发现参数在两个值之间反复那一定是递归步骤的数学关系出了问题。方法三小规模输入先行。别直接测试n100先测n0、1、2、3。通过n2的推导验证基准情形与递归步骤的组合是否正确。这个方法几乎能秒杀80%的入门级Bug。方法四手绘调用树。对一些症状不明显的逻辑错误纸笔推演10步以内基本能发现错误出在哪一层特别适合汉诺塔这类带多个递归调用的场景。方法五用调试器设置递归深度条件断点。GDB支持条件断点可以只观察深度为10的调用点避免误入成百上千层递归调试效率会高很多。6.2 递归的隐藏坑全局变量与静态变量用全局变量或static变量存储递归过程中的累计结果是一个很容易出错的设计。比如你写一个递归累加把结果存在全局变量sum里函数每层sum n这段代码第一次运行没问题第二次调用时sum没有清零结果就错了。堆与栈之外的全局状态是所有递归层共享的。递归天然适合用返回值传递每层计算结果尽量不要依赖外部可变状态。如果一定要用记得在递归开始前做状态初始化。再补充一个深坑返回值类型。计算阶乘时很多教程用int结果n13就已经超出32位int范围了。这个问题在递归里会被放大因为递归的每一层返回值都会参与运算。建议对可能增长很快的数列阶乘、斐波那契直接用long long还不放心就考虑大数处理方案。虽然这是老生常谈但每次见到都是同一个坑。6.3 现场实战一个递归写崩了的例子我模拟一个常见错误求某个数的二进制中1的个数有人写成int count_ones(int n) { if (n 0) return 0; return (n 1) count_ones(n 1); }乍看没问题。但如果调用count_ones(-5)这个代码就永远不会停。因为负数右移最高位补1-5 1还是负数不向0靠近。这就是典型的终止条件没有覆盖非法输入。修正方式在函数开头把负数转成正数处理注意绝对值溢出这个细节或者声明函数只接收非负参数。这个例子在面试里经常出现不管是实习生还是资深工程师都可能翻车。7. 关于递归的一点个人体会我这些年带过不少学C语言的新人发现他们对递归最大的心理障碍不是不会写而是不敢信。跨过这个心理坎的方法很粗暴强制自己先写一个能用递归解决的问题比如阶乘、斐波那契写完再强制自己推演一遍。确实有同学推演一遍就通透了也有同学推演三遍才明白。没关系递归这个东西一旦开了窍后面再看树的遍历、快排、回溯算法都会顺利很多。最后再分享一个小技巧如果下次你看到一个递归函数看不懂不要从头读到尾动笔把它的基准情形和递归步骤拆开标注什么时候停怎么变小然后找一个极小的输入比如n2跟着走进一层——几乎一次就能看懂。这篇就先到这里下一篇我们继续沿着C语言100篇的路线往更硬核的数据结构和算法方向走。如果你也在学递归欢迎在评论区聊聊你是从哪道题开始突然想通的。