C 语言（五）｜递归：从函数自调用到问题拆解
详细介绍递归的核心逻辑、执行过程、编写步骤和实战案例，帮助你从基础理解递归思想。
版权声明：本文为作者原创，版权归作者所有。如需转载或引用，请联系作者获得授权，并在使用时注明出处。
一、什么是递归？
学到指针后回头复习递归，初学留下的诸多困惑竟慢慢通透。递归作为编程基础且易绕晕的知识点，是后续学习的基石，也是新手入门的"小难关"—— 初学时常陷入"栈溢出""逻辑绕圈""不知如何终止"的误区，对着简单阶乘代码也需反复琢磨；如今掌握指针基础，回头再看递归，发现无需复杂内容，也能将其学扎实。
本文以"回头复习"的视角，避开数据结构相关深层内容，仅围绕基础知识点，从定义、核心条件、执行过程、编写步骤，到基础实战案例、避坑技巧层层拆解递归，分享从"模糊理解"到"扎实掌握"的复习过程，帮和我一样学到指针后回头复习递归的小伙伴少走弯路、吃透基础。
核心不是"自调用"，而是"分治思想 + 调用栈机制"。简单来说：把一个复杂的大问题，拆解成和原问题结构相同、但规模更小的子问题，一直拆解到子问题简单到可以直接解决（终止条件），再通过子问题的解，反向推导原问题的解。
用两个通俗比喻理解递归：
- 查字典：查陌生词可能需要先查关联词，直到查到熟悉的基础词，再回头理解原词
- 俄罗斯套娃：从最外层大娃一层一层拆到最小娃，再一层一层套回去，才算完成整个过程
二、递归的两个"硬性条件"：缺一不可
所有正确的递归函数，都必须满足两个缺一不可的硬性条件，这是新手入门和回头复习都要牢记的基础。
2.1 终止条件（Base Case）
递归的"出口"，也是现在写递归函数最先考虑的部分。指当子问题的规模缩小到一定程度，不需要再递归调用自身，就能直接返回结果的条件。
核心坑点 & 注意：终止条件必须可达到，若递推过程中永远触达不到终止条件，会陷入无限递归最终导致栈溢出—— 这和写指针代码时忘记判断指针为空（NULL）的隐患相似，都是"没留出口"的问题。
2.2 递推关系（Recursive Case）
"如何拆解问题"的核心，是连接原问题和子问题的桥梁—— 将原问题拆解为一个或多个规模更小、结构与原问题一致的子问题，且子问题的解能通过一定逻辑推导得出原问题的解。
核心要求：每次递归调用，问题的规模必须严格缩小。比如求阶乘时f(n) = n * f(n-1)，将f(n)拆解为f(n-1)，规模从n缩小到n-1。
三、递归的执行过程："递下去，归回来"
递归的执行过程是"递下去，归回来"的两步走，底层是依赖函数调用栈的压入和弹出，无需复杂概念，记住这两步即可。
3.1 递（向下拆解）
调用递归函数时，函数会不断调用自身，将大问题拆成小问题，此过程为"递"。关键特点："递"的过程中函数不返回任何结果，仅将每次的函数调用信息（入参、局部变量等）压入函数调用栈，直到触达终止条件，"递"才停止。
3.2 归（向上回溯）
触达终止条件后，函数开始返回结果，此过程为"归"。执行逻辑：从终止条件对应的子问题开始，依次将结果返回给上层调用函数；上层函数利用子问题的结果计算自身结果，再继续向上返回，直到回到最开始的原问题调用，完成整个计算。
3.3 递归执行过程详解：阶乘为例
以最经典的递归函数——阶乘为例，通过实例和图解拆解递归的执行过程，帮助理解"递"和"归"：
#include <stdio.h>
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
printf("%d\n", factorial(5));
return 0;
}图解递归调用过程（以factorial(5)为例）：
递阶段（压栈）：
factorial(5) → n=5, 调用factorial(4), 等待factorial(4)结果
factorial(4) → n=4, 调用factorial(3), 等待factorial(3)结果
factorial(3) → n=3, 调用factorial(2), 等待factorial(2)结果
factorial(2) → n=2, 调用factorial(1), 等待factorial(1)结果
factorial(1) → n=1, 终止条件触发，返回1
归阶段（弹栈）：
factorial(1) 返回 1
factorial(2) 接收到 1, 计算 2*1=2, 返回 2
factorial(3) 接收到 2, 计算 3*2=6, 返回 6
factorial(4) 接收到 6, 计算 4*6=24, 返回 24
factorial(5) 接收到 24, 计算 5*24=120, 返回 120运行结果：120
四、递归的编写步骤：三步走策略
4.1 第一步：确定函数功能
明确函数要解决什么问题，比如阶乘函数factorial(n)就是求n的阶乘。
4.2 第二步：确定终止条件
找到最简单、最基础、可以直接返回结果的子问题。求阶乘时，n=1时直接返回1。
4.3 第三步：确定递推关系
找到原问题和子问题之间的关系，即如何通过子问题的解得到原问题的解。求阶乘时，f(n) = n * f(n-1)。
4.4 编写模板
返回值类型 函数名(参数) {
// 第一步：确定终止条件（Base Case）
if (最简单情况) {
return 简单结果;
}
// 第二步：确定递推关系（Recursive Case）
// 假设子问题的函数已经能正确解决子问题
return 原问题与子问题的关系;
}五、递归 vs 迭代：对比与选择
5.1 核心区别
| 特性 | 递归 | 迭代 |
|---|---|---|
| 实现方式 | 函数调用自身 | 循环结构 |
| 内存使用 | 调用栈占用大 | 占用的内存相对较小 |
| 代码简洁性 | 代码更简洁、更易理解 | 代码相对繁琐 |
| 执行效率 | 有函数调用开销 | 通常比递归效率高 |
5.2 什么时候用递归？
适合使用递归的场景：
- 问题可以分解为相似的子问题（如分治、树形结构）
- 问题本身具有递归特性（如阶乘、斐波那契数列）
- 需要保存调用状态（如汉诺塔、迷宫问题）
不适合使用递归的场景：
- 递归层次过深（如求1+2+...+1000000的和），可能导致栈溢出
- 对性能要求极高的场景，递归有函数调用开销
5.3 递归求斐波那契数列
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
for (int i = 0; i < 10; i++) {
printf("%d ", fibonacci(i));
}
return 0;
}运行结果：0 1 1 2 3 5 8 13 21 34
六、递归实战案例
6.1 案例一：求数组元素之和（结合指针）
结合刚学的指针，既能巩固递归，又能复习指针基础用法：
#include <stdio.h>
// 结合指针的数组求和递归函数
int sum_array(int *arr, int len) {
// 终止条件：指针为空或长度为0，返回0
if (arr == NULL || len == 0) {
return 0;
}
// 递推关系：当前元素 + 剩余元素和（指针后移，长度减1）
return *arr + sum_array(arr + 1, len - 1);
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int len = sizeof(arr) / sizeof(arr[0]); // 计算数组实际长度
printf("数组元素的和是：%d\n", sum_array(arr, len)); // 输出：15
return 0;
}运行结果：15
6.2 案例二：顺序打印整数的每一位
常规取余/除法会得到倒序结果，利用递归"先递后归"的特性，可直接实现顺序打印：
#include <stdio.h>
// 顺序打印整数的每一位（处理正整数，负数可先取绝对值）
void print_num(int n) {
// 终止条件：只有一位数，直接打印
if (n > 9) {
print_num(n / 10); // 递：去掉最后一位，继续递归
}
// 归：打印当前最后一位
printf("%d ", n % 10);
}
int main() {
int n;
printf("请输入一个整数：");
scanf("%d", &n);
// 处理负数：先打印负号，再取绝对值打印
if (n < 0) {
printf("-");
n = -n;
}
print_num(n); // 示例输入123，输出：1 2 3
return 0;
}运行结果：输入123，输出：1 2 3
6.3 案例三：字符串逆序输出
#include <stdio.h>
void reverse_string(char *str) {
if (*str == '\0') {
return;
}
reverse_string(str + 1);
printf("%c", *str);
}
int main() {
char str[] = "Hello";
reverse_string(str);
printf("\n");
return 0;
}运行结果：olleH
6.4 案例四：计算数值的位数
#include <stdio.h>
int count_digits(int n) {
if (n / 10 == 0) {
return 1;
}
return 1 + count_digits(n / 10);
}
int main() {
printf("%d\n", count_digits(12345));
return 0;
}运行结果：5
6.5 案例五：求最大公约数（辗转相除法）
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
printf("%d\n", gcd(24, 18));
return 0;
}运行结果：6
6.6 案例六：斐波那契数列（递归版与迭代版对比）
递归版（存在重复计算问题）：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
// 斐波那契数递归函数
long long Fib(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
// 递推关系：存在大量重复计算
return Fib(n - 1) + Fib(n - 2);
}
}
int main() {
int n;
printf("请输入非负整数n：");
scanf("%d", &n);
if (n < 0) {
printf("错误：请输入非负整数！\n");
return 1;
}
long long num = Fib(n);
printf("第%d个斐波那契数为：%lld\n", n, num);
return 0;
}迭代版（优化重复计算问题）：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
// 斐波那契数迭代版（无重复计算，效率高）
long long Fib_iter(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
long long a = 0; // F0
long long b = 1; // F1
long long c = 0; // 保存当前项
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
int main() {
int n;
printf("请输入非负整数n：");
scanf("%d", &n);
if (n < 0) {
printf("错误：请输入非负整数！\n");
return 1;
}
long long num = Fib_iter(n);
printf("第%d个斐波那契数为：%lld\n", n, num);
return 0;
}6.7 案例七：青蛙跳台阶问题
一只青蛙要跳上 n 级台阶，每次只能跳 1 级或 2 级台阶，问跳上 n 级台阶一共有多少种不同的跳法？
#include <stdio.h>
// 青蛙跳台阶递归版（基础版，存在重复计算，n不宜过大）
long long jump_step(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
return jump_step(n - 1) + jump_step(n - 2);
}
}
int main() {
int n;
printf("请输入台阶数（正整数）：");
scanf("%d", &n);
if (n < 1) {
printf("错误：台阶数需为正整数！\n");
return 1;
}
long long num = jump_step(n);
printf("跳上%d级台阶共有%lld种跳法\n", n, num);
return 0;
}七、递归常见错误与调试技巧
7.1 常见错误
错误1：忘记终止条件，导致无限递归
// 错误示例：没有终止条件，会无限递归直到栈溢出
int factorial(int n) {
return n * factorial(n - 1); // 缺少终止条件
}错误2：终止条件永远无法达到
// 错误示例：终止条件无法达到，无限递归
int sum(int n) {
if (n >= 1) {
return n + sum(n + 1); // n越来越大，永远到不了n<=0
}
}错误3：递归层次过深
// 错误示例：递归层次太深会导致栈溢出
int sum_1_to_n(int n) {
if (n == 1) return 1;
return n + sum_1_to_n(n - 1);
}
// 对于n=100000，会递归100000层，可能栈溢出7.2 调试技巧
技巧1：使用printf打印递归过程
#include <stdio.h>
int factorial(int n) {
printf("调用factorial(%d)\n", n);
if (n <= 1) {
printf("factorial(%d)返回1\n", n);
return 1;
}
int result = n * factorial(n - 1);
printf("factorial(%d)返回%d\n", n, result);
return result;
}技巧2：限制递归深度
#include <stdio.h>
int factorial(int n, int depth) {
if (depth > 1000) { // 设置最大递归深度
printf("递归过深，可能栈溢出！\n");
return -1;
}
if (n <= 1) return 1;
return n * factorial(n - 1, depth + 1);
}八、汉诺塔问题（经典递归）
8.1 问题描述
有三根柱子A、B、C，柱子A上有n个大小不同的圆盘（大盘在下，小盘在上）。现在要把所有圆盘从柱子A移动到柱子C，要求：
- 每次只能移动一个圆盘
- 大盘不能放在小盘上面
- 可以利用柱子B作为辅助
8.2 思路分析
当n=1时，直接移动即可。 当n>1时，分三步：
- 将n-1个圆盘从A移动到B（以C为辅助）
- 将第n个圆盘（最大的）从A移动到C
- 将n-1个圆盘从B移动到C（以A为辅助）
8.3 代码实现
#include <stdio.h>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("将第1个圆盘从%c移动到%c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to);
printf("将第%d个圆盘从%c移动到%c\n", n, from, to);
hanoi(n - 1, aux, to, from);
}
int main() {
int n = 3;
printf("将%d个圆盘从A移动到C的步骤：\n", n);
hanoi(n, 'A', 'C', 'B');
return 0;
}8.4 运行结果
将3个圆盘从A移动到C的步骤：
将第1个圆盘从A移动到B
将第2个圆盘从A移动到C
将第1个圆盘从B移动到C
将第3个圆盘从A移动到C
将第1个圆盘从A移动到B
将第2个圆盘从B移动到C
将第1个圆盘从A移动到C九、总结
本篇我们学习了C语言递归的核心知识：
- 递归的核心定义：自己调用自己，拆解问题、回溯求解，底层依赖函数调用栈
- 递归的两个必要条件：终止条件（Base Case）和递推关系（Recursive Case）
- 递归的执行过程："递下去"压栈，"归回来"弹栈
- 递归的编写步骤：确定函数功能 → 确定终止条件 → 确定递推关系
- 递归vs迭代：根据问题特点选择合适的实现方式
- 实战案例：阶乘、斐波那契数列、汉诺塔等经典问题
递归和指针一样，都是"化繁为简"的思路。指针通过地址直接操作数据、简化代码，递归通过拆解问题、简化复杂逻辑。掌握递归的核心思想，能为后续学习数据结构（如树、图）打下坚实基础！