提到函数递归不少刚开始学C语言的朋友都会有同一种感觉概念听得懂函数自己调用自己像两面镜子对着照、一层层套下去可一旦自己上手写代码不是死循环就是结果完全不对。如果你也有这种困惑问题多半不在你而在大多数资料都把递归讲成了“套娃”却没有讲清楚递归在运行时真正发生的事。这篇笔记我想换个角度从函数调用栈讲到递归的写法、代价、调试再聊到什么时候值得用递归。适合学C语言卡在递归这一关的同学也适合工作中被递归Bug折腾过、想系统补一补这块的开发者。1. 先把递归的“物理基础”搞清楚调用栈与栈帧1.1 一次普通函数调用在底层发生了什么想理解递归先得理解一次普通的函数调用。C语言里每当函数A调用函数B运行时都会在一块叫“调用栈”call stack的内存区域里为这次调用分配一段“栈帧”stack frame。栈帧里保存着这次调用的局部变量、参数值以及一个极其重要的东西返回地址。返回地址告诉CPU当前这个函数执行完毕后该跳回哪里继续干活。调用过程的规则是“后进先出”A的栈帧先压上去接着B的栈帧压到A上面B执行完B的栈帧弹出控制权回到A继续执行。等A也执行完A的栈帧再弹出。整个过程跟一摞盘子一模一样你只能往最上面放盘子也只能从最上面取盘子。1.2 函数递归就是不停向栈里压自己的栈帧当函数f调用它自己时运行时的逻辑和上面完全一致唯一的区别是这次调用的是同一个函数且参数往往变了。第一次调用f的栈帧压栈之后函数体里又触发了一次对f的调用于是第二个f的栈帧压到第一个上面如果第二次调用里又触发一次就再压第三帧……直到某个条件满足不再触发新调用函数才开始逐层返回栈帧逐层弹出。我看过一句很准的话递归不是一个“循环套娃”而是一连串普通的函数调用只不过每次调用的是同一个函数。你把运行时这个过程想明白了递归最大的神秘感就消失了。为什么很多人能看懂别人的递归、自己却写不出来就是因为他们只从“语法层”看问题从没走到“栈帧层”去想问题。1.3 写任何递归前先问自己三个问题我在跟人讲递归的时候用的是一套“三问法”比直接对着题目憋代码有效得多子问题当前规模为n的问题能不能拆成一个或几个规模更小、但结构完全相同的问题最小规模当n小到某个程度通常是0或1时答案是不是可以直接给出不用再拆组合子问题的结果拿到之后怎么把它们拼成原问题的答案如果这三个问题都能回答递归函数的骨架就出来了。很多人说“我看得懂递归但写不出”多半就是跳过了这三问。你拿任何一道递归题来先别管代码把这三句话用自然语言写一遍再翻译成C代码会顺畅得多。2. 三个经典入门案例的代码拆解这一章我用三个经典的题目演示上面的方法阶乘、斐波那契数列、汉诺塔。前两个用来把基本功打牢第三个用来训练“只关心子问题不关心中间过程”的整体思维。2.1 阶乘最朴素的递推关系阶乘的定义是n! n × (n-1)!并且规定0! 1。这个定义本身就是递归的算n的阶乘需要先算(n-1)的阶乘。C代码非常短int factorial(int n) { if (n 1) { return 1; } return n * factorial(n - 1); }对照三问法子问题是factorial(n - 1)最小规模是n为0或1时直接返回1组合方式是子问题的结果乘上n。三步齐了代码自然就写出来。这里我想强调一个很多人不注意的细节终止条件我写的是n 1而不是n 1。如果把条件写成n 1那么调用factorial(0)时0不等于1会继续走递归调用factorial(-1)、factorial(-2)……一路往负数冲下去直到栈溢出崩溃。边界条件宁可写宽一点也不要写窄这是递归里保命的好习惯。2.2 斐波那契教科书里的性能大坑斐波那契数列的定义是fib(0)0、fib(1)1、fib(n)fib(n-1)fib(n-2)。代码同样很简洁long long fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); }但这段代码的性能离谱。fib(30)还行到fib(45)已经明显卡顿fib(50)基本等不出结果。原因是它重复计算太严重求fib(50)需要先算fib(49)和fib(48)算fib(49)又需要fib(48)和fib(47)。注意同一个fib(48)在两条路径里都会被完整地重算一遍。这种重复一层层放大调用次数直接变成指数级增长。有同学会问递归每一层的参数不是都不一样吗怎么会重复你画一张调用树就明白了fib(5)调用fib(4)和fib(3)fib(4)又调用fib(3)和fib(2)。两个分支都要算fib(3)但程序不知道前面算过只会老老实实再算一遍。递归的简洁不等于高效当逻辑里出现“同一个子问题被多个分支共享”时要立刻警惕性能问题。解决方案我放到第3章这里先记住结论。2.3 汉诺塔递归思维的最佳训练汉诺塔的规则是有三根柱子A、B、C要把n个盘子从A移到C每次只能移动一个盘子而且任何时候大盘子不能压在小盘子上。这题用迭代硬写非常痛苦但用递归只需要想三步先把上面n-1个盘子从A移到B借道C把最底下的大盘子从A直接移到C再把B上的n-1个盘子移到C借道A。关键点移动n-1个盘子跟你原来移动n个盘子是同一类问题只是规模减一。代码void hanoi(int n, char from, char aux, char to) { if (n 1) { printf(%c - %c\n, from, to); return; } hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); hanoi(n - 1, aux, from, to); }为什么说它是训练递归思维的最佳题目因为汉诺塔没法靠“模拟套娃”的笨办法写你只能信任那个“大问题转小问题”的思路你不必关心那n-1个盘子内部究竟怎么移动的细节只要确认子问题规模更小、边界条件正确函数就会替你完成一切。这种“信任”正是递归思维的核心。很多人写递归时总想控制每一层的细节结果越想越乱汉诺塔能帮你改掉这个毛病。3. 递归的代价栈溢出、重复计算与尾递归优化递归很优雅但C语言里的递归不总是免费的午餐。这一章我专门讲代价——不少项目里出现的崩溃其实是递归引来的。3.1 每一次调用都要吃一块栈空间每调用一次函数就要压一个栈帧。栈帧多大跟参数个数、局部变量数量有关通常从几十字节到几百字节不等。如果递归深度很大栈空间很快就吃紧了。Linux下默认的栈大小常见是8MB左右你可以用ulimit -s查看。假设每层栈帧100字节递归十万层就差不多要10MB——栈直接爆掉程序段错误崩溃。所以写递归前先估算深度这个函数的递归深度会不会跟输入规模成正比如果会且规模可能很大就要小心。典型的反例是深度优先搜索路径遍历递归深度等于节点数量几万个节点的树就能把栈吃干净。而前面斐波那契虽然调用总数爆炸递归深度其实只有n左右倒不至于栈溢出但性能已经无法接受了。两类问题不一样排查方向也不一样。3.2 斐波那契的救星记忆化解决重复子问题最标准的技术叫“记忆化”memoization把已经算过的结果存起来下次直接查表不再重算。C实现如下long long memo[100]; void init_memo() { for (int i 0; i 100; i) { memo[i] -1; } } long long fib_memo(int n) { if (n 1) { return n; } if (memo[n] ! -1) { return memo[n]; } memo[n] fib_memo(n - 1) fib_memo(n - 2); return memo[n]; }调用前先执行init_memo()把数组初始化成-1因为斐波那契的值永远不会是负数-1正好表示“还没算过”。这样每个n最多算一次fib(50)也能瞬间出结果计算量从指数级降到线性级。在我看来记忆化是递归最重要的搭档动态规划里的“递归 查表”思路比很多人想象的从底向上迭代更容易写对也更接近人类思考的自然方式。3.3 尾递归到底能不能信尾递归是指递归调用是函数里最后一个动作并且函数把递归调用的结果直接返回不再做任何加工。典型写法是把“累计值”作为额外参数往下传比如阶乘的尾递归版int factorial_tail(int n, int acc) { if (n 1) { return acc; } return factorial_tail(n - 1, n * acc); }调用时写作factorial_tail(5, 1)acc从1开始每层乘上当前的n往下传。尾递归的妙处在于编译器在开启优化的情况下可以把这种调用改写成循环复用同一个栈帧递归深度就不再消耗栈空间。但有两个前提第一编译器必须开优化比如GCC加-O2不开优化就白搭第二C语言标准并不强制编译器做这种优化不同编译器表现不一样。我的建议是在C里如果递归深度可能很大优先写迭代或者用显式的栈数据结构模拟递归尾递归可以了解、可以在性能要求高的地方试试但别把它当成万能保障。我见过不止一次有人写了尾递归却忘了开优化线上跑着跑着照样栈溢出。4. 调试递归Bug栈溢出与“算错但不崩”的排查思路写递归时最难受的两类错误一种是直接栈溢出崩溃一种是不崩但结果不对。这两类的排查思路很不一样。4.1 递归终止不了的排查先打印再看调用栈栈溢出的根源几乎都是“递归没有在正确的位置停下来”。最常见的是边界条件写错了比如阶乘用n 1当终止条件传入0就会一路往负数递归。另一种是参数变化方向不对递归每深入一层参数必须朝边界逼近如果调用自己时参数不变甚至变大就永远到不了终点。排查时我的第一招是加打印把函数每次进入时的参数输出来int factorial(int n) { printf(enter factorial, n %d\n, n); ... }看输出里参数的变化趋势。如果参数一路涨到天文数字或者一路跌到负数那问题基本锁定了要么边界写错要么递归调用方向写错。如果打印信息太多刷屏就改用调试器。我常用gdb在递归函数入口打断点崩溃后执行btbacktrace一组完整的调用层次立刻展示出来从栈顶到栈底全是同一个函数名只是参数不同——肉眼就能看出哪儿不对。4.2 返回值传丢了一个return引发的离奇结果还有一些递归Bug很像“玄学”函数不崩溃算出的结果却完全不对。最常见的原因是非void的递归函数里漏写return。很多新手写斐波那契时递归那行写成了fib(n - 1) fib(n - 2)而不带return于是本层函数执行到末尾时没有返回值这属于未定义行为程序拿到的就是一个随机垃圾值。判断方法很简单凡是函数声明了返回类型它的每一条可能结束执行的路径上都必须有return而且这个return的值必须是你真正想送回上一层的那个值。我检查递归返回值有个习惯从最内层往外推演先假设最内层返回了一个确定值再想上一层拿到这个值后做了什么、又往上传了什么。中间任何一步少了return最终结果铁定错。用纸笔把这个链条推一遍比瞪着眼睛看代码高效得多。4.3 小规模用例把递归过程完整走一遍调递归还有一招特别好用别一上来就测n50先测n2或n3用纸笔画出完整的调用树再跟程序真实输出对比。比如factorial(3)完整的调用顺序是factorial(3)调factorial(2)、factorial(2)调factorial(1)然后factorial(1)返回1、factorial(2)返回2、factorial(3)返回6。把这个小过程走通复杂逻辑不过是同一套规律的放大。我平常调任何递归函数第一步永远是找一组极小数据跑通路径让代码把“骨架”露出来再放大规模验证优化和边界。5. 递归的使用边界什么时候该用什么时候别硬用递归有栈溢出风险、有性能损耗为什么还要学它、还要用它因为有些问题用递归就是比迭代清晰得多而且递归能帮你建立算法直觉。5.1 天生适合递归的场景凡符合“一个大问题能拆成同样结构的几个小问题”的场景递归几乎都是最自然的第一反应。典型代表是二叉树的遍历。“前序遍历”的定义就是访问根节点、递归遍历左子树、递归遍历右子树直接翻译成C代码void preorder(struct TreeNode *node) { if (node NULL) { return; } visit(node); preorder(node-left); preorder(node-right); }同功能用迭代写得自己维护一个栈不断入栈出栈代码长一倍以上还容易写错。树本身就是递归定义的数据结构用递归处理它属于“顺水推舟”。链表反转、目录树遍历、JSON树结构的处理也类似碰到这些我都推荐优先递归。5.2 别硬用递归的场景反过来如果一个问题用两层for循环就能解决就不要递归。比如数组求和、逐行扫描矩阵、找数组最大值用迭代几行结束递归既更慢、更耗栈、也没让代码变清晰属于纯粹的滥用。我印象很深的是帮某位同学排查代码他把一维数组求最大值写成了递归n上万之后程序莫名崩溃改成循环后三行代码解决问题。判断标准很朴素递归有没有让代码更清晰如果没有还增加了风险那就是用错了地方。5.3 递归与迭代的对照关系不少初学者觉得递归和迭代是互相对立的其实它们描述的是同一类计算过程。可以这样对照对比维度递归迭代代码可读性遇到天然递归结构时更清晰简单问题时更直观内存开销每次调用占用栈帧通常只需固定几个变量风险可能栈溢出循环条件错可能死循环典型应用树的遍历、分治、回溯数组处理、数值累加、状态机很多算法既可以用递归写也可以用迭代写比如归并排序的分治思路可以用递归表达也可以用循环加显式栈模拟。关键不在于“谁高级”而在于哪个版本更容易被团队里的其他人读懂和维护。5.4 理解递归对读别人代码也很有用退一步说就算你以后写C语言很少主动用递归也绕不开读递归代码这件事。很多开源项目、算法教科书里快速排序、归并排序、各种树的算法核心实现经常是递归。搞懂函数调用栈之后你读这类代码时就不会被“一层套一层”吓退你会习惯性地去分析这函数在某次调用中怎么压栈、怎么返回子问题在哪里拆分。这种视角比记住某个具体语法有价值得多。我以前读某项目里的二分查找递归实现时就靠“三个问题”拆解它的结构边界条件是什么、子问题是什么、返回值怎么组合。看懂之后改bug都顺手很多。学习递归最大的收获其实不是“会用递归写阶乘”而是养成一种把大问题拆成小问题的思维习惯。这个习惯在算法设计、系统设计里都会反复用到。我个人的体会是递归写不好的人往往不是智商问题而是缺少一套系统拆解问题的方法。三问法加小规模推演是我见过最有效的起步方式。建议你亲手把阶乘、斐波那契、汉诺塔各写一遍再用gdb的bt命令观察一次真实的递归栈感受一下每一层栈帧的压入和弹出。写过几次之后递归对你来说就不再是“套娃”而是一个用得顺手的工具了。