C 语言中的递归

2025年8月2日 | 阅读 11 分钟

在 C 编程语言中，递归是指一个函数直接或间接地反复调用自身的过程，直到满足特定的基本条件。递归涉及多次递归调用。任何调用自身的函数都称为递归函数，这种函数调用称为递归调用。但是，必须为递归设置一个终止条件。递归代码比迭代代码短。但是，它很难理解。

递归并非适用于所有问题，但对于可以定义为相似子任务的任务来说，它更有用。例如，递归可以应用于排序、搜索和遍历问题。

C 语言递归的语法

它具有以下语法：

return_type function_name(parameters) {
    if (base_condition) {
        // stop recursion
        return result;
    } else {
        // recursive call
        return function_name(modified_parameters);
    }
}

在这个语法中，

return_type：表示函数返回的数据类型。
function_name：表示函数的名称。
base_condition：用于终止递归的条件。
Recursive condition：函数调用自身并修改参数的条件，该参数定期接近基本情况。

使用递归的 C 语言阶乘示例

让我们以一个例子来说明如何在 C 语言中使用递归查找阶乘。

示例

#include <stdio.h>
int fact (int);
int main()
{
    int n,f;
    printf("Enter the number whose factorial you want to calculate?");
    scanf("%d",&n);
    f = fact(n);
    printf("factorial = %d",f);
}
int fact(int n)
{
    if (n==0)
    {
        return 0;
    }
    else if ( n == 1)
    {
        return 1;
    }
    else 
    {
        return n*fact(n-1);
    }
}

编译并运行

输出

Enter the number whose factorial you want to calculate?5
factorial = 120

说明

在此示例中，我们使用递归计算给定数字的阶乘。首先，`fact()` 函数递归地将数字乘以比该数字小一的数字的阶乘，直到达到 1。但是，基本情况 `if (n == 0)` 错误地返回 0，而应返回 1，因为 0! = 1。

C 语言递归的工作原理

在 C 编程中，递归通过两个重要情况工作，即基本情况和递归情况。

1) 基本情况

在 C 语言递归中，基本情况是停止递归的条件。它定义了问题的最简单实例，函数不会调用自身。防止无限递归和堆栈溢出很重要，这可以确保递归最终终止。

2) 递归情况

在 C 语言中，递归情况是指函数以修改后的参数调用自身的情况，该参数会趋向于基本情况。它允许函数反复地将复杂问题分解为更简单的子问题。递归函数通过将任务分解为子任务来执行任务。函数中定义了终止条件，该条件由某些特定的子任务满足。之后，递归停止，并将最终结果从函数返回。

语法

它具有以下语法：

if (test_for_base)
{
	return some_value;
}
else if (test_for_another_base)
{
	return some_another_value;
}
else
{
	// Statements;
	recursive call;
}

C 语言使用递归查找斐波那契数列第 n 项的示例

让我们以一个例子来说明如何在 C 语言中使用递归查找斐波那契数列的第 n 项。

示例

#include<stdio.h>
int fibonacci(int);
void main ()
{
    int n,f;
    printf("Enter the value of n: ");
    scanf("%d",&n);
    f = fibonacci(n);
    printf("%d",f);
}
int fibonacci (int n)
{
    if (n==0)
    {
    return 0;
    }
    else if (n == 1)
    {
        return 1; 
    }
    else
    {
        return fibonacci(n-1)+fibonacci(n-2);
    }
}

编译并运行

输出

Enter the value of n: 12 
144

说明

在此示例中，我们使用递归计算第 n 个斐波那契数。这里，我们使用 `fibonacci()` 函数，该函数调用自身并传入更小的值（n-1 和 n-2），直到达到基本情况（n == 0 或 n == 1）。之后，每个递归调用都会将前两个斐波那契数相加来查找结果。

C 语言递归函数调用中的内存管理

在 C 编程中，每次递归调用都会创建一个该方法的新副本，该副本存储其局部变量、参数和返回地址。一旦某个数据由方法返回，副本就会从内存中删除。由于函数内声明的所有变量和其他内容都存储在堆栈中，因此每次递归调用都会维护一个单独的堆栈。

一旦从相应的函数返回了值，堆栈就会被销毁。递归在解决和跟踪每次递归调用的值方面涉及大量复杂性。因此，我们需要维护堆栈并跟踪堆栈中定义的变量的值。

C 语言递归函数调用内存管理的示例

让我们考虑以下示例来理解递归函数的内存分配。

int display (int n)  
{  
    if(n == 0)  
        return 0; // terminating condition  
    else   
    {  
        printf("%d",n);  
        return display(n-1); // recursive call  
    }  
} 

说明

让我们检查 `n = 4` 的递归函数。首先，维护所有堆栈，打印 `n` 的相应值，直到 `n` 变为 0。一旦达到终止条件，堆栈将通过向其调用堆栈返回 0 而逐个销毁。有关递归函数的堆栈跟踪的更多信息，请参阅以下图像。

C 语言递归的类型

根据可用的递归类型，C 语言中存在各种类型的递归。它们是

直接递归
间接递归

现在，我们将逐一讨论 C 语言中的这些递归类型。

直接递归

在 C 编程中，直接递归是最常用的递归，其中函数在其主体内直接调用自身。递归调用可能在函数内发生一次或多次，因此我们可以进一步细分直接递归

直接递归函数示例

让我们以一个例子来说明 C 语言中的直接递归。

示例

#include <stdio.h>
int factorial(int n) {
    if (n == 0) 
        return 1;
    else
        return n * factorial(n - 1); 
}
int main() {  //main function
    int number = 4;
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

编译并运行

输出

Factorial of 4 is 24

说明

在此示例中，我们通过直接递归计算数字的阶乘。阶乘函数递归地调用自身，参数为 `n - 1`，直到达到基本情况 `n == 0`，此时它返回 1。在 `main()` 函数中，使用参数 4 调用该函数，并输出结果（4 × 3 × 2 × 1 = 24）。

a) 前置递归

前置递归是一种线性递归，其唯一的递归调用位于函数开头。它通常是函数的第一条指令。

C 语言前置递归示例

让我们以一个例子来说明 C 语言中的前置递归。

示例

#include <stdio.h>
void printNumbers(int n) {
    if (n == 0)
        return;
    printNumbers(n - 1); 
    printf("%d ", n);    
}
int main() {   //main function
    int num = 5;
    printf("Numbers from 1 to %d:\n", num);
    printNumbers(num);
    return 0;
}

编译并运行

输出

Numbers from 1 to 5:
1 2 3 4 5

说明

在此示例中，我们使用前置递归打印数字 1 到 5。首先，`printNumbers` 函数调用自身并传入 `n - 1`，直到 `n` 变为 0，然后边返回边打印数字，从而按 1 到 5 的顺序打印数字。

b. 后置递归

后置递归也像前置递归一样是一种线性递归，但递归调用位于函数末尾。因此，后置递归可以被优化以减少堆栈内存的使用。这种优化是通过“尾部调用优化”术语完成的。

C 语言后置递归示例

让我们以一个例子来说明 C 语言中的后置递归。

示例

#include <stdio.h>
void printReverse(int n) {
    if (n == 0)
        return;
    printf("%d ", n);    
    printReverse(n - 1);  
}
int main() {  //main function
    int num = 6;
    printf("Numbers from %d to 1:\n", num);
    printReverse(num);
    return 0;
}

编译并运行

输出

Numbers from 6 to 1:
6 5 4 3 2 1

说明

在此示例中，我们使用后置递归打印数字 1 到 6。`printReverse` 函数打印当前数字，然后以 `n - 1` 递归调用自身，直到 `n` 变为 0（这是基本情况）。

c. 树递归

在树递归中，函数体中有多个递归调用。因此，在调试程序流程时，它会创建一个树状结构。

C 语言树递归示例

让我们以一个例子来说明 C 语言中的树递归。

示例

#include <stdio.h>
void treeRec(int n) {
    if (n <= 0)
        return;
    printf("%d ", n);
    treeRec(n - 1);  
    treeRec(n - 1);  
}
int main() {
    int num = 4;
    printf("Tree Recursion Output:\n");
    treeRec(num);
    return 0;
}

编译并运行

输出

Tree Recursion Output:
4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

说明

在此示例中，我们演示了树递归，因为函数对于每个大于 0 的 `n` 值都会调用自身两次。它会打印当前值，然后用 `n - 1` 调用自身两次，从而形成一个树状的分支调用堆栈。

间接递归

在 C 编程中，间接递归是一种重要的递归类型，其中一个函数调用另一个函数，该函数又调用第一个函数或序列中的另一个函数，从而形成函数调用的循环。多个函数协同工作进行递归过程以解决问题。

C 语言间接递归示例

让我们以一个例子来说明 C 语言中的间接递归。

示例

#include <stdio.h>
void printEven(int n);
void printOdd(int n);
void printEven(int n) {
    if (n <= 0) 
        return;
    if (n % 2 == 0) {
        printf("Even: %d\n", n);
        printOdd(n - 1);  
    } else {
        printOdd(n);
    }
}
void printOdd(int n) {
    if (n <= 0) 
        return;
    if (n % 2 != 0) {
        printf("Odd: %d\n", n);
        printEven(n - 1);  
    } else {
        printEven(n);
    }
}
int main() {  //main function
    int num = 4;
    printEven(num);
    return 0;
}

编译并运行

输出

Even: 4
Odd: 3
Even: 2
Odd: 1

说明

在此示例中，我们使用两个函数 `printEven` 和 `printOdd` 进行间接递归，它们相互调用以向下打印从 4 开始的偶数和奇数。它只打印正数，当 `n` 为 0 或负数时停止递归；因此，不打印零。

C 语言递归的优缺点

C 语言递归有许多优点和缺点。一些主要的优点和缺点如下：

优点

递归有助于简化代码编写。
它减少了不必要的函数调用次数。
当使用相同的解决方案时，它非常有用。
它减少了代码长度。
在解决数据结构问题时非常有用。
它有助于评估中缀、前缀和后缀堆栈等。

缺点

总的来说，递归函数的执行速度比其非递归对应函数慢。
可能需要大量内存来在系统堆栈中存储中间结果。
代码难以阅读或理解。
在时间和空间复杂度方面均无效。
如果递归调用未得到妥善检查，机器可能会耗尽内存。

递归与迭代

迭代和递归都是重复一系列指令的过程。它们之间的唯一区别如下：

当函数反复调用自身时，发生递归；当循环执行，直到控制条件变为 false 时，发生迭代。
递归是一种尤其在函数内部使用的方法，而迭代则用于必须重复的一组步骤。

使用递归的二分查找

二分查找算法测试索引“start”是否大于索引“end”。根据变量“mid”中存储的值，递归调用函数来查找元素。

我们有一个按递增顺序排列的数字列表。之后，我们计算列表的中点，并根据所需数字大于或小于中点处的数字来限制在其中点左侧或右侧进行检查。

C 语言使用递归进行二分查找的示例

让我们以一个例子来说明二分查找如何在 C 语言中使用递归。

示例

#include <stdio.h>
int binarySearch(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 binarySearch(arr, left, mid - 1, target);  
    else
        return binarySearch(arr, mid + 1, right, target); 
}
int main() {   //main function
    int arr[] = {1, 3, 7, 11, 22, 64};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 22;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result != -1)
        printf("Element %d found at index %d.\n", target, result);
    else
        printf("Element %d not found in the array.\n", target);
    return 0;
}

编译并运行

输出

Element 22 found at index 4.

说明

在此示例中，我们对排序数组执行递归二分查找以查找目标值。它找到中间索引并将其与目标值进行比较。如果相等，则返回索引；如果目标值较小，则搜索左半部分；如果较大，则搜索右半部分。搜索将继续进行，直到找到目标或子数组超出边界，如果未找到则返回 -1。main 函数通过一个示例数组测试此功能并打印结果。

递归选择题

1) C 语言中的递归是什么？

函数调用自身
一个函数调用另一个函数
函数内的循环
一个函数返回多个值

答案： a) 函数调用自身

2) 为了避免 C 语言中的无限调用，递归函数中需要包含什么？

指针
基本情况或终止条件
返回
循环

答案： b) 基本情况或终止条件

3) C 语言中的间接递归是什么？

函数直接调用自身
一个函数从不调用另一个函数
函数以循环方式相互调用
递归必须使用循环

答案： c) 函数以循环方式相互调用

4) 在斐波那契递归函数中，C 语言中检查了哪些基本情况？

n == 0 和 n == 2
n == 1 和 n == 2
n == 0 和 n == 1
仅 n == 0

答案： c) n == 0 和 n == 1

5) 如果递归方法在 C 语言中没有终止条件，会发生什么？

它将返回 0
它将终止程序
它将产生编译时错误
它将导致堆栈溢出

答案： d) 它将导致堆栈溢出

下一主题C 语言存储类

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言中的递归

C 语言递归的语法

使用递归的 C 语言阶乘示例

示例

C 语言递归的工作原理

1) 基本情况

2) 递归情况

C 语言使用递归查找斐波那契数列第 n 项的示例

示例

C 语言递归函数调用中的内存管理

C 语言递归函数调用内存管理的示例

C 语言递归的类型

直接递归

示例

示例

示例

示例

间接递归

示例

C 语言递归的优缺点

优点

缺点

递归与迭代

使用递归的二分查找

C 语言使用递归进行二分查找的示例

示例

递归选择题

相关帖子

C 语言按值调用和按引用调用

C 语言函数测试

C 语言存储类别

C 语言中的函数

订阅 Tpoint Tech

联系信息