30 C 语言递归算法详解：基准条件、递归逻辑、循环对比、经典案例（斐波那契、猴子吃桃、汉诺塔、二分查找等）

1 递归概述

        在 C 语言中，递归是一种函数直接或间接调用自身的技术，特别适合解决可分解为结构相同但规模更小的子问题。递归通过将复杂问题逐步转化为更简单的子问题，最终达到可直接求解的基准情况（终止条件）来返回结果。

关键注意事项：

• 必须确保递归能正确终止（避免无限递归）。
• 每次递归调用必须缩小问题规模（向基准情况靠近）。
• 设计不当可能导致栈溢出或性能问题。

2 递归构成要素

2.1 基准情况

• 定义：基准情况（Base Case）是递归函数中无需进一步递归即可直接返回结果的终止条件，它代表了问题可以被直接求解的最简单形式。
• 关键作用：
  • 作为递归的出口，防止函数无限调用自身导致栈溢出。
  • 确保递归过程最终能够停止。
• 设计要点：
  • 必须明确且可验证（如 n == 0 或 n == 1）。
  • 每个递归函数至少需要一个基准情况。
  • 基准情况的结果应是已知的、可直接返回的。
• 示例：在阶乘计算中，0! = 1 和 1! = 1 是基准情况，此时函数直接返回 1 而无需继续递归。

2.2 递归步骤

• 定义：递归步骤（Recursive Step）是函数通过调用自身来分解问题并解决更小规模子问题的过程。
• 关键要求：
  • 问题规模必须减小：每次递归调用都应使问题更接近基准情况。
  • 最终会达到基准情况：递归链必须能终止于某个基准情况。
  • 保持正确性：递归步骤的数学定义必须与问题本质一致。
• 设计要点：
  • 递归调用必须缩小参数范围（如 n 变为 n-1）。
  • 递归结果应能正确组合（如 n * factorial(n-1)）。
  • 避免重复计算（可通过记忆化等技术优化）。
• 示例：阶乘函数的递归步骤 factorial(n) = n * factorial(n-1)：
  • 所有递归调用的结果最终组合为最终答案。
  • 当 n 减到 0 或 1 时触发基准情况。
  • 每次调用将 n 减 1，问题规模逐步减小。

2.3 案例：阶乘计算

循环实现

#include <stdio.h>

// 循环方式计算阶乘
int factorial(int n)
{
    int result = 1; // 初始化结果为 1（0! 和 1! 的基准值）

    for (int i = 2; i <= n; i++)
    {
        result *= i; // 累乘计算阶乘
    }
    
    return result;
}

int main()
{
    int number;
    printf("请输入非负整数：");
    scanf("%d", &number);

    if (number >= 0)
    {
        printf("%d! = %d\n", number, factorial(number));
    }
    else
    {
        printf("错误：负数无阶乘定义\n");
    }

    return 0;
}

递归实现

#include <stdio.h>

// 递归方式计算阶乘
long factorial(int n)
{
    // 基准情况：0! 和 1! 直接返回 1
    if (n <= 1)
        return 1;

    // 递归步骤：n! = n * (n-1)!
    return n * factorial(n - 1);
}

int main()
{
    int number;
    printf("请输入非负整数：");
    scanf("%d", &number);

    if (number >= 0)
    {
        printf("%d! = %ld\n", number, factorial(number));
    }
    else
    {
        printf("错误：负数无阶乘定义\n");
    }

    return 0;
}

        程序在 VS Code 中的多次运行结果如下所示：

        递归调用过程分析（以 factorial(5) 为例）：

递归展开：
factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * 4 * (3 * factorial(2))
= 5 * 4 * 3 * (2 * factorial(1))
= 5 * 4 * 3 * 2 * 1  // 触发基准情况
= 120

差异对比

3 递归特性

3.1 自我调用

        递归函数的核心特性是在其函数体内直接或间接调用自身。这种自我调用（Self-Invocation）的机制使得函数能够将复杂问题分解为更小的同类问题，直到达到可直接解决的基准情况。

• 关键点：
  • 每次递归调用都处理问题的更小实例。
  • 必须存在明确的递归终止条件（基准情况）。
  • 递归深度直接影响性能和资源消耗。

3.2 栈机制

        在 C 语言等大多数编程语言中，递归调用通过调用栈（call stack）实现。

        每次递归调用创建一个新的栈帧（stack frame），存储：局部变量、函数参数、返回地址。

        栈帧按后进先出（LIFO）原则管理，递归返回时，栈帧依次弹出，实现回溯。

• 示例风险：
  • 深层递归可能导致栈溢出（stack overflow）。
  • 典型栈大小限制（通常几 MB 到 几十 MB）。

3.3 问题分解

        递归的本质是将问题逐步分解为更简单的同类问题：

1. 分解策略：将原问题转化为一个或多个子问题。
2. 终止条件：当子问题达到足够简单程度时直接解决。
3. 结果组合：将子问题的解合并为原问题的解。

• 设计原则：
  • 确保每次递归都向基准情况靠近。
  • 保持子问题与原问题的同构性。
  • 避免重复计算（可通过记忆化优化）。

3.4 性能考量

• 递归的优势与代价：
  • 优势：
    • 代码简洁，接近数学定义。
    • 适合分治、树形结构等问题。
  • 代价：
    • 函数调用开销（参数传递、栈操作等）。
    • 栈空间消耗（与递归深度成正比）。
    • 潜在重复计算（如朴素斐波那契实现）。
• 优化策略：
  • 尾递归优化（如编译器支持）。
  • 记忆化（Memoization）技术。
  • 必要时转换为迭代实现。

3.5 案例：递归回溯

#include <stdio.h>

// 演示递归调用栈行为的函数
void recursive_trace(int n)
{
    printf("调用: %d\n", n); // 前序遍历打印

    if (n > 1)
    {
        recursive_trace(n - 1); // 递归调用
    }

    printf("返回: %d\n", n); // 后序遍历打印
}

int main()
{
    recursive_trace(3);

    return 0;
}

        程序在 VS Code 中的运行结果如下所示：

执行过程分析：

1. recursive_trace(3) 开始调用
   1. 输出：调用: 3
   2. 条件 3 > 1 成立，递归调用 recursive_trace(2)
   3. 本次调用挂起
2. recursive_trace(2) 开始调用
   1. 输出：调用: 2
   2. 条件 2 > 1 成立，递归调用 recursive_trace(1)
   3. 本次调用挂起
3. recursive_trace(1) 开始调用
   1. 输出：调用: 1
   2. 条件 1 > 1 不成立，不进行递归调用
   3. 输出：返回: 1（本次调用结束）
4. recursive_trace(2) 继续执行
   1. 递归调用 recursive_trace(1) 已结束
   2. 输出：返回: 2（本次调用结束）
5. recursive_trace(3) 继续执行
   1. 递归调用 recursive_trace(2) 已结束
   2. 输出：返回: 3（本次调用结束）

这个案例清晰地展示了：

• 递归调用的 "深入 - 回溯" 双阶段特性。
• 栈帧的压入（调用阶段）和弹出（返回阶段）顺序。
• 前序/后序打印的时间点差异。

关键结论：

• 递归函数的执行包含两个关键阶段：
  • 分解阶段：通过递归调用深入问题分解。
  • 组合阶段：在回溯过程中组合子问题的解。

4 递归与循环

4.1 主要区别

4.2 紧密联系

1. 功能互换性
   • 任何递归算法都可转换为循环实现（通过显式维护栈结构）。
   • 任何循环也可用递归模拟（但通常不推荐，除非语言不支持循环）。
2. 选择场景
   • 递归更优：
     • 问题具有自相似结构（如目录遍历、汉诺塔）。
     • 数学定义直接映射（如阶乘、斐波那契数列）。
   • 循环更优：
     • 迭代次数明确且性能敏感（如累加求和）。
     • 避免深层递归导致的栈溢出风险。
3. 混合使用
   • 复杂问题常结合两者：递归分解问题 + 循环处理子问题。
   • 现代优化：尾递归可被编译器优化为循环。

        总结：循环是显式的重复控制，递归是隐式的分解抽象；两者本质都是重复执行，选择时需权衡问题特性、性能需求和代码可维护性。

5 编程练习

5.1 斐波那契数列

        斐波那契数列是一个经典的数学序列，定义如下：

• 第 1 项：1
• 第 2 项：1
• 从第 3 项开始，每一项都等于前两项之和

        即数列形式为：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

        本程序要求用户输入一个正整数 n，然后输出斐波那契数列的第 n 项和前 n 项。提供两种实现方式：循环实现和递归实现。

循环实现：

#include <stdio.h>

// 函数声明：使用循环计算斐波那契数列的第 n 项
int fibonacci(int n);

int main()
{
    int n;
    printf("请输入一个正整数n(n≥1)，计算斐波那契数列的第n项及前n项: ");
    scanf("%d", &n);

    // 输入验证
    if (n < 1)
    {
        printf("错误：输入必须为正整数。\n");
        return 1; // 非正常退出
    }

    // 计算并输出第 n 项结果
    printf("\n斐波那契数列的第%d项是: %d\n", n, fibonacci(n));

    // 打印前 n 项
    printf("\n斐波那契数列的前%d项为：\n", n);
    for (int i = 1; i <= n; i++)
    {
        printf("F(%d) = %d%s", i, fibonacci(i), (i == n) ? "\n" : ", ");
    }

    return 0; // 正常退出
}

/**
 * 使用循环高效计算斐波那契数列的第 n 项
 * @param n 要计算的项数(n≥1)
 * @return 斐波那契数列的第 n 项值
 */
int fibonacci(int n)
{
    // 前两项直接返回 1
    if (n == 1 || n == 2)
    {
        return 1;
    }

    // 初始化前两项
    int prev_prev = 1; // 第 n-2 项
    int prev = 1;      // 第 n-1 项
    int current = 0;   // 当前项

    // 从第 3 项开始迭代计算
    for (int i = 3; i <= n; i++)
    {
        current = prev_prev + prev; // 当前项 = 前两项之和
        prev_prev = prev;           // 更新 n-2 项为原来的 n-1 项
        prev = current;             // 更新 n-1 项为当前计算的值
    }

    return current; // 返回计算结果
}

递归实现：

#include <stdio.h>

// 函数声明：使用递归计算斐波那契数列的第 n 项
int fib(int n);

int main()
{
    int n;
    printf("请输入一个正整数n(n≥1)，计算斐波那契数列的第n项及前n项: ");
    scanf("%d", &n);

    // 输入验证
    if (n < 1)
    {
        printf("错误：输入必须为正整数。\n");
        return 1; // 非正常退出
    }

    // 计算并输出第 n 项结果
    printf("\n斐波那契数列的第%d项是: %d\n", n, fib(n));

    // 打印前 n 项
    printf("\n斐波那契数列的前%d项为：\n", n);
    for (int i = 1; i <= n; i++)
    {
        printf("F(%d) = %d%s", i, fib(i), (i == n) ? "\n" : ", ");
    }

    return 0; // 正常退出
}

/**
 * 使用递归计算斐波那契数列的第 n 项
 * @param n 要计算的项数(n≥1)
 * @return 斐波那契数列的第 n 项值
 *
 * 注意：递归实现虽然代码简洁，但时间复杂度为 O(2^n)，
 * 当 n 较大时(如 n > 40 )性能会显著下降，不推荐用于实际生产环境。
 */
int fib(int n)
{
    // 基准情况：前两项返回 1
    if (n == 1 || n == 2)
    {
        return 1;
    }
    // 递归情况：F(n) = F(n-1) + F(n-2)
    else
    {
        return fib(n - 1) + fib(n - 2);
    }
}

        程序在 VS Code 中的运行结果如下所示：

5.2 猴子吃桃

        有一堆桃子，猴子每天会吃掉当前桃子数量的一半加一个。具体规则如下：

1. 每天早上，猴子会吃掉当前桃子数量的一半，然后再多吃一个。
2. 到第十天早上，猴子准备吃桃子时（注意：此时还没吃），发现只剩下 1 个桃子了。
3. 问：最初共有多少个桃子？

分析思路：

        这是一个典型的逆向思维问题。通常，正向思考是从初始数量开始，逐步计算每天剩下的桃子数量，直到第十天。但这里已知的是第十天早上的桃子数量，要求初始数量，因此更适合采用逆向思维，从第十天倒推回第一天。

正向规则：

逆向规则：

循环实现：

#include <stdio.h>

int main()
{
    int peaches = 1; // 第十天早上的桃子数量

    // 循环从第 10 天倒推到第 2 天（共 9 次循环）
    for (int day = 10; day > 1; day--)
    {
        peaches = 2 * (peaches + 1); // 根据递推关系计算前一天的桃子数量
    }
    printf("最初共有 %d 个桃子。\n", peaches); // 1534

    return 0;
}

递归实现：

#include <stdio.h>

// 递归函数：计算第 day 天的桃子数量
int calculatePeaches(int day)
{
    if (day == 10)
    {
        return 1; // 第十天早上的桃子数量为 1
    }
    else
    {
        return 2 * (calculatePeaches(day + 1) + 1); // 递推关系
    }
}

int main()
{
    int initialPeaches = calculatePeaches(1); // 从第 1 天开始计算
    printf("最初共有 %d 个桃子。\n", initialPeaches);

    return 0;
}

        程序在 VS Code 中的运行结果如下所示：

5.3 汉诺塔

        汉诺塔（Tower of Hanoi）是一个经典的递归问题，源于印度的一个古老传说。问题描述如下：

• 有三根柱子（通常标记为 A、B、C），以及一系列不同大小的圆盘。
• 初始时，所有圆盘按照大小顺序穿在柱子 A 上，且大的圆盘在下面，小的圆盘在上面。
• 目标是将所有圆盘从柱子 A 移动到柱子 C，同时满足以下规则：
  1. 每次只能移动一个圆盘。
  2. 在任何时候，较大的圆盘都不能放在较小的圆盘上面。
  3. 可以使用柱子 B 作为辅助柱子。

        递归是解决汉诺塔问题的经典方法。

#include <stdio.h>

// 递归函数：将 n 个圆盘从 from 柱移动到 to 柱，借助 aux 柱
void hanoi(int n, char from, char to, char aux);

int main()
{
    int n = 3; // 圆盘的数量
    printf("汉诺塔问题的解（递归）：\n");
    // 调用 hanoi 函数，将 n 个圆盘从柱子 A 移动到柱子 C，借助柱子 B
    hanoi(n, 'A', 'C', 'B');

    return 0;
}

/**
 * @brief 递归函数：将 n 个圆盘从 from 柱移动到 to 柱，借助 aux 柱
 * @param n 当前需要移动的圆盘数量
 * @param from 起始柱子（源柱子）
 * @param to 目标柱子
 * @param aux 辅助柱子
 */
void hanoi(int n, char from, char to, char aux)
{
    // 基本情况：如果只有一个圆盘，直接将其从 from 移动到 to
    if (n == 1)
    {
        printf("将圆盘 1 从 %c 移动到 %c\n", from, to);
    }
    else
    {
        // 递归步骤：
        // 1. 将 n-1 个圆盘从 from 柱移动到 aux 柱，借助 to 柱
        //    这样可以将上面的 n-1 个圆盘移开，以便移动最下面的第 n 个圆盘
        hanoi(n - 1, from, aux, to);

        // 2. 将第 n 个圆盘（最大的圆盘）从 from 柱移动到 to 柱
        //    因为此时 from 柱上只有第 n 个圆盘，所以可以直接移动
        printf("将圆盘 %d 从 %c 移动到 %c\n", n, from, to);

        // 3. 将 n-1 个圆盘从 aux 柱移动到 to 柱，借助 from 柱
        //    将之前移开的 n-1 个圆盘重新叠放到第 n 个圆盘上
        hanoi(n - 1, aux, to, from);
    }
}

        程序在 VS Code 中的运行结果如下所示：

5.4 最大公约数

        最大公约数（Greatest Common Divisor, GCD）是两个或多个整数共有的最大的那个正整数约数。欧几里得算法（也称为辗转相除法）是一种高效求解两个整数最大公约数的算法。其基本步骤如下：

1. 对于两个正整数 a 和 b（假设 a≥b）：
   • 计算 a 除以 b 的余数，记为 r（即 r=amodb）。
   • 如果 r = 0，则 b 就是 a 和 b 的最大公约数。
   • 如果 r ≠ 0，则将 b 的值赋给 a，将 r 的值赋给 b，然后重复上述步骤。
2. 这个过程会一直进行，直到余数为 0。此时，最后的非零除数就是两个数的最大公约数。

计算 98 和 56 的最大公约数（欧几里得算法）：

98 / 56 = 1……42（余数）
56 / 42 = 1……14（余数）
42 / 14 = 3……0（余数）

或者

56 / 98 = 0………56（余数）
98 / 56 = 1……42（余数）
56 / 42 = 1……14（余数）
42 / 14 = 3……0（余数）

所以 98 和 56 的最大公约数是 14

循环实现：

#include <stdio.h>

// 循环实现欧几里得算法
int gcd_iterative(int a, int b)
{
    while (b != 0)
    {
        int r = a % b; // 求余数
        a = b;         // 更新 a 为 b
        b = r;         // 更新 b 为余数
    }
    return a;
}

int main()
{
    int a, b;
    printf("请输入两个正整数：");
    scanf("%d %d", &a, &b);

    // 确保 a >= b（虽然不强制要求，但可以避免第一步的“无意义”交换）
    if (a < b)
    {
        // 交换 a 和 b
        int temp = a;
        a = b;
        b = temp;
    }

    int result = gcd_iterative(a, b);
    printf("%d 和 %d 的最大公约数是：%d\n", a, b, result);

    return 0;
}

递归实现：

#include <stdio.h>

/**
 * @brief 递归实现欧几里得算法，计算两个正整数的最大公约数（GCD）
 * @param a 第一个正整数
 * @param b 第二个正整数
 * @return 返回 a 和 b 的最大公约数
 */
int gcd_recursive(int a, int b)
{
    // 基本情况：如果 b 为 0，则 a 就是最大公约数
    if (b == 0)
    {
        return a;
    }
    else
    {
        // 递归情况：计算 gcd(b, a % b)
        // 欧几里得算法的核心思想：gcd(a, b) = gcd(b, a % b)
        // 通过不断用较小的数去除较大的数，直到余数为 0
        return gcd_recursive(b, a % b);
    }
}

int main()
{
    int a, b;
    printf("请输入两个正整数：");
    scanf("%d %d", &a, &b);

    // 确保 a >= b（虽然不强制要求，但可以避免第一步的“无意义”交换）
    if (a < b)
    {
        // 交换 a 和 b 的值
        int temp = a;
        a = b;
        b = temp;
    }

    // 调用递归函数计算最大公约数
    int result = gcd_recursive(a, b);
    // 输出结果
    printf("%d 和 %d 的最大公约数是：%d\n", a, b, result);

    return 0;
}

        程序在 VS Code 中的运行结果如下所示：

5.5 二分查找

        二分查找是一种高效的查找算法，适用于已排序的数组。其基本思想是通过不断将查找范围缩小一半，快速定位目标值。具体步骤如下：

1. 初始化查找范围为数组的整个区间（left = 0，right = n - 1，其中 n 是数组长度）。
2. 计算中间位置 mid = left + (right - left) / 2（避免直接 (left + right) / 2 可能导致的整数溢出）。
3. 比较中间元素 arr[mid] 和目标值 target：
   • 如果 arr[mid] == target，返回 mid（找到目标值）。
   • 如果 arr[mid] < target，说明目标值在右半部分，调整 left = mid + 1。
   • 如果 arr[mid] > target，说明目标值在左半部分，调整 right = mid - 1。
4. 重复上述步骤，直到 left > right（未找到目标值，返回 -1）。

循环实现：

#include <stdio.h>

/**
 * @brief 循环实现二分查找
 * @param arr 已排序的数组
 * @param n 数组长度
 * @param target 目标值
 * @return 目标值的索引（如果找到），否则返回 -1
 */
int binary_search_iterative(int arr[], int n, int target)
{
    int left = 0, right = n - 1; // 左右边界

    while (left <= right)
    {
        int mid = left + (right - left) / 2; // 防止溢出

        if (arr[mid] == target)
        {
            return mid; // 找到目标值
        }
        else if (arr[mid] < target)
        {
            left = mid + 1; // 右半部分
        }
        else
        {
            right = mid - 1; // 左半部分
        }
    }
    return -1; // 未找到
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 11, 13};  // 已排序的数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度
    int target = 7;                       // 目标值

    int result = binary_search_iterative(arr, n, target); // 调用二分查找函数

    if (result != -1)
    {
        printf("目标值 %d 的索引是：%d\n", target, result);
    }
    else
    {
        printf("未找到目标值 %d\n", target);
    }

    return 0;
}

递归实现：

#include <stdio.h>

/**
 * @brief 递归实现二分查找
 * @param arr 已排序的数组
 * @param left 当前查找范围的左边界
 * @param right 当前查找范围的右边界
 * @param target 目标值
 * @return 目标值的索引（如果找到），否则返回 -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, mid + 1, right, target); // 右半部分
    }
    else
    {
        return binary_search_recursive(arr, left, mid - 1, target); // 左半部分
    }
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 11, 13};  // 已排序的数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度
    int target = 7;                       // 目标值

    int result = binary_search_recursive(arr, 0, n - 1, target); // 调用递归函数

    if (result != -1)
    {
        printf("目标值 %d 的索引是：%d\n", target, result);
    }
    else
    {
        printf("未找到目标值 %d\n", target);
    }

    return 0;
}

        程序在 VS Code 中的运行结果如下所示：