【C语言】函数递归

Yue丶越

发布于 2025-12-17 16:33:45

2720

文章被收录于专栏：C语言C语言

前言：

在 C 语言函数学习之旅中，递归是一个绕不开的重要话题。它不仅是一种编程技巧，更是一种解决问题的独特思路。本文将从递归的基本概念出发，深入剖析其限制条件，通过实例演示递归的应用，并对比递归与迭代的优劣，帮助你彻底掌握 C 语言中的函数递归。

一、递归是什么？

递归，从字面意义上看，包含 “递” 和 “归” 两层含义。在 C 语言中，递归本质上是函数自己调用自己的一种行为，它将一个大型复杂的问题层层拆解为与原问题相似但规模更小的子问题，直到子问题无法再拆分，最终通过子问题的解逐步推导出原问题的解。

1.1递归的基本形式

#include <stdio.h>
int main()
{
    printf("hehe\n");
    main();// main函数中调用了main函数
    return 0;
}

这段代码中，main函数在自身内部调用了自己，符合于函数递归的定义。但需要注意的是，这段代码由于缺乏终止条件，最终会陷入死递归，导致栈溢出（Stack overflow）的错误，出现类似于以下的提示：

“0x7BF20907 (ucrtbased.d11)(test.exe 中) 处有未经处理的异常：0xC0000OP:Stack overflow (参数：0x00000000, 0x00602000)”

1.2 递归的核心思想

递归的核心思想是 “大事化小”。比如要解决一个复杂问题A，我们可以将其拆解为问题 B，问题 B 的解决方法与问题 A`相似但规模更小；接着再将问题 B 拆解为问题 C，以此类推，直到拆解出的子问题可以直接解决（即递归的终止条件），然后再从子问题的解逐步回归，得到原问题的解。

二、递归的限制条件

并非任意函数自己调用自己都能构成有效的递归，有效的递归必须满足两个必要条件，这两个条件缺一不可，否则就会出现死递归。

2.1 存在终止条件

递归必须存在一个明确的限制条件，当满足这个条件时，递归将不再继续。这个终止条件是递归能够正常结束的关键，它就像递归的 “刹车”，防止递归无限进行下去。

2.2 逐步接近终止条件

在每次递归调用过程中，函数的参数或状态必须逐渐接近递归的终止条件。也就是说，每一次递归调用都应该让问题的规模更小，使得问题一步步向可直接解决的方向靠近。

三、递归实例解析

论结合实践才能更好地理解递归，下面我们通过两个经典实例，详细的讲解一下递归的应用过程。

3.1 实例 1：求 n 的阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且规定 0 的阶乘为 1。自然数 n 的阶乘记作 n!，其数学公式为： 当 n = 0 时，n! = 1； 当 n > 0 时，n! = n × (n - 1) ! 。

问题分析

从公式可以看出，求 n 的阶乘可以拆解为求 n 乘以 (n - 1) 的阶乘，而求 (n - 1) 的阶乘又可以拆解为 (n - 1) 乘以 (n - 2) 的阶乘，以此类推，直到拆解到求 0 的阶乘（结果为 1），此时递归终止，再逐步回归计算出原问题的解。

举例 5 ! = 5* 4* 3* 2 1 4 ! = 4 3* 2* 1 所以：5 ! = 4 !

代码实现

#include <stdio.h>

// 定义递归函数计算n的阶乘
int Fact(int n)
{
    // 递归终止条件：n == 0时，返回1
    if (n == 0)
        return 1;
    // 递归调用：n > 0时，返回n乘以(n - 1)的阶乘
    else
        return n * Fact(n - 1);
}

int main()
{
    int n = 0;
    // 输入要计算阶乘的数字
    scanf("%d", &n);
    // 调用递归函数计算阶乘
    int ret = Fact(n);
    // 输出结果
    printf("%d\n", ret);
    return 0;
}

运行结果与推演

当输入 n = 5 时，程序运行结果为 120，符合 5! = 5×4×3×2×1 = 120 的预期。我们来推演一下递归过程：

Fact(5) = 5 × Fact(4)
Fact(4) = 4 × Fact(3)
Fact(3) = 3 × Fact(2)
Fact(2) = 2 × Fact(1)
Fact(1) = 1 × Fact(0)
Fact (0) = 1（递归终止） 然后开始回归计算：
Fact(1) = 1 × 1 = 1
Fact(2) = 2 × 1 = 2
Fact(3) = 3 × 2 = 6
Fact(4) = 4 × 6 = 24
Fact(5) = 5 × 24 = 120

3.2 实例 2：顺序打印一个整数的每一位

问题分析

输入一个整数 m，要求按照顺序打印出该整数的每一位。例如，输入 1234，输出 1 2 3 4；输入 520，输出 5 2 0。

要解决这个问题，首先需要思考如何获取整数的每一位。对于一个多位数，通过取余运算（%10）可以得到其最低位，通过整除运算（/10）可以去掉最低位。但直接使用这种方法得到的数字顺序是倒着的，比如 1234，先得到 4，再得到 3，接着得到 2，最后得到 1。

这时候就可以利用递归的思想：要打印 1234 的每一位，可以先打印 123 的每一位，再打印 1234 的最低位 4；要打印 123 的每一位，可以先打印 12 的每一位，再打印 123 的最低位 3；以此类推，直到要打印的数字是一位数时，直接打印该数字，递归终止。

代码实现

#include <stdio.h>

// 定义递归函数顺序打印整数的每一位
void Print(int n)
{
    // 递归终止条件：当n是一位数时，直接打印
    if (n > 9)
    {
        // 递归调用：先打印n去掉最低位后的数字的每一位
        Print(n / 10);
    }
    // 打印n的最低位
    printf("%d ", n % 10);
}

int main()
{
    int m = 0;
    // 输入要打印每一位的整数
    scanf("%d", &m);
    // 调用递归函数打印每一位
    Print(m);
    return 0;
}

运行结果与推演

当输入 m = 1234 时，程序运行结果为 1 2 3 4，符合预期。同样我们可以来推演递归过程：

Print (1234)：1234 > 9，调用 Print (123)，之后打印 1234%10 = 4
Print (123)：123 > 9，调用 Print (12)，之后打印 123%10 = 3
Print (12)：12 > 9，调用 Print (1)，之后打印 12%10 = 2
Print (1)：1 <= 9，直接打印 1%10 = 1（递归终止） 最终打印顺序为 1 2 3 4。

四、递归与迭代

递归虽然是一种简洁的编程技巧，但并非在所有场景下都是最优选择，很多时候迭代（通常指循环）是更好的替代方案。下面我们来对比递归与迭代的特点，并通过实例分析何时该使用递归，何时该使用迭代。

4.1 递归的优缺点

优点

代码简洁易懂：递归能够直接反映问题的数学模型，使得代码逻辑更加清晰，便于理解和编写。比如求 n 的阶乘，递归代码直接对应阶乘的数学公式，非常直观。
解决复杂问题更有优势：对于一些复杂问题，如汉诺塔问题、树的遍历等，使用递归可以将问题分解为更小的子问题，降低问题的复杂度，而使用迭代实现则可能非常繁琐。

缺点

栈溢出风险：在 C 语言中，每一次函数调用都会在栈区申请一块栈帧空间来保存局部变量等信息。如果递归层次过深，会占用大量的栈空间，导致栈溢出错误。
效率较低：递归过程中存在函数调用的开销，而且可能会出现大量重复计算的情况，导致程序运行效率降低。

4.2 迭代的优缺点

优点

效率高：迭代通过循环实现，避免了频繁的函数调用开销，也不会出现重复计算的问题（除非代码逻辑设计不当），运行效率更高。
内存占用少：迭代不需要额外的栈帧空间，内存占用相对较少，不存在栈溢出的风险。

缺点

代码逻辑可能复杂：对于一些复杂问题，使用迭代实现时，代码逻辑可能会比较繁琐，不易理解和维护。

4.3 实例对比：求第 n 个斐波那契数

斐波那契数的数学定义为： 当 n <= 2 时，Fib (n) = 1； 当 n > 2 时，Fib (n) = Fib (n - 1) + Fib (n - 2)。 根据这个定义，我们能很容易写出递归代码：

#include <stdio.h>

int Fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    return 0;
}

但当 n = 50 时，程序需要很长时间才能算出结果，效率极低。这是因为递归过程中存在大量重复计算，我们通过一个计数器来统计第 3 个斐波那契数的计算次数：

#include <stdio.h>
int count = 0;

int Fib(int n)
{
    if (n == 3)
        count++;// 统计第3个斐波那契数被计算的次数
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    printf("count = %d\n", count);
    return 0;
}

运行结果

40 102334155 count = 39088169

当输入 n = 40 时，输出结果中 count = 39088169，这意味着第 3 个斐波那契数被重复计算了近 4000 万次，大量的重复计算严重影响了程序效率。

4.4 迭代实现的优势

针对斐波那契数的计算，我们可以使用迭代的方式来避免重复计算。由于斐波那契数的前两个数都是 1，从第三个数开始，每个数都是前两个数的和. 因此我们可以通过循环从前往后依次计算：

#include <stdio.h>

int Fib(int n)
{
    // 初始化前两个斐波那契数
    int a = 1;
    int b = 1;
    // 存储当前斐波那契数，初始值为1（当n <= 2时）
    int c = 1;
    // 循环计算从第3个到第n个斐波那契数
    while (n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    return 0;
}

使用迭代实现后，即使 n = 100，程序也能快速计算出结果，效率远高于递归实现。