c语言程序设计使用递归的方法-C语言-盈思创科技

什么是递归？

递归的定义：一个函数在其内部直接或间接地调用自身。

（图片来源网络，侵删）

就像“照镜子”：你拿着一面镜子，镜子里反射出你拿着另一面镜子，而那面镜子里又反射出你拿着第三面镜子……这个过程就是一个无限递归，在程序中，我们需要一个“出口”来终止这个过程。

递归的核心要素

一个有效的递归函数必须满足两个关键条件：

基本情况 / 终止条件
- 这是递归的“出口”，当问题规模缩小到可以直接解决时，递归停止。
- 如果没有终止条件,递归将无限进行下去，最终导致栈溢出，程序崩溃。
- 计算 n! (n的阶乘) 时，当 n 为 0 或 1 时，结果就是 1，这就是基本情况。
递归情况
（图片来源网络，侵删）
- 函数调用自身,处理一个更小的子问题。
- 递归调用必须朝着“基本情况”的方向发展，即每次调用时，问题的规模都应该减小。
- 计算 n! 时，可以将其分解为 n * (n-1)!，这里 (n-1)! 就是规模更小的子问题。

递归的执行过程可以想象成一个“调用栈”： 每次函数调用自身时，系统都会为新的函数调用创建一个新的“栈帧”，保存其参数、局部变量和返回地址，当遇到基本情况返回时，再依次弹出栈帧，计算最终结果。

C语言递归程序示例

下面通过几个经典的例子来理解递归的实现。

示例1：计算阶乘

阶乘的数学定义：

n! = n * (n-1)! (当 n > 1 时)
0! = 1 (基本情况)

C语言代码：

#include <stdio.h>
// 函数声明
long factorial(int n);
int main() {
    int num;
    printf("请输入一个非负整数: ");
    scanf("%d", &num);
    if (num < 0) {
        printf("错误：请输入一个非负整数，\n");
    } else {
        printf("%d 的阶乘是: %ld\n", num, factorial(num));
    }
    return 0;
}
// 递归函数定义
long factorial(int n) {
    // 1. 基本情况 / 终止条件
    if (n == 0 || n == 1) {
        return 1;
    }
    // 2. 递归情况
    else {
        return n * factorial(n - 1); // 调用自身，处理更小的子问题
    }
}

执行流程分析 (以 factorial(3) 为例):

main 调用 factorial(3)。
factorial(3) 判断 n 不为 0 或 1，于是执行 return 3 * factorial(2)。
- factorial(3) 等待 factorial(2) 的结果，并暂停执行。
factorial(2) 被调用，它判断 n 不为 0 或 1，于是执行 return 2 * factorial(1)。
- factorial(2) 等待 factorial(1) 的结果，并暂停执行。
factorial(1) 被调用，它判断 n 为 1，符合基本情况，return 1。
factorial(1) 执行完毕，返回结果 1。
factorial(2) 得到 factorial(1) 的结果 1，计算 2 * 1，得到 2，然后返回 2。
factorial(3) 得到 factorial(2) 的结果 2，计算 3 * 2，得到 6，然后返回 6。
main 函数得到最终结果 6。

示例2：斐波那契数列

斐波那契数列的定义：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (当 n > 1 时)

C语言代码：

#include <stdio.h>
// 函数声明
int fibonacci(int n);
int main() {
    int n;
    printf("请输入要计算的斐波那契数列项数: ");
    scanf("%d", &n);
    if (n < 0) {
        printf("错误：请输入一个非负整数，\n");
    } else {
        printf("斐波那契数列的第 %d 项是: %d\n", n, fibonacci(n));
    }
    return 0;
}
// 递归函数定义
int fibonacci(int n) {
    // 1. 基本情况
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    // 2. 递归情况
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

注意：这个斐波那契的递归解法虽然直观，但效率极低，因为它会重复计算很多值（例如计算 fib(5) 时，fib(3) 会被计算两次），在实际应用中，通常会使用迭代法或“记忆化递归”来优化。

示例3：字符串反转

这个例子展示了递归在数据处理上的应用。

思路：

基本情况：如果字符串为空（长度为0）或只有一个字符，它本身就是反转后的结果。
递归情况：将字符串的第一个字符移动到末尾，然后递归地反转剩余的子字符串。
- reverse_string(s) = reverse_string(s+1) + s[0]

C语言代码：

#include <stdio.h>
#include <string.h>
// 函数声明
void reverseString(char *str);
int main() {
    char str[100];
    printf("请输入一个字符串: ");
    fgets(str, sizeof(str), stdin); // 使用fgets安全地读取字符串
    // 去掉fgets可能读取的换行符
    str[strcspn(str, "\n")] = 0;
    printf("原始字符串: %s\n", str);
    reverseString(str);
    printf("反转后的字符串: %s\n", str);
    return 0;
}
// 递归函数定义
void reverseString(char *str) {
    // 1. 基本情况
    // 如果指针指向空字符 '\0'，或者只有一个字符（下一个就是'\0'），则停止
    if (*str == '\0' || *(str + 1) == '\0') {
        return;
    }
    // 2. 递归情况
    // 递归处理子字符串，从第二个字符开始
    reverseString(str + 1);
    // 递归返回后，进行交换
    // 保存第一个字符
    char first_char = *str;
    // 将子字符串的最后一个字符（即原字符串的第二个字符）移动到开头
    *str = *(str + strlen(str) - 1);
    // 将保存的第一个字符放到子字符串的末尾
    *(str + strlen(str) - 1) = first_char;
}

递归的优缺点

优点

代码简洁、可读性强：对于某些问题（如树的遍历、图的搜索），递归的实现方式非常自然、优雅，代码量远少于迭代法。
问题分解清晰：递归强制你思考问题的分解方式，将大问题拆解成小问题，符合分治算法的思想。

缺点

性能开销大：每次函数调用都需要在调用栈上分配空间、保存上下文，这个过程比简单的循环要慢得多。
栈空间消耗：递归的深度受限于系统的栈大小，如果递归层次太深（例如计算 factorial(50000)），很容易导致栈溢出。
调试困难：递归的调用链比较复杂，调试时跟踪变量和流程不如迭代直观。

何时使用递归？

使用递归的场景：

问题本身是递归定义的：如阶乘、斐波那契、汉诺塔等。
数据结构是递归的：如树（二叉树、多叉树）和图，树的遍历（前序、中序、后序）、深度优先搜索等用递归实现极为方便。
代码清晰度和可维护性比性能更重要，且递归深度可控时。

避免使用递归的场景：

对性能要求极高的场景：如高频交易、游戏引擎核心循环等。
问题规模不确定且可能非常大：容易导致栈溢出。
可以用简单的迭代高效解决的问题：如简单的数组求和、遍历等。

递归是C语言程序设计中一个强大的工具,它将复杂的问题分解为简单的、可管理的子问题，掌握递归的关键在于：

找到问题的递归定义。
明确地定义基本情况（递归出口）。
确保递归调用能够向基本情况逼近。

通过大量的练习,你会逐渐培养出递归思维，能够识别出哪些问题适合用递归来解决，并写出高效、优雅的递归代码。

c语言程序设计使用递归的方法

什么是递归？

递归的核心要素

C语言递归程序示例

示例1：计算阶乘

示例2：斐波那契数列

示例3：字符串反转

递归的优缺点

优点

缺点

何时使用递归？

相关文章

目录[+]