企业官网建设流程全解析

递归这块硬骨头，我劝你别再背代码了

山东理工大学（SDUT）的《程序设计基础Ⅱ》，到了递归这一章，几乎每个初学C语言的人都会卡一下。但说实话，卡住的原因真的不是智商问题，而是我们的大脑习惯了“从头到尾按顺序执行”的思维方式，突然要你“在函数内部调用自己”，一下子转不过弯来。

这篇文章我打算把递归这块内容彻底讲透。不光是讲理论，还会用OJ上常见的题目例子，把递归的写法套路、运行机制、调试方法和选型逻辑都过一遍。不管你是刚学到函数、第一次接触递归的新手，还是已经刷题刷到怀疑人生的同学，这篇文章应该都能帮你把“知其然”变成“知其所以然”。顺便说一句，期末考试递归必考，而且往往是拉开分数的那道题，所以值得你花一个小时认真看完。

1. 从“函数调用函数”看递归的本质：一场永不结束的套娃

递归这个概念，教科书上喜欢下定义：“函数直接或间接调用自身”。但这句话太抽象，我换一种说法：递归本质上就是函数调函数，只不过调用的是它自己。而“函数调函数”这件事，你从学第一门课的时候就会了。

1.1 你早就会函数调用了，只是没反应过来

想想看，你在主函数里写过这样的代码：

printf("Hello, SDUT!");

printf就是一个函数，主函数调用它，它执行完就返回。然后你又写过自定义函数：

int add(int a, int b) { return a + b; } int main() { int sum = add(3, 4); printf("%d", sum); return 0; }

主函数调用add，add里的代码执行完，把结果返回给主函数。整个过程就是：调用方暂停，被调方执行，执行完返回，调用方继续。

递归就是把“被调方”换成了“自己”。比如：

void hello() { printf("Hello!\n"); hello(); // 自己调用自己 }

你运行这个程序，它会把Hello!无限打印下去——因为hello执行到hello()这行时，又去执行hello了，永远没有返回的时候。

很多人到这一步就开始懵：“它怎么不往下走了？”因为它根本就没走完过。caller在等callee返回，而callee又在等下一个callee返回，形成一个无限嵌套的等待链。

1.2 用“剥洋葱”建立递归直觉

我给学生讲递归时，最喜欢用的类比是剥洋葱。你要把一整颗洋葱剥到最里面那层，步骤是：

• 先剥掉最外面一层；
• 剥完发现还是一颗洋葱，那就再剥一层；
• 重复这个过程，直到剥到最里面什么都没有了。

你发现没有，剥洋葱的过程本身就是重复的——“剥掉一层”这个动作反复执行，但剥的对象（洋葱）越来越小。这就是递归的核心直觉：通过反复处理一个规模更小的同类问题，最终到达一个不能再拆分的终点。

人类理解递归的方式其实是“懒人算法”：我不用关心整颗洋葱要剥多少层，我只需要知道“剥一层之后，剩下的还是一颗更小的洋葱，重复同样的方法就行”。至于到底剥了几层，那是计算机的事。

1.3 运行栈：递归背后的“记账本”

递归能跑起来，靠的是函数调用栈（Call Stack）。每次调用一个函数，系统会在栈上分配一块区域，称为栈帧（Stack Frame），用来存放这次调用的参数、局部变量和返回地址。函数返回时，栈帧被弹出，控制权交还给调用方。

我画一个阶乘函数factorial(3)的调用过程你就明白了。假设代码是：

int factorial(int n) { if (n <= 1) return 1; // 边界条件 return n * factorial(n - 1); // 递归调用 }

调用factorial(3)时，栈上依次压入：

factorial(3)的栈帧: n = 3，等待factorial(2)的结果 factorial(2)的栈帧: n = 2，等待factorial(1)的结果 factorial(1)的栈帧: n = 1，直接返回1

注意，factorial(1)因为满足n <= 1，所以不用再往下调，直接返回1。然后这个结果“一层层往回送”：

factorial(1)返回1 → factorial(2)算出2*1=2 → factorial(3)算出3*2=6

整个过程就像洋葱剥到底之后，再把每一层重新粘回去。

理解这个栈帧机制特别重要。因为后面你会碰到栈溢出（Stack Overflow），就是递归太深，栈空间被用完了。到时候你就知道，不是程序逻辑错，而是你的递归层数超出了栈的容量。

2. 手写递归的固定套路：从数学归纳到代码实现

“递归我能看懂，但让我自己写就写不出来。”这句话我听了不下百遍。说实话，写递归确实有套路，而且套路非常固定。你只要按部就班地做三步，大部分递归题都能写出来。

2.1 三步法：边界条件、递归关系、递归调用

我写递归从来都是按这个顺序思考：

第一步：找边界条件（Base Case）。就是“问题小到什么程度，答案就显而易见了”。比如阶乘，1的阶乘就是1；数组求和，空数组的和是0。边界条件必须有限且可到达。

第二步：找递归关系（Recurrence Relation）。就是把“n的答案”和“n-1（或更小）的答案”联系起来。阶乘的递归关系就是n! = n * (n-1)!。

第三步：把递归关系写成代码。在函数体内调用自身，注意调用的规模必须朝边界条件方向递减。

拿阶乘来说：

int factorial(int n) { // 第一步：边界条件 if (n <= 1) return 1; // 第三步：递归调用（规模n-1 < n，朝边界靠近） return n * factorial(n - 1); }

三步走完，代码就出来了。但这里有个很多教材没点破的细节：为什么边界条件是n <= 1而不是n == 1？因为如果某人传入factorial(0)，n == 1就会无限递归。写成n <= 1，0的阶乘也能正确返回1。这就是我在实际写代码时的一个习惯：边界条件宁可多覆盖一点，也别留缝隙。

2.2 从数学归纳法理解递归的正确性

写递归的人，本质上是在用数学归纳法思考。数学归纳法有两步：证明n=1时命题成立（对应边界条件）；假设n=k成立，证明n=k+1成立（对应递归关系）。

递归代码的正确性也是靠这两点保证的。你不需要在脑子里把factorial(500)的完整调用链条跑一遍——你只需要相信两件事：

1. 边界条件是对的；
2. 如果factorial(n-1)返回了正确答案，那么n * factorial(n-1)也是正确答案。

这就是所谓的递归信任（Recursive Leap of Faith）。我当年学递归的时候，老师说过一句话让我记到现在：“写递归的时候，别想着递归的过程，只想着递归的结果。”意思是，你在写factorial(n)函数体时，直接假设factorial(n-1)是对的函数，把它当现成的工具用就行。

2.3 经典入门题实战：数组求和与字符串反转

光说理论没用，我们上手写两个OJ最常见的入门递归题。

数组求和：给定数组a[]和长度n，返回所有元素之和。

int sum(int a[], int n) { if (n == 0) return 0; // 边界：空数组和为0 return sum(a, n - 1) + a[n - 1]; // 递归：前n-1个元素的和 + 第n个元素 }

这个写法非常典型：把“求n个元素的和”转化为“求n-1个元素的和加上最后一个元素”。规模从n减到n-1，一直到0。

字符串反转：给定字符串s，反转后输出。

void reverse(char s[], int start, int end) { if (start >= end) return; // 边界：只剩0个或1个字符，无需反转 char tmp = s[start]; s[start] = s[end]; s[end] = tmp; reverse(s, start + 1, end - 1); // 递归：处理中间的字符串 }

这里的递归思路是：先把首尾字符交换，然后“里面的字符串交给递归去做”。你看，一旦想通了，递归代码其实很简洁，比循环写起来还要直观。

2.4 为什么“兔子数列”是递归教学的头号陷阱

说到递归，必然绕不开斐波那契数列：

int fib(int n) { if (n == 0 || n == 1) return n; return fib(n - 1) + fib(n - 2); }

代码只有三行，看起来非常完美。但你要是真去算fib(50)，你会等到怀疑人生。原因很简单：这个递归存在大量重复计算。fib(5)要算fib(4)和fib(3)，而fib(4)又要算fib(3)和fib(2)——同一个fib(3)被算了两次。展开之后你会发现，这棵递归树几乎膨胀成一棵满二叉树，时间复杂度是O(2^n)。

我给学生讲这个例子，是想说明一个重要的道理：写得出不等于写得好。你学会了递归的套路，还得学会判断“这个递归值不值得写”。斐波那契用循环写只要O(n)：

int fib(int n) { if (n <= 1) return n; int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; }

所以在实际做题时，我通常先问自己一句：“这个问题用递归写，会不会有严重的重复计算？”如果有，要么加个数组做记忆化，要么直接改迭代。

3. 递归和迭代的正面交锋：机制差异与选型依据

你肯定听说过“递归和迭代可以互相转换”这句话。没错，理论上任何递归都能用循环加栈模拟出来，任何循环也都能改写成递归。但理论归理论，真到做题和写项目的时候，选哪个是要拿实际约束说话的。

3.1 从求1加到n看两种思维方式的差异

先看最简单的题目：求1 + 2 + ... + n。

迭代写法：

int sum_iter(int n) { int s = 0; for (int i = 1; i <= n; i++) s += i; return s; }

递归写法：

int sum_rec(int n) { if (n == 0) return 0; return sum_rec(n - 1) + n; }

迭代的思路是“从1开始累加，加到一个目标值”，它维护一个不断变化的累加变量，本质上是一个一个地把工作做完。递归的思路是“我先把前面n-1项的和算出来，再加上最后一项”，本质上是把一个大问题分解成同构的小问题。

这两种思路没有高下之分，但它们对应的场景不一样。迭代适合“过程明确、每个步骤都看得见”的任务；递归适合“问题能自然按规模拆分”的任务。

3.2 同一个功能两种实现的性能对比

说个SDUT OJ上很经典的问题：求最大公约数，用辗转相除法。这是递归和迭代都能轻松写的题目。

递归实现：

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

迭代实现：

int gcd_iter(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; }

从性能角度说，递归版每次调用都要分配栈帧、保存现场，开销比循环大。但请注意，这里的“大”是相对于普通循环而言的。gcd的递归深度非常浅（对数级别），所以两者运行时间几乎无差别。真正有差别的是斐波那契那种“递归爆炸”的题目，那种情况下，递归版会慢到不可用。

我给一个经验判断标准，你直接照抄即可：

3.3 什么时候必须用递归？什么时候千万别用

先说“千万别用”的场景：递归深度不可控的时候。比如说，你要处理一个可能上万层的嵌套结构，用递归写得很爽，但程序一运行就爆栈。这时候你就需要把递归改成迭代，自己维护一个栈。

再说“最好用递归”的场景：问题本身的定义就是递归的。典型的例子是二叉树的遍历。树的定义本身就是“一个节点下面挂两棵子树”，用递归写出来的遍历代码，干净利落：

void inOrder(struct TreeNode* root) { if (root == NULL) return; inOrder(root->left); printf("%d ", root->val); inOrder(root->right); }

如果用迭代写中序遍历，你得手动模拟栈，代码起码翻倍，还得小心入栈出栈的顺序。所以这棵树长得那么“递归”，你就别非拿循环跟它硬碰。

4. 递归调试与翻车现场：爆栈、无限递归和边界错乱

写递归最大的痛苦不是写不出来，而是写出来了却不知道错在哪。循环写错了，你可以单步调试；递归写错了，你单步调试都可能陷进去出不来。这一节我讲讲自己在LibreOJ和SDUT OJ上踩过的那些递归坑。

4.1 栈溢出：不是逻辑错，而是层数太深

先说最经典的一个错误。写这个求幂的递归：

int power(int x, int n) { if (n == 0) return 1; return x * power(x, n - 1); }

算power(2, 100000)，程序崩溃。报错通常是Segmentation fault或者Stack overflow。很多人第一反应是“我代码哪里写错了”，但其实逻辑完全没毛病，错在递归深度超过了栈的容量。

每一层递归大约消耗几十字节到上百字节的栈空间。默认栈空间在Linux下通常是8MB，在Windows MSVC下通常是1MB。假设一层消耗100字节，1MB栈大概能支持一万层递归。你算power(2, 100000)就是10万层，不炸才怪。

遇到这种情况，要么把递归改成循环，要么用快速幂——快速幂的递归深度是O(log n)，10万次方深度只有17层左右：

int fastPower(int x, int n) { if (n == 0) return 1; if (n % 2 == 1) return x * fastPower(x, n - 1); return fastPower(x * x, n / 2); }

所以你看，递归并非不能深层，关键是深度要以对数级别增长，而不是线性级别。

4.2 无限递归：少了那行“return”的惨痛教训

写递归时最深恶痛绝的BUG：忘记写边界条件，或者边界条件永远达不到。比如：

void countDown(int n) { printf("%d ", n); countDown(n - 1); }

看起来没啥问题，n确实一直在减。但问题是：n减成负数之后呢？这个递归没有任何停下来的条件，它会一直减到int溢出，然后变成正数继续减……无限循环。正确写法：

void countDown(int n) { if (n < 0) return; // 边界条件 printf("%d ", n); countDown(n - 1); }

还有另一种隐蔽的情况：递归调用时参数没变。比如：

int f(int n) { if (n == 0) return 1; return f(n); // 参数还是n，根本没变小 }

这代码跑起来就是活脱脱的“死循环”，而且比while(1)难排查得多——因为它披着“递归”的外衣，让你总觉得哪里有点不对但说不出来。所以写递归时养成一个习惯：每次写递归调用，先看一眼参数是不是比原来的小。

4.3 调试递归的两把斧头：打印调用树和“尾递归”陷阱

我在OJ上调试递归，不喜欢单步跟，因为跟几步就晕了。我更喜欢打印调用痕迹。例如调试汉诺塔的时候，我会在函数入口打印当前参数：

void hanoi(int n, char from, char aux, char to) { printf("hanoi(%d, %c, %c, %c)\n", n, from, aux, to); if (n == 1) { printf("move %d from %c to %c\n", n, from, to); return; } hanoi(n - 1, from, to, aux); printf("move %d from %c to %c\n", n, from, to); hanoi(n - 1, aux, from, to); }

输出一下，你就能清清楚楚看到每一次调用的参数变化，问题往往一眼就能看出来。

顺带说说尾递归。尾递归是指递归调用是函数体里的最后一步操作，不再做任何额外计算。比如：

int fact_tail(int n, int acc) { if (n == 0) return acc; return fact_tail(n - 1, acc * n); // 最后一步是递归调用，没有后续操作 }

普通的阶乘递归n * factorial(n-1)在递归返回后还要做一次乘法，所以它必须保留当前栈帧，等递归返回后才能算乘法。尾递归不同，它把中间结果通过参数往下传，理论上不需要保留外层栈帧，因此现代编译器（在优化选项开启时）可能把它优化成循环，不再消耗栈空间。但要注意：C语言编译器不保证一定做尾递归优化，很多OJ和评测机默认不开优化。所以别仗着“我写的是尾递归”就无限递归下去。

4.4 边界条件错乱：一个等于号毁掉一个OJ提交

说一个特别容易阴沟翻船的细节。写二分查找的递归版：

int binarySearch(int a[], int left, int right, int target) { if (left > right) return -1; // 边界：没找到 int mid = (left + right) / 2; if (a[mid] == target) return mid; if (a[mid] < target) return binarySearch(a, mid + 1, right, target); return binarySearch(a, left, mid - 1, target); }

注意mid的计算。(left + right) / 2其实是有隐患的：如果left + right很大，可能整数溢出。稳妥写法是left + (right - left) / 2。这算是一个面试官爱考、OJ上容易踩的经典坑。

更常见的边界错乱是应该返回mid还是mid+1。每次递归调用区间的划分，必须保证：区间缩小、不遗漏元素、不无限循环。这三个条件缺一不可。我的习惯是写完之后，用两个最小例子手工走一遍：一个能找到目标，一个找不到目标。

5. 把递归用出水平：汉诺塔与八皇后的设计思维

学会了基本套路，你还得会举一反三。程序设计基础课的期末卷子，递归的大题往往不是阶乘那种送分题，而是需要你设计递归结构的题目。汉诺塔和八皇后是两道必修课。

5.1 汉诺塔：从“三步走”理解递归抽象

汉诺塔的规则我就不重复了，直接说递归解法。要把n个盘子从A柱移到C柱，借助B柱：

1. 先把上面n-1个盘子从A移到B（借助C）；
2. 把最底下的大盘子从A移到C；
3. 再把n-1个盘子从B移到C（借助A）。

代码就是文章前面看到的那样，但这里我想让你注意一个思维转变：你根本不需要去关心“n-1个盘子具体怎么移动”。你只需要相信，hanoi(n-1, A, C, B)这个调用能帮你完成这件事。至于它内部怎么倒腾，那是更小规模的同一个问题，它自己会解决。

这种“把大问题缩小到能直接解决，然后把小问题的解组合成大问题的解”的思路，就是递归设计的核心。汉诺塔的递归代码难住过很多人，但它的核心逻辑只有这三大步——第一步，移动上方n-1个盘子；第二步，移动底部第n个盘子；第三步，移动上方n-1个盘子到目标柱。这背后的思路，和你在学校社团里组织人搬宿舍是一个道理：我只需要安排“负责人”去做一部分事，不用事必躬亲。

5.2 回溯思想：八皇后里的递归不止是“递”，还得有“归”

如果说汉诺塔让你学会了“递”，那八皇后就是让你学会“归”。八皇后问题要在8x8的棋盘上放8个皇后，让它们互不攻击（不同行、不同列、不同对角线）。

我给你的思路是：一行一行放皇后。每到一个新行，尝试每一列；如果这个位置不冲突，就放下皇后，然后递归去处理下一行；如果下一行怎么都放不下，就回到这个位置，尝试下一列——这就是回溯（Backtracking）。

核心代码框架：

int queens[10]; // queens[i]表示第i行皇后所在的列号 int isSafe(int row, int col) { for (int i = 0; i < row; i++) { if (queens[i] == col) return 0; // 同列 if (abs(queens[i] - col) == row - i) return 0; // 对角线 } return 1; } void solve(int row, int n) { if (row == n) { // 所有行都放好了，找到一个解 // 输出解 return; } for (int col = 0; col < n; col++) { if (isSafe(row, col)) { queens[row] = col; solve(row + 1, n); // 放这一行，递归处理下一行 // 不需要显式“撤销”，下一次循环会覆盖queens[row] } } }

你注意观察，这里的递归结构和前面阶乘完全一样：有边界条件（放满一行），有递归调用（处理下一行），规模在递减（行数在增加）。唯一的区别是，它在一个for循环里做了多次递归尝试，每次尝试都代表一种可能性。这就是递归从“求值”到“搜索”的转折。

5.3 为什么说“能用递归解决的题，往往也能用递归深刻理解”

我教了这么多年程序设计的经验是：递归不只是编程技巧，它更是一种对问题结构进行抽象的能力。你写递归的过程，其实是逼迫自己去回答一个问题：“这个问题能不能拆成更小的自己？”

会拆，代码就自然写出来了；不会拆，背十遍代码也没用。像汉诺塔、八皇后、二叉树遍历、快速排序、归并排序，这些都是“结构上天然递归”的问题，你用递归理解它们，比背代码强得多。

所以我的建议是：每看到一个可以用递归解决的问题，先别看题解，自己在纸上画一画“这个问题凭什么能拆小”。画出来了，代码就是三步法的事；画不出来，说明你还没吃透问题本身。

我自己带过的学生里，有不少人就是靠这个方法，从“递归恐惧症”变成“递归真香”的。他们后来刷动态规划题时，往往也更快上手——因为动态规划本质上就是在递归的基础上加了一个“备忘录用”，你递归底子好，转DP就是顺水推舟的事。

说句题外话，期末考试前我会让学生专门练三道题：汉诺塔、八皇后、二叉树遍历。把这三题的递归写法烂熟于心，递归这一章基本就拿下了。如果你现在正被递归折磨，不妨也按这个路子来——别急，递归这个东西，真的就是一层窗户纸，捅破一次，以后就再也不怕了。