递归这玩意儿我当年学 C 语言的时候被它折磨得不轻。明明代码就那么几行但程序怎么跑出来的愣是想不明白。后来总算把函数调用栈、递归出口这些概念啃透了才发现递归其实就是“函数自己调用自己”这么简单只是思维方式和普通编程不太一样。这篇东西不是教科书复读而是把我自己从“看不懂”到“会写、会调、会避坑”的过程和心得整理出来。如果你正在学 C 语言卡在函数递归这里或者虽然能写出递归但不知道背后发生了什么那这篇文章应该能帮上大忙。1. 函数递归到底是什么从一个生活场景说起1.1 递归的核心思想大事化小小事化了递归的英文是 recursion它的定义听起来很绕一个函数直接或间接地调用自身。但光是“自己调用自己”这句话初学者听了等于没听。我更喜欢用“套娃”来理解——一个大娃娃里面装着同样形状的小娃娃小娃娃里面还装着更小的娃娃直到最小的那个实心娃娃为止。放到编程里递归强调的是“把大问题分解成更小、但结构相同的子问题然后用同一种方法处理子问题”。比如你要算第 5 个斐波那契数那我就先算第 4 个和第 3 个要算第 4 个又得算第 3 个和第 2 个……一直拆到已知的第 1 个、第 2 个为止。这个“一直拆”的过程就是递归调用“已知的最小子问题”就是递归出口。很多教材会把递归总结成三步分解、求解、合并。我觉得更贴切的说法是“递”和“归”先一层层往里递进到达最底层的最小问题后再一层层把结果返回来。整个过程就像你往一个深井里扔石头听到回声后声音再从井底一层层传上来。理解了“递”和“归”是两个方向很多混乱就消除了。1.2 递归必须具备的两个要素递归出口与递归调用写过递归的人都知道递归函数基本长得像一个模板先判断是否到达最小问题是就直接返回答案否则调用自身去解决更小的子问题。这两个核心要素缺一不可。第一个要素是递归出口也有人叫基线条件、终止条件。它决定了递归什么时候停。如果没有出口函数会永远调用自己直到系统栈空间耗尽程序崩溃。我见过太多新手写递归时忘记出口或者出口条件写错程序直接 Stack Overflow。记住一个原则每次递归调用问题规模必须比上一次小而且最终一定能到达出口。第二个要素是递归调用也就是函数体内部调用自己。这里的“自己”并不是复制了一份代码而是重新执行了一遍同样的逻辑只不过参数变了。新手最容易迷惑的就是这里同一个函数为什么第一次 return 之后又跑到上一次调用的代码里去了这就要聊到函数调用栈了。2. 递归背后函数调用栈与内存运行机制2.1 函数调用时发生了什么要真正理解递归光看代码是看不出门道的必须知道 CPU 和内存是怎么配合的。每次你调用一个函数不管是普通函数还是递归调用系统都会在内存的栈区为这次调用分配一块空间这块空间叫作栈帧stack frame。栈帧里保存了这次调用的局部变量、参数值以及“函数执行完后该回到哪一行继续执行”的返回地址。当函数执行到 return 时栈帧被释放程序跳回返回地址继续执行。这个“压栈”和“弹栈”的过程是所有函数调用的底层机制并不是递归特有的。你写一个 main 调用 funcAfuncA 调用 funcB也是同样的压栈弹栈。只不过递归特殊在调用链上的每个函数长得一模一样参数和局部变量值不同罢了。我推荐新手把“函数调用栈”画出来。很多人问为什么递归最后的结果是倒着出来的画一遍栈就全明白了。2.2 递归压栈与弹栈以阶乘为例手把手画栈我们拿最经典的阶乘递归来画。C 语言代码长这样long factorial(int n) { if (n 1) { return 1; } return n * factorial(n - 1); }main 里调用factorial(4)。注意每次调用 factorial都会在栈顶压入一个新栈帧第一次调用factorial(4)n 4不满足n 1执行return 4 * factorial(3)。但注意在算乘法之前得先调用factorial(3)于是压入新栈帧。第二层factorial(3)n 3继续压入factorial(2)。第三层factorial(2)n 2压入factorial(1)。第四层factorial(1)n 1满足出口直接return 1这时最底层栈帧弹出。接着开始“归”的过程factorial(2)拿到了factorial(1)的结果 1计算2 * 1 2返回。factorial(3)拿到了 2计算3 * 2 6返回。factorial(4)拿到了 6计算4 * 6 24返回。所以最终结果是 24。很多人开始容易把return n * factorial(n - 1)理解成“先算出 n-1 的阶乘再乘 n”这个理解没错但要清楚这个“先算出 n-1 的阶乘”是一个完整的函数调用它会一直递归到出口再返回。所以整个递归过程是“先递后归”不是一步到位的。2.3 递归深度与栈溢出为什么不能无限递归每个栈帧要占用内存空间虽然单个栈帧一般只有几十到几百字节但几万次调用压下去栈区就吃不消了。在 Windows 的默认设置下线程栈一般是 1MB 到 8MBLinux 下通常是 8MB。如果递归深度太大比如写了一个没有出口的foo()系统就会抛出Stack Overflow。我实测过一个实验在一台 64 位 Linux 机器上用一个空参数的递归函数去无限调用默认栈大小 8MB大概几万层就崩了。你问为什么不把栈扩大可以改但没必要。真正务实的态度是能用循环解决的递归不要硬写递归必须用递归的场景要估算最深层数避免在运行时爆栈。3. 案例拆解五个最经典的递归入门练习3.1 阶乘计算最简单的递归模板阶乘的递推关系是n! n * (n-1)!出口是0! 1或1! 1。代码刚才已经给了。这个例子适合理解“递归出口 递归调用”的最小结构但它其实也是效率最低的一种写法。如果只是为了算阶乘用循环long fact_iter(int n) { long result 1; for (int i 2; i n; i) { result * i; } return result; }两者结果一样。递归版好处是代码和数学定义一一对应容易写对坏处是每次调用都有函数压栈弹栈的开销还容易爆栈。阶乘超过 20 用 long 已经不够了需要考虑溢出问题这也是一个隐藏考点。3.2 斐波那契数列让你看清递归的膨胀代价斐波那契数列的递推式是f(n) f(n-1) f(n-2)出口是f(0)0, f(1)1。初学递归十有八九写过这样long fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); }这段代码非常“漂亮”但跑fib(40)就已经卡得让人怀疑人生。为什么因为重复计算爆炸。画一下调用树算fib(5)需要fib(4)和fib(3)算fib(4)又需要fib(3)和fib(2)。这里的fib(3)被计算了两次fib(2)被计算了三次。当 n 增大时调用次数几乎到达了2^n的量级这不是开玩笑。解决重复计算的办法有两个一是改成循环用两个变量滚动迭代二是用记忆化递归Memoization用一个数组把算过的值存下来下次直接取。在实际项目中我一般不推荐用纯递归写斐波那契除非你显式地加了缓存。这个例子最大的意义是让你直观感受到递归虽然思维简单但不加限制地使用代价有多可怕。3.3 汉诺塔递归思维的最佳训练场汉诺塔几乎是递归入门必须手写一遍的题目有三根柱子 A、B、CA 上有 n 个盘子要把所有盘子移到 C且任何时候大盘不能压小盘。你让非递归思路的人去想“怎么移动”三个盘子还能凑合手推五个盘子就开始崩溃。但用递归描述只需要三句话先把上面 n-1 个盘子从 A 移到 B借助 C。把第 n 个盘子从 A 移到 C。再把 B 上的 n-1 个盘子移到 C借助 A。代码void hanoi(int n, char from, char temp, char to) { if (n 1) { printf(%c - %c\n, from, to); return; } hanoi(n - 1, from, to, temp); printf(%c - %c\n, from, to); hanoi(n - 1, temp, from, to); }这里面最容易懵的是temp和to的角色互换。其实不用纠结“哪一根是辅助柱”你只需要知道这层函数负责把 n 个盘子从 from 移到 to中间允许用 temp 当辅助。那么递归调用时把别人当辅助就行。我教学生的方法是不要试图跟踪每一层柱子的具体名字只要你坚信“这个函数能完成把 n 个盘子从 from 移到 to”这件事那么第一步和第三步的调用就是合法的。汉诺塔的移动次数是2^n - 1所以 64 个盘子的总量是个天文数字。这个题目对新手最大的启发是递归可以让你用很少的代码描述一个极其复杂的过程。但它的代价就是时间指数爆炸所以只能作为思维训练不适合大规模实际运算。3.4 字符串逆序用两个函数思路对比字符串逆序是个高频练习题PTA、翁恺 C 语言练习题里都有。递归解法一般长这样把字符串看成“首字符 剩余子串”逆序就是“剩余子串逆序 首字符”。用指针写void reverse_str(char *s, int left, int right) { if (left right) { return; } char temp s[left]; s[left] s[right]; s[right] temp; reverse_str(s, left 1, right - 1); }这种写法本质上是“双指针交换 递归推进”每次把最左和最右的字符交换然后向内缩小范围。出口是 left right。这个递归的深度是字符串长度的一半所以不太容易爆栈。其实字符串逆序用循环更直观。递归的价值在于它强迫你从“不断缩小问题区间”的角度思考。同样的思路还可以用于判断回文串把递归体改成比较首尾字符是否相等如果不相等返回 0否则继续递归判断中间部分。从字符串逆序到判断回文再到二分查找你会发现递归经常被用来处理“区间”问题。3.5 二分查找与求数组最大值递归处理“区间”问题很多教材把二分查找放到数组或指针章节但它也适合用来练递归。递归版二分查找的思路是在一个有序数组的[left, right]区间里找目标值。取中间位置 mid如果中间值等于目标返回下标如果中间值大于目标说明目标在左半区间递归查找[left, mid-1]否则递归查找[mid1, right]。出口是 left right表示没找到返回 -1。int binary_search_recursive(int arr[], int left, int right, int target) { if (left right) { return -1; } int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binary_search_recursive(arr, left, mid - 1, target); } else { return binary_search_recursive(arr, mid 1, right, target); } }注意计算 mid 不要写成(left right) / 2因为 left right 可能溢出。这属于面试官爱问的细节。求数组最大值也可以用递归把数组对半分分别求左右两半的最大值再取两者较大者。这其实就是分治思想的雏形。递归在这里的写法:int max_recursive(int arr[], int left, int right) { if (left right) { return arr[left]; } int mid left (right - left) / 2; int left_max max_recursive(arr, left, mid); int right_max max_recursive(arr, mid 1, right); return left_max right_max ? left_max : right_max; }这种“分而治之”的写法到了归并排序、快速排序里会反复出现。所以别觉得递归只是练习它其实是后续学算法的基础。4. 递归与循环的博弈什么时候必须用递归4.1 递归 vs 迭代三张对照表看懂差别很多新手会问既然循环都能做为什么还要学递归这个问题很实在。递归和迭代各有优劣我列几个常见维度对比一下对比维度递归迭代循环代码可读性对复杂结构问题更直观对简单重复问题更易读性能有函数调用开销可能重复计算通常更快内存占用低适用场景树、图、分治、回溯、动态规划线性遍历、累加、简单计数风险递归深度过大容易栈溢出基本无栈溢出风险代码复杂度代码短但理解成本高代码长但控制流程清楚注意这不是说“递归慢迭代快”这句话永远正确。如果递归是尾递归且编译器做了优化两者性能可以接近。但在 C 语言里标准并没有强制要求编译器做尾递归优化所以你不能把性能押在编译器上。4.2 尾递归优化递归的救星还是安慰剂尾递归是指递归调用是函数体中的最后一个动作并且函数返回的就是递归调用的返回值。比如上面的阶乘递归不是尾递归因为最后一步是n * factorial(n-1)乘法还没有执行。改成尾递归需要多传一个“累计结果”参数long factorial_tail(int n, long acc) { if (n 1) { return acc; } return factorial_tail(n - 1, acc * n); }调用时写成factorial_tail(4, 1)。你看factorial_tail(n - 1, acc * n)是最后一个表达式没有任何后续计算所以是尾递归。如果编译器优化这种递归可以复用当前栈帧不新增栈帧从而避免栈溢出。但在 C 语言里尾递归优化不是标准的硬性要求。GCC 在-O2下优化得不错VS 的编译器MSVC就不一定了。所以我不建议把“反正有尾递归优化”当成随便写深递归的理由。更稳妥的做法是如果递归深度可能超过几千尽量改成循环如果必须保留递归结构再考虑尾递归写法自求多福。4.3 实战建议如何选择递归、循环或结合我的选择原则很简单第一如果问题是天然分层的比如遍历二叉树、求表达式值、汉诺塔这类优先用递归因为循环写起来要么太复杂要么需要自己维护一个栈反而容易出错。第二如果问题只是简单线性迭代比如求和、阶乘、斐波那契果断用循环。第三如果必须用递归但深度可能很大可以先考虑是否能用记忆化、动态规划或者干脆用循环加显式栈模拟递归。这里分享一个我常用的折中方案用循环模拟递归。原理很简单递归本质就是压栈弹栈那我可以自己定义一个栈结构把每次需要处理的“状态”压进去循环处理。示例用栈模拟二叉树中序遍历。这类代码虽然比递归长但不会爆栈还能精确控制内存。等你熟练掌握递归后再去看“显式栈模拟递归”的代码思路会清晰很多。5. 新手必踩的坑递归调试与代码优化实录5.1 常见错误一忘记递归出口或出口条件永远不满足这个坑我在带新手的时候见得太多了。最典型的就是下面这样void bad_recursion(int n) { printf(%d\n, n); bad_recursion(n - 1); }如果传的是负数它会一直往负无穷递归。更隐蔽的写法是出口条件放错位置或者判断条件与递归变化不一致。比如递归里写n--但传给函数的还是原 n。因为n--是“先使用后自减”导致递归永远在传同一个 n这就是出口条件永远不满足的经典原因。我的排查建议是写递归之前先口头说一遍“当参数是什么值时函数直接返回”如果这个“什么值”永远不会被递归参数递进到那一定有问题。调试时可以直接打印每次递归的入参一眼就能看出参数有没有变小、有没有逼近出口。5.2 常见错误二重复计算导致超时斐波那契递归就是重复计算的典型。很多 PTA 题目、OJ 题都会故意让你用递归做然后一提交发现 Time Limit Exceeded。这中间的坑在于你逻辑完全正确但效率太低。我的经验是写完递归后先算一下它的时间复杂度。假如递归画出来的树里子问题有大量重叠那就要考虑两种优化。第一种是记忆化用一个全局数组或键值对存结果long fib_memo(int n) { static long memo[100] {0}; if (n 1) { return n; } if (memo[n] ! 0) { return memo[n]; } memo[n] fib_memo(n - 1) fib_memo(n - 2); return memo[n]; }第二种是直接改成自底向上的动态规划用循环推。在 C 语言里除非老师明确要求用递归实现否则我建议能迭代就迭代。5.3 常见错误三传参陷阱与全局变量滥用递归函数经常需要传递很多参数比如区间递归要传左右边界。新手容易犯一个错在递归函数内部修改了作为参数的数组然后期待上层调用不受影响。其实数组传递的是地址内层修改会直接影响原数组但普通变量按值传递内层修改不会影响外层。这个“值传递”和“引用传递”的区别在递归里会被放大。还有全局变量。初学者总喜欢用全局变量来省去传参比如让递归函数直接操作一个全局数组。这样写虽然省事但很容易出 bug。因为递归是分层的每次调用都可能修改全局状态你很难判断当前修改影响的是哪一层。我建议尽量把所有需要变化的状态都通过函数参数传递这样每一层的输入输出更明确。5.4 调试技巧printf 大法、断点观察栈帧说到调试递归我强烈推荐新手先用“printf 大法”。在函数开头打印当前参数或者在 return 前打印返回值能让你直观看到递进和回归的顺序。比如int fact(int n) { printf(enter fact(%d)\n, n); if (n 1) { printf(exit fact(%d) - 1\n, n); return 1; } int result n * fact(n - 1); printf(exit fact(%d) - %d\n, n, result); return result; }跑一遍fact(4)你就能在终端看到一层层 enter 和 exit 的配对像括号一样嵌套。这种方法是理解递归执行顺序最快的捷径比单步调试还直观。如果你用 IDE 的断点调试也可以在调用栈窗口观察当前栈帧。VS Code 里配置好 C/C 调试环境后每递归一次调用栈窗口就会多一层函数调用。你点开每一层能看到那个层里局部变量的值。这种“上帝视角”对理解递归很有帮助。5.5 实用检查清单写递归或改递归的时候我习惯过一遍这个清单分享给你递归出口是否清晰参数最终能到达出口吗每次递归调用问题规模是否变小是朝出口方向变小吗递归函数里的返回值是否被正确使用有没有忘记 return参数是用值传递还是地址传递内层修改会不会意外影响外层是否存在大量重复子问题需不需要记忆化或改迭代最坏情况下递归深度是多少会不会爆栈递归调用和后续运算的顺序是否正确比如是先递归再运算还是先运算再递归。6. 课后练习与资源推荐从入门到进阶6.1 推荐练习题目对应翁恺、PTA 常见题型如果你是跟着网课学尤其是看过翁恺 C 语言课程或者要在 PTA拼题 A刷题我建议按难度梯度练这些递归题第一梯队递归求阶乘、递归求 1 到 n 的和、递归求最大值。这些是模板题只要求你照猫画虎写出递归结构。第二梯队字符串逆序PTA 常见、判断回文串、递归二分查找。这些要求你把递归用在“区间”上理解缩小范围的思路。第三梯队汉诺塔、快速排序递归实现、归并排序递归实现。这些是分治思想的核心练习考你的分解和合并能力。第四梯队全排列、八皇后、二叉树遍历。这些已经是回溯和高级算法的范畴但根基依然是递归。我做 PTA 题目时发现很多题会卡时间这时候递归写法很可能超时。所以你在本地跑通了递归版之后最好再思考一下怎么用迭代优化。举个例子PTA 上有“数列求和”之类的题递归会超时迭代就能过。这种“先递归实现再迭代优化”的训练方式能让你同时掌握两种思维。6.2 从递归到分治、回溯的过渡递归学到后面你会发现它其实是一整类算法的底座。分治算法本质就是“递归拆问题再合并结果”快速排序、归并排序、二分查找都是这个套路。回溯算法本质是“递归搜索 撤销选择”八皇后、迷宫、全排列都是在一个递归搜索树上不断前进和后退。动态规划里的状态转移方程很多也可以用递归加记忆化来表达只是最终为了性能改成了自底向上的循环。所以我一直觉得C 语言里的函数递归不只是一个小知识点它是开启算法思维闸门的那把钥匙。你在初学阶段把它搞透后面学数据结构里的树、图、排序、搜索都会顺畅很多。6.3 我的个人学习心得最后说点实际的。我自己学递归时曾经卡在“汉诺塔”三个参数的角色转换上整整一个下午。后来我把递归函数里的人名全部改成 from、to、temp然后反复用三个盘子、四个盘子去手推又把 printf 插在函数开头和结尾最后终于通了。这个过程给我的启发是不要试图用眼睛“跟踪”每一层递归状态而是要信任递归定义。只要你把“某个函数能完成某件事”当作事实那递归调用就是安全的。这是递归思维和普通命令式思维最大的不同——你得先把“重复发生的事情”抽象出来而不是每次都重新模拟一遍。如果你现在还是觉得递归很难别急这是正常的。我见过不少同学在阶乘和斐波那契那儿反复看视频突然某天早上醒来就会写汉诺塔了。递归这种思维方式需要一点顿悟而顿悟的前提是你已经积累了大量“看不懂”的画面。你只要多画栈、多打印、多做题这个“卡住”的阶段一定会过去。等你再看递归代码时能一眼瞄出出口、找到递推关系、估算复杂度那你就算真正入门了。 
长河君 · 2026/9/10 4:46:38 · 阅读 1.2k C语言递归入门：从函数调用栈到调试避坑全指南
递归这玩意儿我当年学 C 语言的时候被它折磨得不轻。明明代码就那么几行但程序怎么跑出来的愣是想不明白。后来总算把函数调用栈、递归出口这些概念啃透了才发现递归其实就是“函数自己调用自己”这么简单只是思维方式和普通编程不太一样。这篇东西不是教科书复读而是把我自己从“看不懂”到“会写、会调、会避坑”的过程和心得整理出来。如果你正在学 C 语言卡在函数递归这里或者虽然能写出递归但不知道背后发生了什么那这篇文章应该能帮上大忙。1. 函数递归到底是什么从一个生活场景说起1.1 递归的核心思想大事化小小事化了递归的英文是 recursion它的定义听起来很绕一个函数直接或间接地调用自身。但光是“自己调用自己”这句话初学者听了等于没听。我更喜欢用“套娃”来理解——一个大娃娃里面装着同样形状的小娃娃小娃娃里面还装着更小的娃娃直到最小的那个实心娃娃为止。放到编程里递归强调的是“把大问题分解成更小、但结构相同的子问题然后用同一种方法处理子问题”。比如你要算第 5 个斐波那契数那我就先算第 4 个和第 3 个要算第 4 个又得算第 3 个和第 2 个……一直拆到已知的第 1 个、第 2 个为止。这个“一直拆”的过程就是递归调用“已知的最小子问题”就是递归出口。很多教材会把递归总结成三步分解、求解、合并。我觉得更贴切的说法是“递”和“归”先一层层往里递进到达最底层的最小问题后再一层层把结果返回来。整个过程就像你往一个深井里扔石头听到回声后声音再从井底一层层传上来。理解了“递”和“归”是两个方向很多混乱就消除了。1.2 递归必须具备的两个要素递归出口与递归调用写过递归的人都知道递归函数基本长得像一个模板先判断是否到达最小问题是就直接返回答案否则调用自身去解决更小的子问题。这两个核心要素缺一不可。第一个要素是递归出口也有人叫基线条件、终止条件。它决定了递归什么时候停。如果没有出口函数会永远调用自己直到系统栈空间耗尽程序崩溃。我见过太多新手写递归时忘记出口或者出口条件写错程序直接 Stack Overflow。记住一个原则每次递归调用问题规模必须比上一次小而且最终一定能到达出口。第二个要素是递归调用也就是函数体内部调用自己。这里的“自己”并不是复制了一份代码而是重新执行了一遍同样的逻辑只不过参数变了。新手最容易迷惑的就是这里同一个函数为什么第一次 return 之后又跑到上一次调用的代码里去了这就要聊到函数调用栈了。2. 递归背后函数调用栈与内存运行机制2.1 函数调用时发生了什么要真正理解递归光看代码是看不出门道的必须知道 CPU 和内存是怎么配合的。每次你调用一个函数不管是普通函数还是递归调用系统都会在内存的栈区为这次调用分配一块空间这块空间叫作栈帧stack frame。栈帧里保存了这次调用的局部变量、参数值以及“函数执行完后该回到哪一行继续执行”的返回地址。当函数执行到 return 时栈帧被释放程序跳回返回地址继续执行。这个“压栈”和“弹栈”的过程是所有函数调用的底层机制并不是递归特有的。你写一个 main 调用 funcAfuncA 调用 funcB也是同样的压栈弹栈。只不过递归特殊在调用链上的每个函数长得一模一样参数和局部变量值不同罢了。我推荐新手把“函数调用栈”画出来。很多人问为什么递归最后的结果是倒着出来的画一遍栈就全明白了。2.2 递归压栈与弹栈以阶乘为例手把手画栈我们拿最经典的阶乘递归来画。C 语言代码长这样long factorial(int n) { if (n 1) { return 1; } return n * factorial(n - 1); }main 里调用factorial(4)。注意每次调用 factorial都会在栈顶压入一个新栈帧第一次调用factorial(4)n 4不满足n 1执行return 4 * factorial(3)。但注意在算乘法之前得先调用factorial(3)于是压入新栈帧。第二层factorial(3)n 3继续压入factorial(2)。第三层factorial(2)n 2压入factorial(1)。第四层factorial(1)n 1满足出口直接return 1这时最底层栈帧弹出。接着开始“归”的过程factorial(2)拿到了factorial(1)的结果 1计算2 * 1 2返回。factorial(3)拿到了 2计算3 * 2 6返回。factorial(4)拿到了 6计算4 * 6 24返回。所以最终结果是 24。很多人开始容易把return n * factorial(n - 1)理解成“先算出 n-1 的阶乘再乘 n”这个理解没错但要清楚这个“先算出 n-1 的阶乘”是一个完整的函数调用它会一直递归到出口再返回。所以整个递归过程是“先递后归”不是一步到位的。2.3 递归深度与栈溢出为什么不能无限递归每个栈帧要占用内存空间虽然单个栈帧一般只有几十到几百字节但几万次调用压下去栈区就吃不消了。在 Windows 的默认设置下线程栈一般是 1MB 到 8MBLinux 下通常是 8MB。如果递归深度太大比如写了一个没有出口的foo()系统就会抛出Stack Overflow。我实测过一个实验在一台 64 位 Linux 机器上用一个空参数的递归函数去无限调用默认栈大小 8MB大概几万层就崩了。你问为什么不把栈扩大可以改但没必要。真正务实的态度是能用循环解决的递归不要硬写递归必须用递归的场景要估算最深层数避免在运行时爆栈。3. 案例拆解五个最经典的递归入门练习3.1 阶乘计算最简单的递归模板阶乘的递推关系是n! n * (n-1)!出口是0! 1或1! 1。代码刚才已经给了。这个例子适合理解“递归出口 递归调用”的最小结构但它其实也是效率最低的一种写法。如果只是为了算阶乘用循环long fact_iter(int n) { long result 1; for (int i 2; i n; i) { result * i; } return result; }两者结果一样。递归版好处是代码和数学定义一一对应容易写对坏处是每次调用都有函数压栈弹栈的开销还容易爆栈。阶乘超过 20 用 long 已经不够了需要考虑溢出问题这也是一个隐藏考点。3.2 斐波那契数列让你看清递归的膨胀代价斐波那契数列的递推式是f(n) f(n-1) f(n-2)出口是f(0)0, f(1)1。初学递归十有八九写过这样long fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); }这段代码非常“漂亮”但跑fib(40)就已经卡得让人怀疑人生。为什么因为重复计算爆炸。画一下调用树算fib(5)需要fib(4)和fib(3)算fib(4)又需要fib(3)和fib(2)。这里的fib(3)被计算了两次fib(2)被计算了三次。当 n 增大时调用次数几乎到达了2^n的量级这不是开玩笑。解决重复计算的办法有两个一是改成循环用两个变量滚动迭代二是用记忆化递归Memoization用一个数组把算过的值存下来下次直接取。在实际项目中我一般不推荐用纯递归写斐波那契除非你显式地加了缓存。这个例子最大的意义是让你直观感受到递归虽然思维简单但不加限制地使用代价有多可怕。3.3 汉诺塔递归思维的最佳训练场汉诺塔几乎是递归入门必须手写一遍的题目有三根柱子 A、B、CA 上有 n 个盘子要把所有盘子移到 C且任何时候大盘不能压小盘。你让非递归思路的人去想“怎么移动”三个盘子还能凑合手推五个盘子就开始崩溃。但用递归描述只需要三句话先把上面 n-1 个盘子从 A 移到 B借助 C。把第 n 个盘子从 A 移到 C。再把 B 上的 n-1 个盘子移到 C借助 A。代码void hanoi(int n, char from, char temp, char to) { if (n 1) { printf(%c - %c\n, from, to); return; } hanoi(n - 1, from, to, temp); printf(%c - %c\n, from, to); hanoi(n - 1, temp, from, to); }这里面最容易懵的是temp和to的角色互换。其实不用纠结“哪一根是辅助柱”你只需要知道这层函数负责把 n 个盘子从 from 移到 to中间允许用 temp 当辅助。那么递归调用时把别人当辅助就行。我教学生的方法是不要试图跟踪每一层柱子的具体名字只要你坚信“这个函数能完成把 n 个盘子从 from 移到 to”这件事那么第一步和第三步的调用就是合法的。汉诺塔的移动次数是2^n - 1所以 64 个盘子的总量是个天文数字。这个题目对新手最大的启发是递归可以让你用很少的代码描述一个极其复杂的过程。但它的代价就是时间指数爆炸所以只能作为思维训练不适合大规模实际运算。3.4 字符串逆序用两个函数思路对比字符串逆序是个高频练习题PTA、翁恺 C 语言练习题里都有。递归解法一般长这样把字符串看成“首字符 剩余子串”逆序就是“剩余子串逆序 首字符”。用指针写void reverse_str(char *s, int left, int right) { if (left right) { return; } char temp s[left]; s[left] s[right]; s[right] temp; reverse_str(s, left 1, right - 1); }这种写法本质上是“双指针交换 递归推进”每次把最左和最右的字符交换然后向内缩小范围。出口是 left right。这个递归的深度是字符串长度的一半所以不太容易爆栈。其实字符串逆序用循环更直观。递归的价值在于它强迫你从“不断缩小问题区间”的角度思考。同样的思路还可以用于判断回文串把递归体改成比较首尾字符是否相等如果不相等返回 0否则继续递归判断中间部分。从字符串逆序到判断回文再到二分查找你会发现递归经常被用来处理“区间”问题。3.5 二分查找与求数组最大值递归处理“区间”问题很多教材把二分查找放到数组或指针章节但它也适合用来练递归。递归版二分查找的思路是在一个有序数组的[left, right]区间里找目标值。取中间位置 mid如果中间值等于目标返回下标如果中间值大于目标说明目标在左半区间递归查找[left, mid-1]否则递归查找[mid1, right]。出口是 left right表示没找到返回 -1。int binary_search_recursive(int arr[], int left, int right, int target) { if (left right) { return -1; } int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binary_search_recursive(arr, left, mid - 1, target); } else { return binary_search_recursive(arr, mid 1, right, target); } }注意计算 mid 不要写成(left right) / 2因为 left right 可能溢出。这属于面试官爱问的细节。求数组最大值也可以用递归把数组对半分分别求左右两半的最大值再取两者较大者。这其实就是分治思想的雏形。递归在这里的写法:int max_recursive(int arr[], int left, int right) { if (left right) { return arr[left]; } int mid left (right - left) / 2; int left_max max_recursive(arr, left, mid); int right_max max_recursive(arr, mid 1, right); return left_max right_max ? left_max : right_max; }这种“分而治之”的写法到了归并排序、快速排序里会反复出现。所以别觉得递归只是练习它其实是后续学算法的基础。4. 递归与循环的博弈什么时候必须用递归4.1 递归 vs 迭代三张对照表看懂差别很多新手会问既然循环都能做为什么还要学递归这个问题很实在。递归和迭代各有优劣我列几个常见维度对比一下对比维度递归迭代循环代码可读性对复杂结构问题更直观对简单重复问题更易读性能有函数调用开销可能重复计算通常更快内存占用低适用场景树、图、分治、回溯、动态规划线性遍历、累加、简单计数风险递归深度过大容易栈溢出基本无栈溢出风险代码复杂度代码短但理解成本高代码长但控制流程清楚注意这不是说“递归慢迭代快”这句话永远正确。如果递归是尾递归且编译器做了优化两者性能可以接近。但在 C 语言里标准并没有强制要求编译器做尾递归优化所以你不能把性能押在编译器上。4.2 尾递归优化递归的救星还是安慰剂尾递归是指递归调用是函数体中的最后一个动作并且函数返回的就是递归调用的返回值。比如上面的阶乘递归不是尾递归因为最后一步是n * factorial(n-1)乘法还没有执行。改成尾递归需要多传一个“累计结果”参数long factorial_tail(int n, long acc) { if (n 1) { return acc; } return factorial_tail(n - 1, acc * n); }调用时写成factorial_tail(4, 1)。你看factorial_tail(n - 1, acc * n)是最后一个表达式没有任何后续计算所以是尾递归。如果编译器优化这种递归可以复用当前栈帧不新增栈帧从而避免栈溢出。但在 C 语言里尾递归优化不是标准的硬性要求。GCC 在-O2下优化得不错VS 的编译器MSVC就不一定了。所以我不建议把“反正有尾递归优化”当成随便写深递归的理由。更稳妥的做法是如果递归深度可能超过几千尽量改成循环如果必须保留递归结构再考虑尾递归写法自求多福。4.3 实战建议如何选择递归、循环或结合我的选择原则很简单第一如果问题是天然分层的比如遍历二叉树、求表达式值、汉诺塔这类优先用递归因为循环写起来要么太复杂要么需要自己维护一个栈反而容易出错。第二如果问题只是简单线性迭代比如求和、阶乘、斐波那契果断用循环。第三如果必须用递归但深度可能很大可以先考虑是否能用记忆化、动态规划或者干脆用循环加显式栈模拟递归。这里分享一个我常用的折中方案用循环模拟递归。原理很简单递归本质就是压栈弹栈那我可以自己定义一个栈结构把每次需要处理的“状态”压进去循环处理。示例用栈模拟二叉树中序遍历。这类代码虽然比递归长但不会爆栈还能精确控制内存。等你熟练掌握递归后再去看“显式栈模拟递归”的代码思路会清晰很多。5. 新手必踩的坑递归调试与代码优化实录5.1 常见错误一忘记递归出口或出口条件永远不满足这个坑我在带新手的时候见得太多了。最典型的就是下面这样void bad_recursion(int n) { printf(%d\n, n); bad_recursion(n - 1); }如果传的是负数它会一直往负无穷递归。更隐蔽的写法是出口条件放错位置或者判断条件与递归变化不一致。比如递归里写n--但传给函数的还是原 n。因为n--是“先使用后自减”导致递归永远在传同一个 n这就是出口条件永远不满足的经典原因。我的排查建议是写递归之前先口头说一遍“当参数是什么值时函数直接返回”如果这个“什么值”永远不会被递归参数递进到那一定有问题。调试时可以直接打印每次递归的入参一眼就能看出参数有没有变小、有没有逼近出口。5.2 常见错误二重复计算导致超时斐波那契递归就是重复计算的典型。很多 PTA 题目、OJ 题都会故意让你用递归做然后一提交发现 Time Limit Exceeded。这中间的坑在于你逻辑完全正确但效率太低。我的经验是写完递归后先算一下它的时间复杂度。假如递归画出来的树里子问题有大量重叠那就要考虑两种优化。第一种是记忆化用一个全局数组或键值对存结果long fib_memo(int n) { static long memo[100] {0}; if (n 1) { return n; } if (memo[n] ! 0) { return memo[n]; } memo[n] fib_memo(n - 1) fib_memo(n - 2); return memo[n]; }第二种是直接改成自底向上的动态规划用循环推。在 C 语言里除非老师明确要求用递归实现否则我建议能迭代就迭代。5.3 常见错误三传参陷阱与全局变量滥用递归函数经常需要传递很多参数比如区间递归要传左右边界。新手容易犯一个错在递归函数内部修改了作为参数的数组然后期待上层调用不受影响。其实数组传递的是地址内层修改会直接影响原数组但普通变量按值传递内层修改不会影响外层。这个“值传递”和“引用传递”的区别在递归里会被放大。还有全局变量。初学者总喜欢用全局变量来省去传参比如让递归函数直接操作一个全局数组。这样写虽然省事但很容易出 bug。因为递归是分层的每次调用都可能修改全局状态你很难判断当前修改影响的是哪一层。我建议尽量把所有需要变化的状态都通过函数参数传递这样每一层的输入输出更明确。5.4 调试技巧printf 大法、断点观察栈帧说到调试递归我强烈推荐新手先用“printf 大法”。在函数开头打印当前参数或者在 return 前打印返回值能让你直观看到递进和回归的顺序。比如int fact(int n) { printf(enter fact(%d)\n, n); if (n 1) { printf(exit fact(%d) - 1\n, n); return 1; } int result n * fact(n - 1); printf(exit fact(%d) - %d\n, n, result); return result; }跑一遍fact(4)你就能在终端看到一层层 enter 和 exit 的配对像括号一样嵌套。这种方法是理解递归执行顺序最快的捷径比单步调试还直观。如果你用 IDE 的断点调试也可以在调用栈窗口观察当前栈帧。VS Code 里配置好 C/C 调试环境后每递归一次调用栈窗口就会多一层函数调用。你点开每一层能看到那个层里局部变量的值。这种“上帝视角”对理解递归很有帮助。5.5 实用检查清单写递归或改递归的时候我习惯过一遍这个清单分享给你递归出口是否清晰参数最终能到达出口吗每次递归调用问题规模是否变小是朝出口方向变小吗递归函数里的返回值是否被正确使用有没有忘记 return参数是用值传递还是地址传递内层修改会不会意外影响外层是否存在大量重复子问题需不需要记忆化或改迭代最坏情况下递归深度是多少会不会爆栈递归调用和后续运算的顺序是否正确比如是先递归再运算还是先运算再递归。6. 课后练习与资源推荐从入门到进阶6.1 推荐练习题目对应翁恺、PTA 常见题型如果你是跟着网课学尤其是看过翁恺 C 语言课程或者要在 PTA拼题 A刷题我建议按难度梯度练这些递归题第一梯队递归求阶乘、递归求 1 到 n 的和、递归求最大值。这些是模板题只要求你照猫画虎写出递归结构。第二梯队字符串逆序PTA 常见、判断回文串、递归二分查找。这些要求你把递归用在“区间”上理解缩小范围的思路。第三梯队汉诺塔、快速排序递归实现、归并排序递归实现。这些是分治思想的核心练习考你的分解和合并能力。第四梯队全排列、八皇后、二叉树遍历。这些已经是回溯和高级算法的范畴但根基依然是递归。我做 PTA 题目时发现很多题会卡时间这时候递归写法很可能超时。所以你在本地跑通了递归版之后最好再思考一下怎么用迭代优化。举个例子PTA 上有“数列求和”之类的题递归会超时迭代就能过。这种“先递归实现再迭代优化”的训练方式能让你同时掌握两种思维。6.2 从递归到分治、回溯的过渡递归学到后面你会发现它其实是一整类算法的底座。分治算法本质就是“递归拆问题再合并结果”快速排序、归并排序、二分查找都是这个套路。回溯算法本质是“递归搜索 撤销选择”八皇后、迷宫、全排列都是在一个递归搜索树上不断前进和后退。动态规划里的状态转移方程很多也可以用递归加记忆化来表达只是最终为了性能改成了自底向上的循环。所以我一直觉得C 语言里的函数递归不只是一个小知识点它是开启算法思维闸门的那把钥匙。你在初学阶段把它搞透后面学数据结构里的树、图、排序、搜索都会顺畅很多。6.3 我的个人学习心得最后说点实际的。我自己学递归时曾经卡在“汉诺塔”三个参数的角色转换上整整一个下午。后来我把递归函数里的人名全部改成 from、to、temp然后反复用三个盘子、四个盘子去手推又把 printf 插在函数开头和结尾最后终于通了。这个过程给我的启发是不要试图用眼睛“跟踪”每一层递归状态而是要信任递归定义。只要你把“某个函数能完成某件事”当作事实那递归调用就是安全的。这是递归思维和普通命令式思维最大的不同——你得先把“重复发生的事情”抽象出来而不是每次都重新模拟一遍。如果你现在还是觉得递归很难别急这是正常的。我见过不少同学在阶乘和斐波那契那儿反复看视频突然某天早上醒来就会写汉诺塔了。递归这种思维方式需要一点顿悟而顿悟的前提是你已经积累了大量“看不懂”的画面。你只要多画栈、多打印、多做题这个“卡住”的阶段一定会过去。等你再看递归代码时能一眼瞄出出口、找到递推关系、估算复杂度那你就算真正入门了。