C++ 递归

2025 年 4 月 25 日 | 7 分钟阅读

在 C++ 中，递归函数是直接或间接在同一函数内调用自身的函数。它必须包含至少一个基类和一个递归条件。基类有助于在条件完成后终止条件。另一方面，递归条件有助于代码的重复。在 C++ 中，递归函数将继续循环，直到不满足基条件。

语法

它具有以下语法：

void recursion(data_type parameter 1, ....)
{
    //Code to be Executed
    recursion(data_type param1, ....); //calling self
    //Code to be Executed
}

在此语法中，我们采用了一个名为（数据类型参数 1…）的函数，该函数声明为“recursion”并传递了多个参数。在这里，递归函数多次调用自身。

C++ 递归的简单示例

让我们举一个简单的例子，使用 C++ 中的递归来查找阶乘。

示例

#include <iostream>
using namespace std; //using standard namespace

int fact(int); //initialize fact as integer

int main() {
    int num, res;

    cout << "Enter the Positive Number: "; //input a number
    cin >> num;

    res = fact(num);
    cout << "Factorial of " << num << " is: " << res; //print the result of fact
    return 0;
}

int fact(int num) //recursion function calling itself
{
    if (num > 1) {
        return num * fact(num - 1);
    } else {
        return 1;
    }
}

编译并运行

输出

Enter the Positive Number: 6
Factorial of 6 is: 720

说明

在此示例中，我们使用了 fact() 函数，该函数正在调用自身。但是，我们在每次调用时都将 num 的值减小了 1。当 num 小于 1 时，fact() 函数返回输出。

C++ 中的递归如何工作？

在 C++ 中，递归使用了两种情况，即基条件和递归条件。

1. 基条件

在 C++ 递归中，基类是一种条件，一旦匹配，它有助于终止条件。它定义了函数不再调用自身的最简单场景。基条件定义了递归何时应该停止。它防止了无限递归和堆栈溢出。它确保函数到达停止点。

2. 递归条件

在 C++ 中，递归条件是函数使用修改后的参数调用自身的情况，该参数趋向于基条件。它有助于代码的重复。

递归函数的类型

递归函数主要有两种类型。它们如下

直接递归
间接递归

直接递归

在 C++ 中，当函数直接调用自身时，就会发生直接递归。

语法

它具有以下语法：

void direct_recursion() 
{
  //code to be executed
  direct_recursion() {
  //code to be executed
}

使用直接递归的 C++ 斐波那契数列示例

让我们举一个例子来说明 C++ 中使用直接递归的斐波那契数列。

示例

#include <iostream>
using namespace std; //using standard namespace

int fibonacci(int num) // Direct Recursion Function
{
    if (num == 0) return 0;  // Base case
    if (num == 1) return 1;  // Base case
    return fibonacci(num - 1) + fibonacci(num - 2);  // Recursive case
}

int main() {
    int number;
    cout << "Enter the Number: ";
    cin >> number;
    
    cout << "Fibonacci Series: ";
    for (int i = 0; i < number; i++) {
        cout << fibonacci(i) << " ";
    }
    
    return 0;
}

编译并运行

输出

Enter the Number: 5
Fibonacci Series: 0 1 1 2 3

说明

在此示例中，我们使用了一个整数 fibonacci (int num) 函数，该函数调用直接递归函数。我们还使用 (num==0) 和 (num==1) 作为基条件。之后，用户被要求输入数字，然后 for 循环开始根据给定条件打印斐波那契数。最后，它在控制台中打印输出。

间接递归

在 C++ 中，当两个或多个函数以循环方式相互调用时，就会发生间接递归。

语法

它具有以下语法：

void indirect_recursion() { 
  //code to be executed
  func(); 
  //code to be executed
} 
void func() { 
  //code to be executed
  indirect_recursion(); 
  //code to be executed
}

使用间接递归的 C++ 阶乘数示例

让我们举一个例子，使用 C++ 中的间接递归来查找阶乘数

示例

#include <iostream>
using namespace std; //using standard namespace

int factA(int n); //function declaration
int factB(int n);

int factA(int n) //Here function A call the Function B
{
    if (n == 1) return 1;  // Base case
    return n * factB(n - 1); //it calls the factB
}

int factB(int n) //Indirect function
{
    if (n == 1) return 1;  // Base case
    return n * factA(n - 1); // Calls factA
}

int main() {
    int num;
    cout << "Enter the Number: ";
    cin >> num;

    cout << "Factorial of " << num << " = " << factA(num) << endl;

    return 0;
}

编译并运行

输出

Enter the Number: 6
Factorial of 6 = 720

说明

在此示例中，我们使用了两个函数，其中 factA(int n) 函数使用 factB 函数计算阶乘，而 factB(int n) 函数使用 factA 计算阶乘。之后，发生间接递归，因为 factA(n) 调用 factB(n-1)，而 factB(n) 调用 factA(n-1)。

在 main() 函数中，程序要求用户输入数字并调用 factA(num) 来计算阶乘。最后，它在控制台中打印输出。

使用递归检查素数的 C++ 程序

让我们举一个例子，使用 C++ 中的递归来检查素数。

示例

#include <iostream> 
using namespace std; //using standard namespace

bool primeNum(int num, int x = 2) //initialize boolean value
{ 
if (num <= 2)
  return (num == 2) ? true : false; 

if (num % x == 0) 
  return false; 

if (x * x > num) 
  return true; 

return primeNum(num, x + 1); 
} 

int main() //main function
{ 
int num; 
cout << "Enter the Integer Number: "; //user input
cin >> num; 
if (primeNum(num))
  cout << "It is a Prime Number"; //print if number is prime
else
  cout << "It is not a Prime Number"; //print if number is not prime
return 0; 
}

编译并运行

输出

Enter the Integer Number: 5
It is a Prime Number

说明

在此示例中，primeNum() 函数是一个递归函数，它根据给定条件调用自身并检查给定数字是否为素数。

C++ 中的嵌套递归

在 C++ 中，嵌套递归是一种间接递归，其中递归函数在其自身的递归调用中创建另一个递归调用。它主要用于解决复杂的数学和算法问题。

C++ 中的 C++ 嵌套递归示例

让我们举一个例子来说明 C++ 中的嵌套递归。

示例

#include <iostream>
using namespace std; //using standard namespace

int NestRecursion(int a) 
{
    if (a > 120) //using if condition
        return a + 15;
    else
        return NestRecursion(NestRecursion(a - 20));  // Nested recursive call
}

int main() //main function
{
    int num;
    cout << "Enter the Number: "; //user input
    cin >> num;

    cout << "The Output is: " << NestRecursion(num) << endl; //print result
    return 0;
}

编译并运行

输出

Enter the Number: 130
The Output is: 145

C++ 中递归的优缺点

C++ 中递归的几个优缺点如下

C++ 中递归的优点

它通常导致优雅简洁的代码，特别是对于具有固有递归结构的问题。
它通过将复杂问题分解为更小、更易于管理的小问题来简化问题。
它用途广泛，可应用于各种问题。
它有助于减少代码长度。
它提供了一种简洁明了的编码方式。

C++ 中递归的缺点

由于调用堆栈，它会消耗更多内存，这对于深度递归会导致堆栈溢出错误。
递归解决方案可能不如迭代解决方案高效，因为每次函数调用都会产生开销。
由于复杂的调用堆栈和多个函数实例，调试递归函数可能具有挑战性。
这些函数比其他非递归函数慢。
它很难理解。

递归和迭代的区别

以下是递归和迭代的表格比较

方面	递归	迭代 (循环)
控制流	自引用函数调用自身。	循环结构（*for、while* 等）控制流程。
终止	它需要一个基条件来终止递归。	它由循环条件或计数器控制。
可读性	它有时可以导致更简洁、优雅的代码。	对于简单任务，它通常更直接。
内存使用	由于函数调用，它会消耗更多内存。	它通常消耗更少内存。
代码复杂度	对于某些问题，它可能涉及更少的代码。	它需要显式的循环控制和迭代。
状态处理	它维护一个函数调用堆栈以管理状态。	它依赖变量进行状态管理。
尾递归优化	一些编译器会优化尾递归。	循环尾调用没有固有的优化。
适用问题	适用于具有递归结构的问题。	适用于重复或迭代任务。

C++ 递归 MCQ

1. 以下哪个选项显示了 C++ 中递归的正确属性？

调用自身
基条件
返回值
以上全部。

答案： (d) 以上所有选项

2. C++ 递归函数中定义了多少个基条件？

两个
一次
两个以上
以上都不是

答案： b) 一个

3. 给定的 C++ 程序的结果是什么？

#include <iostream>
using namespace std;

int funct(int x) 
{
    if (x == 5)
        return x;
    else
        return 2 * funct(x + 3);
}

int main() {
    cout << funct(2);
    return 0;
}

答案： b) 10

4. 以下哪个数据结构用于管理 C++ 递归中的函数调用？

堆
链表
Stack
Queue

答案： c) 堆栈

5. 给定的 C++ 程序的输出是什么？

#include <iostream>
using namespace std;

void Numb(int a) {
    if (a > 0) {
        Numb(a - 2);
        cout << a << " ";
    }
}

int main() {
    Numb(7);
    return 0;
}

1 2 3 4 5 6 7
1 3 4 5 6 7
2 4 6
1 3 5 7

答案： d) 1 3 5 7

下一主题C++ 中的存储类

C++ 递归

语法

C++ 递归的简单示例

示例

C++ 中的递归如何工作？

1. 基条件

2. 递归条件

递归函数的类型

直接递归

使用直接递归的 C++ 斐波那契数列示例

示例

间接递归

使用间接递归的 C++ 阶乘数示例

示例

使用递归检查素数的 C++ 程序

示例

C++ 中的嵌套递归

C++ 中的 C++ 嵌套递归示例

示例

C++ 中递归的优缺点

C++ 中递归的优点

C++ 中递归的缺点

递归和迭代的区别

C++ 递归 MCQ

联系信息

关注我们

教程

面试题

在线编译器

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++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 递归

语法

C++ 递归的简单示例

示例

C++ 中的递归如何工作？

1. 基条件

2. 递归条件

递归函数的类型

直接递归

使用直接递归的 C++ 斐波那契数列示例

示例

间接递归

使用间接递归的 C++ 阶乘数示例

示例

使用递归检查素数的 C++ 程序

示例

C++ 中的嵌套递归

C++ 中的 C++ 嵌套递归示例

示例

C++ 中递归的优缺点

C++ 中递归的优点

C++ 中递归的缺点