C 递归（长文讲解）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

递归的定义与核心思想

递归（Recursion）是一种在函数定义中直接或间接调用自身的技术。在 C 语言中，递归通过函数自身作为子程序被调用来实现特定功能。其核心思想可以比喻为“解决问题的分治策略”：将复杂问题拆解为更小的、相似的子问题，直到问题规模缩小到可以直接解决的基例（Base Case）。

递归的两个关键要素：

1. 基例：递归终止的条件，避免无限循环。
2. 递归步骤：将问题分解为更小的子问题，并通过递归调用解决这些子问题。

递归的结构解析

基例与递归步骤的协作关系

基例是递归的“安全网”，确保递归最终能够退出。例如，计算阶乘时，当输入为 0 或 1 时，函数直接返回 1，这就是基例。而递归步骤则通过缩小问题规模来逼近基例。

示例：阶乘的递归实现

#include <stdio.h>  

int factorial(int n) {  
    if (n == 0 || n == 1) {  
        return 1; // 基例  
    }  
    return n * factorial(n - 1); // 递归步骤  
}  

int main() {  
    int num = 5;  
    printf("Factorial of %d is %d\n", num, factorial(num));  
    return 0;  
}  

在这个例子中，factorial(5) 的计算过程可以拆解为：
5 * factorial(4) → 5 * 4 * factorial(3) → ... → 5 * 4 * 3 * 2 * 1。

递归的执行机制

C 语言通过函数调用栈管理递归调用。每次函数调用会将参数、返回地址等信息压入栈中。当递归调用到达基例后，栈开始逐层弹出，计算最终结果。

比喻：递归如同“楼梯的攀登与返回”

想象你站在楼梯的第 n 级，要到达第 0 级。每次递归调用相当于向下走一级（n-1），直到到达第 0 级（基例）。此时，你开始逐级返回，计算每一步的值。

递归的常见应用场景

场景一：数学问题

递归天然适合解决数学问题，如斐波那契数列、幂运算等。

示例：斐波那契数列

斐波那契数列的定义为：F(n) = F(n-1) + F(n-2)，基例为 F(0)=0，F(1)=1。

int fibonacci(int n) {  
    if (n <= 1) {  
        return n; // 基例  
    }  
    return fibonacci(n-1) + fibonacci(n-2); // 递归步骤  
}  

场景二：数据结构操作

递归在树、图等数据结构的遍历中应用广泛。例如，二叉树的前序、中序、后序遍历通常通过递归实现。

示例：二叉树的前序遍历

struct Node {  
    int data;  
    struct Node* left;  
    struct Node* right;  
};  

void pre_order(struct Node* node) {  
    if (node == NULL) {  
        return; // 基例  
    }  
    printf("%d ", node->data);  
    pre_order(node->left); // 左子树递归  
    pre_order(node->right); // 右子树递归  
}  

场景三：分治算法

分治算法（Divide and Conquer）的核心思想是将问题划分为多个子问题，递归解决后再合并结果。快速排序和归并排序都是典型应用。

示例：快速排序的递归实现

void quick_sort(int arr[], int low, int high) {  
    if (low < high) {  
        int pivot = partition(arr, low, high); // 分区操作  
        quick_sort(arr, low, pivot - 1); // 左半部分递归  
        quick_sort(arr, pivot + 1, high); // 右半部分递归  
    }  
}  

递归的注意事项与优化

问题一：栈溢出（Stack Overflow）

递归层级过深可能导致栈内存不足。例如，计算 fibonacci(40) 时，递归调用次数呈指数级增长，容易引发栈溢出。

解决方案：

1. 限制递归深度：确保问题规模在合理范围内。
2. 尾递归优化：将递归调用转化为尾递归形式，允许编译器优化栈空间。

尾递归示例：阶乘的优化版本

int factorial_tail(int n, int acc) {  
    if (n == 0) {  
        return acc; // 基例  
    }  
    return factorial_tail(n - 1, acc * n); // 尾递归调用  
}  

int factorial(int n) {  
    return factorial_tail(n, 1);  
}  

问题二：性能问题

递归可能导致重复计算（如斐波那契数列的朴素递归实现），此时可通过记忆化（Memoization） 或改用迭代方法优化。

记忆化示例：斐波那契数列优化

#include <stdlib.h>  

int memo[100]; // 假设 n ≤ 99  

int fibonacci_memo(int n) {  
    if (n <= 1) {  
        return n;  
    }  
    if (memo[n] != -1) {  
        return memo[n]; // 直接返回已计算值  
    }  
    memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2);  
    return memo[n];  
}  

int main() {  
    for (int i = 0; i < 100; i++) {  
        memo[i] = -1; // 初始化为未计算状态  
    }  
    printf("%d\n", fibonacci_memo(40));  
    return 0;  
}  

问题三：递归与循环的权衡

递归代码通常比循环更简洁，但可能牺牲效率。在性能敏感的场景（如大规模数据处理），应优先考虑循环或尾递归优化。

对比：阶乘的递归与循环实现

递归的经典问题与进阶案例

案例一：汉诺塔问题

汉诺塔（Tower of Hanoi）是递归的经典问题。目标是将 n 个盘子从源柱移动到目标柱，规则为每次只能移动一个盘子，且大盘不能叠在小盘上。

递归解法分析：

1. 将前 n-1 个盘子从源柱移动到辅助柱。
2. 将第 n 个盘子从源柱移动到目标柱。
3. 将 n-1 个盘子从辅助柱移动到目标柱。

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); // 步骤 1  
    printf("Move disk %d from %c to %c\n", n, from, to); // 步骤 2  
    hanoi(n-1, aux, to, from); // 步骤 3  
}  

案例二：树的深度优先搜索（DFS）

在二叉树的深度优先遍历中，递归实现代码简洁且直观。

void in_order(struct Node* node) {  
    if (node == NULL) {  
        return; // 基例  
    }  
    in_order(node->left); // 左子树  
    printf("%d ", node->data); // 访问当前节点  
    in_order(node->right); // 右子树  
}  

递归的调试与调试技巧

调试难点

由于递归调用栈的多层嵌套，调试时可能难以追踪变量状态。

调试建议：

1. 打印调试信息：在函数入口和出口处添加 printf，观察参数变化。
2. 逐步执行：使用调试器逐步单步执行，观察函数调用栈的变化。
3. 断言验证：在基例处添加断言，确保参数符合预期。

示例：调试阶乘函数

#include <assert.h>  

int factorial(int n) {  
    assert(n >= 0); // 断言 n 非负  
    if (n == 0) {  
        return 1;  
    }  
    printf("Computing factorial(%d)\n", n); // 调试信息  
    return n * factorial(n - 1);  
}  

结论

递归是 C 语言中一种强大的编程技术，尤其适用于分治、树结构操作和数学问题。通过合理设计基例和递归步骤，开发者可以编写出简洁高效的代码。然而，递归也存在性能和栈溢出的风险，需结合问题特点选择合适的应用场景。

对于编程初学者，建议从简单问题（如阶乘、斐波那契数列）入手，逐步过渡到复杂场景（如汉诺塔、树遍历）。通过实践和调试，掌握递归的执行机制与优化方法，最终能够灵活运用这一技术解决实际问题。

在学习过程中，保持对“分而治之”思想的理解，结合代码示例反复练习，逐步构建对递归的直观认知。随着经验积累，递归将成为你工具箱中不可或缺的利器。