学C语言的时候函数递归这四个字曾经让我在图书馆里闷了一个下午。周围人都在说汉诺塔多经典、青蛙跳台阶多巧妙可我盯着代码就是不知道它凭什么能算出正确答案。后来我把递归调用栈一层层画在草稿纸上才突然明白递归不是算法竞赛的炫技也不是C语言考试拿来卡人的偏题它就是“函数调用自己”这么简单的一件事只是很多人没把运行时发生的事看清楚。这篇文章就按我自己的理解路径来写先搞懂调用栈再学会写递归函数然后用汉诺塔和青蛙跳台阶这两个经典题目把递归的思想和坑都过一遍。适合已经会写函数、但看到递归就发怵的C语言学习者也适合要准备机考、想系统过一遍递归套路的人。1. 递归卡住的人大概率没见过调用栈的样子1.1 用阶乘把递归调用慢动作重放一遍好多讲递归的文章一上来就丢公式factorial(n) n * factorial(n - 1)。公式背得再熟心里还是会犯嘀咕这函数怎么算着算着就自己调用自己了它凭什么不会乱套我建议你暂时忘掉公式跟着代码走一遍计算机的实际执行过程。先看最常见的阶乘递归实现#include stdio.h int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); } int main() { int result factorial(4); printf(%d\n, result); return 0; }main调用factorial(4)这是第一次调用。n4不满足n 1所以函数走到return 4 * factorial(3);。问题来了要算出这个 return 的值得先知道factorial(3)是多少。于是程序不是立刻返回而是把当前这一“层”的执行现场保存下来然后去调factorial(3)。接下来的流程可以这样看当前调用它要做什么发生了什么factorial(4)计算4 * factorial(3)卡住了先等 factorial(3) 返回factorial(3)计算3 * factorial(2)卡住了先等 factorial(2) 返回factorial(2)计算2 * factorial(1)卡住了先等 factorial(1) 返回factorial(1)直接返回 1终于触底开始往回给答案再从返回方向看一遍factorial(1)返回 1factorial(2)拿到 1 后计算2 * 1返回 2factorial(3)拿到 2 后计算3 * 2返回 6factorial(4)拿到 6 后计算4 * 6返回 24。整个过程就是“先一层层往下递再一层层往上归”这也是“递归”这个名字的由来。很多人卡住是因为脑子里总想同时维护好几层计算。其实计算机根本不需要“同时想”它只需要把每一层挂起等下一层的结果回来再继续。这个“挂起”靠的就是系统栈。1.2 递归与普通函数调用并没有本质区别只是恰好调用了自己你平时肯定写过这样的调用链main调用funcAfuncA调用funcB。funcB执行完后回到funcA继续funcA执行完后回到main继续。每进入一个函数系统就在内存的栈区分配一小块空间用来保存这个函数的参数、局部变量和返回地址这块空间叫栈帧。递归函数只是在调用链上反复出现同一个函数名而已。factorial(4)调factorial(3)和factorial(4)调factorial_other(3)在机制上没有任何区别。每次调用都会生成一个新的栈帧里面的n互不干扰。你在factorial(4)里看到的n4不会因为下面有个factorial(3)就变成 3两个n只是名字碰巧一样实际是不同栈帧里的不同变量。栈是先进后出的。每发生一次函数调用就往栈顶压一个栈帧每返回一次就弹出一个栈帧。如果递归函数没有终止条件函数就会一直调用自己栈帧越叠越多直到栈空间耗尽程序崩溃。这个错误叫栈溢出英文就是 Stack Overflow。有不少人问过我为什么编译器不在递归写错的时候直接报错因为编译器静态分析很难判断某个递归会不会无限执行所以它选择不拦你只会在运行时用崩溃告诉你“栈爆了”。理解了这一点递归最大的神秘感就消失了。剩下的问题是什么样的递归函数才是正确的这就需要开始聊递归的骨架。2. 递归的骨架终止条件、递推关系、递归信任2.1 终止条件写在函数第一行像安全检查一样几乎每个合格的递归函数都长着同一副骨架返回值类型 函数名(参数) { if (最小情况成立) { return 直接可算的结果; } // 把问题缩小成更小规模的同类问题 return 需要和本身函数组合的表达式; }其中的“最小情况成立”就是终止条件也叫递归出口。它回答的问题是问题小到什么程度小到不用再继续调用自己我就能直接给答案factorial里最小情况是n 1直接返回 1因为 0! 和 1! 都是 1。如果你不写这个条件写成下面这样int bad(int n) { return bad(n - 1); }n会从 10 变成 9再变成 8……一路减到负几千、负几万永远没有一个“不用递归”的出口。每次调用都压栈最终结果就是栈空间被塞满程序段错误退出。所以写递归的第一习惯是先问自己参数取到什么值时我能一口说出答案把这个情况写在函数第一行。这不是风格问题是正确性问题。有人可能见过某些递归写法不把终止条件写在第一行而是写在中间或最后。不推荐初学者这么做。放在第一行你每次看代码时都能立刻确认递归有出口调试的时候也方便在入口打日志观察。2.2 递归信任不要试图在脑子里展开每一层新手写递归最容易踩的心态坑就是想手动模拟完整调用链f(n)依赖f(n-1)f(n-1)依赖f(n-2)……一路模拟到出口再一路代回来。这个过程对于 n4 还能忍n10 就开始头晕n30 基本就放弃了。正确做法是“递归信任”。假设更小规模的问题已经由一个“神秘函数”帮你算好了你现在只需要当前这一层怎么把结果拼出来。举个例子用递归求数组前 n 个元素的最大值int max(int arr[], int n) { if (n 1) return arr[0]; int sub_max max(arr, n - 1); return arr[n - 1] sub_max ? arr[n - 1] : sub_max; }函数语义是“返回 arr 前 n 个元素中的最大值”。当 n1最大就是arr[0]这是终止条件。当 n1我先把前 n-1 个元素的最大值交给max(arr, n - 1)去算它返回的结果存放在sub_max里。然后当前层只需要回答一个问题arr[n-1]和sub_max谁更大谁大谁就是前 n 个元素的最大值。写这个函数的时候你不需要关心max(arr, n - 1)内部到底走了多少步。你只需要相信两件事第一它的函数语义是“返回前 n-1 个元素的最大值”第二由于参数变小了它不会陷入无限递归。这两点成立递归信任就成立。怎么验证拿小例子手推。比如arr {3, 7, 2}n3。max(arr, 3)调用max(arr, 2)max(arr, 2)调用max(arr, 1)返回 3于是max(arr, 2)比较arr[1]7和 3返回 7接着max(arr, 3)比较arr[2]2和 7返回 7。整个过程和上一节阶乘的分析方式完全一致但你写的时候只用关注“当前层怎么组合”。2.3 新手写递归最常见的三个错误忘写出口、参数没缩小、盲目展开调用树把这三个问题单独拎出来说是因为我见过太多人在上面翻车。第一个错误是忘写终止条件前面已经说过了。第二个错误是递归调用时参数没有向“最小情况”靠近。比如写max(arr, n)时不小心调用了max(arr, n 1)参数反而变大那么递归永远走不到出口。参数必须一步一步逼近终止条件。第三个错误是试图在脑子里展开完整调用树把自己绕晕。实际上写递归时只需要关心两层当前层和下一层。当前层负责把下一层的结果拼成最终结果下一层的正确性由“递归信任”兜底。如果你想验证用 n2 或 n3 这种小规模数据去跑比在脑子里死磕一万层有用得多。3. 汉诺塔递归思想最完美的教学案例3.1 汉诺塔的规则与“把 n-1 个盘子整体搬家”的拆法汉诺塔问题是这样的有三根柱子A、B、CA 柱上从上到下依次叠着 n 个盘子的“金字塔”小盘子在上大盘子在下。目标是把所有盘子从 A 移到 C每次只能移动一个盘子而且任何时候大盘子都不能压在小盘子上面B 柱可以临时借用来放盘子。先看最简单的情况。n1只有一个盘子直接从 A 移到 C 就完事。n2两个盘子步骤是三步小盘 A 移到 B大盘 A 移到 C小盘 B 移到 C。n3 的时候如果硬着头皮手动模拟也能做但要花 7 步。可如果你直接把前面两步的“模式”抽象一下规律就出来了。要把 n 个盘子从 A 移到 C可以拆成三步把上面的 n-1 个盘子当作一个整体从 A 移到 B借助 C。把最底下那个最大的盘子从 A 移到 C。再把 B 上的 n-1 个盘子移到 C借助 A。注意第 1 步和第 3 步本质上都是在做“移动 n-1 个盘子”这件事只不过起点、终点、辅助柱的角色换了。移动 n 个盘子的问题就这样被拆成了两个移动 n-1 个盘子的问题。这不正是递归吗3.2 完整C代码和n3的输出逐行解读汉诺塔的递归实现比很多人想象中短得多#include stdio.h void hanoi(int n, char from, char to, char aux) { if (n 1) { printf(move disk 1 from %c to %c\n, from, to); return; } hanoi(n - 1, from, aux, to); printf(move disk %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, to, from); } int main() { hanoi(3, A, C, B); return 0; }函数签名里的四个参数分别是当前要移动几个盘子、起点柱、终点柱、辅助柱。在main里调用hanoi(3, A, C, B)意思是把 3 个盘子从 A 移到 CB 作为辅助。这个代码的输出是move disk 1 from A to C move disk 2 from A to B move disk 1 from C to B move disk 3 from A to C move disk 1 from B to A move disk 2 from B to C move disk 1 from A to C我们对照前面“三步拆法”看前两行加第三行对应“把上面 2 个盘子从 A 移到 B借助 C”第四行是“最大的第 3 号盘子从 A 移到 C”后三行对应“把 B 上的 2 个盘子移到 C借助 A”。整个递归结构一目了然。很多第一次看这个代码的人会疑惑为什么递归调用前面有一行printf后面也有一行printf因为移动 n 个盘子被拆成了“移动 n-1 个盘子、移动第 n 个盘子、再移动 n-1 个盘子”中间的printf就是“移动第 n 个盘子”这一步两头则是对两个子问题的递归调用。3.3 移动次数、递推公式和指数爆炸汉诺塔的移动次数有很多种推法递归角度最自然。设T(n)为把 n 个盘子从一根柱子移到另一根柱子所需的最少移动次数。根据三步拆法移动上面 n-1 个盘子需要T(n-1)次。移动最底下的大盘子需要 1 次。再把 n-1 个盘子移过去又需要T(n-1)次。所以递推关系是T(n) 2 * T(n-1) 1并且T(1) 1。把这个关系展开T(1) 1T(2) 2 * 1 1 3T(3) 2 * 3 1 7T(4) 2 * 7 1 15很容易看出规律T(n) 2^n - 1。这个式子的增长速度非常吓人n移动次数112337101023201048575301073741823401099511627775n40 时已经是万亿级别普通计算机根本跑不完。所以汉诺塔递归代码写出来主要是为了理解递归不是真的让你跑一个超大 n 去数输出行数。看到指数增长时要能意识到“这个问题的规模不可随意扩大”这是递归学习中很重要的一课。3.4 最容易写错的参数顺序以及怎么用“角色”来理解汉诺塔代码本身短但很多初学者会在这里卡上很久为什么第一处递归调用是hanoi(n - 1, from, aux, to)第二处是hanoi(n - 1, aux, to, from)把顺序写反程序会立刻给出完全错误的移动步骤。关键不在于死记字母顺序而在于理解每个位置的“角色”。参数名字本身不重要重要的是语义这次递归调用要把盘子从哪里移动到哪里辅助柱是哪根。第一处调用的任务是“把 n-1 个盘子从起点柱移到辅助柱”。所以源柱是from目标柱不是最终的to而是aux剩下的to成为辅助柱。于是写hanoi(n - 1, from, aux, to)。第二处调用的任务是“再把 n-1 个盘子从辅助柱移到终点柱”。这次源柱是aux目标柱是to剩下的from成为辅助柱。于是写hanoi(n - 1, aux, to, from)。我自己的经验是不要在脑子里死磕“A、B、C 三个字母”而是把参数想成三个角色从哪来、到哪去、借谁当辅助。递归每下降一层角色就重新分配一次。画出 n3 的递归树你会看到每一层的from/to/aux都不一样但逻辑完全一致。这个角色化思维比背代码有用得多。4. 青蛙跳台阶递推关系是灵魂递归只是其中一种实现4.1 问题原题与 f(n) f(n-1) f(n-2) 的推导青蛙跳台阶是递归练习题里的另一位常客。题目通常是这样一只青蛙一次可以跳上 1 级台阶也可以一次跳上 2 级台阶。请问它跳上 n 级台阶一共有多少种不同的跳法这里的“不同的跳法”指的是跳法的组合跟顺序有关。比如 n3 时可以 111可以 12可以 21一共 3 种。用递归的思路拆解青蛙想跳到第 n 级台阶它的最后一步只有两种可能。要么是从第 n-1 级跳 1 级上来要么是从第 n-2 级跳 2 级上来。所以跳到第 n 级的总跳法等于跳到第 n-1 级的跳法加上跳到第 n-2 级的跳法。写成公式f(n) f(n-1) f(n-2)。边界条件也很直观f(1) 1因为只有 1 级台阶时只有一种跳法f(2) 2因为可以一次跳 2 级也可以分两次各跳 1 级。至于f(0)有的资料喜欢定义成 1只是为了公式统一好看我们平时写代码不需要用到它直接用f(1)和f(2)当边界更不容易出错。把前面几个值列出来f(1)1, f(2)2, f(3)3, f(4)5, f(5)8, f(6)13。你马上会发现这就是斐波那契数列的变种只不过经典的斐波那契是 1、1、2、3、5、8……青蛙跳台阶把第二个 1 换成了 2。4.2 最直观递归代码和它致命的重复计算看到递推关系之后立刻写递归代码是很自然的int frog(int n) { if (n 1) return 1; if (n 2) return 2; return frog(n - 1) frog(n - 2); }这个代码逻辑上完全正确n5 时也能算出 8。但如果你拿它去跑很大的 n比如 n50程序会卡到让你怀疑人生。原因在于重复计算。设frog(6)。它需要frog(5)和frog(4)。frog(5)又需要frog(4)和frog(3)。注意这里的frog(4)被算了两次第一次是frog(6)直接要的第二次是frog(5)要的。再往下frog(3)会被算更多次。整个计算量不是线性增长的而是近似指数级增长的。n30 时递归调用次数已经能到百万级别n50 时基本就是天文数字。这给我们的教训很重要递归公式漂亮不代表递归实现一定高效。能不能用递归还要看会不会产生大量重复的子问题。4.3 记忆化递归与迭代优化考试和面试的两种答法既然问题出在重复计算解决方案也很直接把已经算过的结果存起来下次直接用。第一种做法是记忆化递归。在函数外面开一个数组初始值设 0表示还没算过算完一个frog(n)就存进数组long long memo[100] {0}; long long frog_memo(int n) { if (n 1) return 1; if (n 2) return 2; if (memo[n] 0) return memo[n]; memo[n] frog_memo(n - 1) frog_memo(n - 2); return memo[n]; }这样每个frog_memo(n)只真正递归计算一次后面的调用直接查数组时间复杂度降为 O(n)。第二种做法更简单干脆不用递归用三个变量滚动迭代long long frog_iter(int n) { if (n 1) return 1; if (n 2) return 2; long long a 1, b 2, c; for (int i 3; i n; i) { c a b; a b; b c; } return b; }变量a表示f(i-2)b表示f(i-1)每轮用c算出f(i)然后整体往后挪。循环结束b就是f(n)。这段代码连数组都不需要空间复杂度 O(1)。所以青蛙跳台阶这道题真正的价值不只是让你练习写出frog(n)的递归而是让你明白“递推关系”和“递归实现”是两回事。递推关系可以用递归写出来但遇到指数级重复计算时要么记忆化要么转成迭代。考试中如果题目只要求“用递归实现”写最前面的版本就够了如果题目额外要求“运行效率高”你就得写成记忆化或迭代。5. 递归的进阶边界什么时候用它什么时候尽早收手5.1 递归适合什么场景不适合什么场景学完汉诺塔和青蛙跳台阶很容易产生一个错觉递归无所不能。但实际上递归更像一把锋利的刀用对地方很顺手用错地方容易伤人。递归适合的场景通常是问题天然具有“自相似”结构一个大问题能拆成几个更小的同类问题而且每个小问题的解能组合成大问题的解。最典型的是树形结构二叉树的先序、中序、后序遍历求树的深度判断两棵树是否相同几乎都是递归的舒适区。分治算法也很典型比如归并排序、快速排序本质上都是把数组拆成两半分别排序再合并。链表的某些操作也适合比如递归反转链表、递归合并两个有序链表。不适合递归的场景也很明显斐波那契那种“同一子问题被反复计算”的纯递推问题、深度很深且层级不确定的问题、以及性能敏感要求栈空间可控的问题。在这些场景下递归代码即使写出来了也往往是低效或危险的。用一个简单的判断标准如果一个问题你能轻松写出迭代循环并且不会因此损失可读性那就优先写迭代如果迭代需要自己维护模拟栈或者逻辑绕到看不明白而递归能清晰表达问题本身的结构那就放心用递归。5.2 尾递归、栈深度与实际开发中的隐形成本说到递归的“危险”最典型的就是栈溢出。函数每调用一次就占用一份栈帧普通栈帧可能只有几十字节但架不住层数多。Linux 默认栈空间通常是 8MB如果代码里递归层数达到几十万层栈空间很快就会耗尽。有些读者可能听说过“尾递归优化”。尾递归指的是递归调用是函数体里的最后一条语句并且返回值直接传给上一层不需要再做额外运算。以阶乘为例可以改写成int factorial_tail(int n, int acc) { if (n 1) return acc; return factorial_tail(n - 1, acc * n); }这里acc是累积结果每次递归前先把当前结果乘进去。第一版factorial是return n * factorial(n - 1)递归返回后还要再乘一个n而尾递归版本return factorial_tail(...)不需要再做任何运算直接返回子调用的结果。理论上编译器可以复用当前栈帧把尾递归优化成循环从而避免栈增长。但这里有个坑C 语言标准并不强制要求编译器做尾递归优化。GCC 在-O2下通常能优化简单的尾递归但依赖编译器优化是很危险的做法。你在课程作业或考试中写代码千万不要默认尾递归一定会被优化。一旦编译器没有优化尾递归和普通递归一样会爆栈。实际项目中如果预计递归深度可能达到数千甚至数万我会先算一笔账栈空间通常 8MB每个栈帧大约 40-80 字节乐观估计能支持 10 万层以上。但函数参数越多、局部变量越多栈帧越大能支持的递归深度就越小。稳妥的做法是设置递归深度上限或者在递归进入前检查边界条件防止异常输入导致无限递归。5.3 实战经验遇到递归题快速写对的五步法刷题或者考试时拿到一道递归题我习惯按这五步来基本不会卡壳第一步明确函数语义。写清楚这个函数接收什么参数、返回什么、要完成什么任务。比如青蛙跳台阶“frog(n) 表示 n 级台阶的跳法数”汉诺塔“hanoi(n, from, to, aux) 表示把 n 个盘子从 from 借助 aux 移到 to”。第二步找最小规模。问自己参数取什么值时问题简单到可以直接返回这个值就是终止条件。注意一定要比所有可能的调用参数都“更小”否则有漏网之鱼。第三步假设子问题已经解决。直接调用相同函数处理更小的参数这时候不要展开细节。第四步组合当前结果。把子问题的结果和当前层的操作拼在一起。汉诺塔里就是“先移 n-1 个、再移第 n 个、再移 n-1 个”。青蛙跳台阶里就是f(n-1) f(n-2)。第五步用 n1、n2 这种小规模数据验证一遍。哪个地方和预期不一致就回到对应步骤排查。大部分初学者卡在第三步和第四步是因为总想把第五步提前到写代码之前。举一个简短的例子递归逆序打印字符串。void print_reverse(const char *s) { if (*s \0) return; print_reverse(s 1); putchar(*s); }函数语义是“逆序打印从 s 开始的字符串”。最小规模是*s \0遇到字符串结束符直接返回。子问题假设是print_reverse(s 1)已经帮我把后面的字符逆序打印完了那么当前层只需要再打印*s。注意putchar(*s)写在递归调用后面是因为要等后面的字符先打印完才能轮到当前字符。这个例子也再次印证了前面说的“栈先进后出”特性。5.4 一个最笨但好用的递归调试方法最后分享一个我自己的土办法特别适合调试递归逻辑不明的问题在递归函数第一行打印参数和缩进深度。原理很简单用缩进模拟递归层数一层比一层多缩进一段这样你就能清楚看到每次调用进入了哪个分支。void hanoi_debug(int n, char from, char to, char aux, int depth) { for (int i 0; i depth; i) printf( ); printf(hanoi(n%d, from%c, to%c, aux%c)\n, n, from, to, aux); if (n 1) { for (int i 0; i depth; i) printf( ); printf(move 1: %c - %c\n, from, to); return; } hanoi_debug(n - 1, from, aux, to, depth 1); for (int i 0; i depth; i) printf( ); printf(move %d: %c - %c\n, n, from, to); hanoi_debug(n - 1, aux, to, from, depth 1); }调试完把这堆 printf 去掉替换成干净版本就是正式代码。这个方法虽然“笨”但比对着屏幕空想“它到底怎么走的”要高效得多。我看到很多人在递归问题上纠结半天最后其实只需要一行打印参数就能发现问题出在哪里。递归没有那么多玄学把调用过程可视化之后它就是一个有结构的循环展开。记住终止条件、递推关系和递归信任这三件事再配上一两个经典题目练手函数的递归对你来说就不会再是障碍。