文章目录
- 前言
- 一、 递归
- 1.1 基本概念
- 1.2 递归的过程
- 1.3 使用场景
- 二、例题讲解
- 问题一:1002 - 编程求解1+2+3+...+n
- 问题二:1241 - 角谷猜想
- 问题三:1108 - 正整数N转换成一个二进制数
- 问题四:1088 - 求两个数M和N的最大公约数
- 三、练习
- 问题一:1083 - 回文数
- 问题二:1084 - 因子求和
- 问题三:1244 - 请问一个正整数能够整除几次2
- 问题四:1307 - 数的计数
- 问题五:1087 - 两个数M和N的最小公倍数
- 四、感谢
前言
递归是一种计算机程序设计技术,它是指在一个函数或子程序的定义中直接或间接地调用自身的过程。递归的核心特点是解决问题时通过将问题分解为规模更小但结构与原问题相似的子问题来逐步求解,直到子问题足够简单可以直接得出答案。
本章节主要讲述递归的相关内容。
学习路线:C++从入门到NOI学习路线
学习大纲:C++全国青少年信息学奥林匹克竞赛(NOI)入门级-大纲
上一站:
下一站:
一、 递归
1.1 基本概念
大家都听过愚公移山这个故事吧?传说之中有两座大山,名字叫太行和王屋。
这两座山本来是在冀州南边,黄河北岸的北边。在北山的山下住着一个人,别人都叫他愚公。
愚公平时也没啥爱好,就爱刷刷抖音看看剧,打打游戏。
那愚公不好好的享受老年生活,干嘛非要去移山呢?
因为这两座山刚好在他家的对面。太行和王屋非常的高大,周围七百里,高七八千丈。
这就导致了一个问题—信号不好!!!!
于是愚公就开始了移山。
愚公有一个邻居,叫做智叟。
智叟发现了愚公的谜之操作。
为啥说是谜之操作呢?搬家不比搬山轻松?
智叟就问他(愚公):“你咋不搬家呢? ”,呸,”你都90岁了,少玩两天手机呗”。
愚公回答到:”那不行,我的队友还等我呢!“
智叟:“这么一大座山你也挖不完啊!”
愚公嘴角微微一翘,“虽我之死,有子存焉;子又生孙,孙又生子;子又有子,子又有孙;子子孙孙无穷匮也,而山不加增,何苦而不平?”
智叟听到愚公的回答,撇撇嘴,愤愤地走了。
智叟觉得办不到,是因为8000米高的太行、王屋山想要搬走实在是太难了。
而愚公觉得可以做到,是因为每天只需要挖掉一米就好了(举例而已),并不是要一下就完成这件事。
将复杂的问题转换成简单的问题,然后逐步求解。这就是递归的思想。
在编程中,递归的实现通常包含两个重要部分:
-
基本情况(Base Case):这是递归结束的条件,没有更小的子问题需要解决的情况。
-
递归步骤(Recursive Step):这是将大问题分解为小问题并调用自身的过程。
1.2 递归的过程
我们以愚公移山来展示递归的过程:
步骤1:定义递归函数
什么是递归函数呢?说白了就是立个flag。
- 首先,我们需要定义一个“移山”的递归函数。这个函数接收一个参数(对象),就是打算把哪座山要移掉。
void 移山(山名 太行山):
...
步骤2:确定基本情况(Base Case)
接下来,需要确定基本情况。
你问我什么是基本情况?
基本情况就是递归结束的条件,没有更小的子问题需要解决的情况。
基本情况就是打算干到什么时候退休、不干了。
在愚公移山中,估计把太行山挖空,愚公一家就能退休了。
- 因此基本情况是:
void 移山(山名 太行山):
如果 太行山 为空:
输出 "报告,太行山已经欧克!"
返回
愚公一家到这里就可以松一口气了。
不对!
还有王屋山。延迟退休!!!
延迟退休:就是递归函数被再一次调用。
步骤3:定义递归步骤(Recursive Step)
立了flag,设定了退休条件。接下来需要做什么呢?
没错,工作绩效。
愚公移山这件事,说白了就是愚公突然头脑发热。
他的后代可能并不想。。。他们可能只想。。。
所以需要设置一个每天最少要干多少事的目标。
愚公:那就每天挖1米吧。
没办法,老祖宗发话,得干啊。
void 移山(山名 太行山):
如果 太行山 为空:
输出 "报告,太行山已经欧克!"
返回
否则:
挖掉 太行山的1米
输出 "今日工作内容已完成,over!"
调用 移山(剩余的太行山)
注意在递归步骤这一部分结尾处我们一定要重新调用递归函数。
因为:明天的事情明天做!
我们已经完成了我们今天的工作绩效,加班是不可能的。
关于愚公移山的递归函数我们就写完了。
总结一下,递归的过程就是不断将问题规模缩小到基本情况,通过反复调用自身来解决小规模的问题,最终累积起来解决原来的大规模问题。
1.3 使用场景
- 数据结构遍历:
- 树(Tree)的遍历:深度优先搜索(DFS)通常采用递归来实现,包括前序遍历、中序遍历和后序遍历。
- 图(Graph)的深度优先搜索。
- 分治算法:
-
二分查找:在有序数组中查找一个数,每次都把待查找区间缩小一半。
-
大整数乘法:利用“分而治之”的思想将大整数分解为更小的部分进行计算。
-
斐波那契数列:计算第n个斐波那契数时,其值等于前两个数之和,自然适合用递归来表示。
- 动态规划问题:
-
最长公共子序列(LCS)问题:求解两个字符串的最长公共子序列时,可以使用递归定义状态转移方程。
-
最短路径问题(如矩阵链乘法):通过递归地分解问题来求解最优解。
- 数学函数:
-
计算阶乘:n! = n * (n-1)!
-
函数幂运算:a^n = a * a^(n-1)
- 图形绘制:
- 绘制分形图形,如科赫曲线、谢尔宾斯基三角形等。
- 文件系统操作:
- 在文件系统中查找文件或目录,往往需要递归地遍历所有子目录。
- 编译原理:
- 解析表达式树或其他语法结构时,递归下降解析器是一种常用的递归应用。
二、例题讲解
问题一:1002 - 编程求解1+2+3+…+n
类型:简单循环
题目描述:
编程求解下列式子的值: S=1+2+3+⋯+n。
输入:
输入一行,只有一个整数 n(1≤n≤1000) 。
输出:
输出只有一行(这意味着末尾有一个回车符号),包括 1 个整数。
样例:
输入:
100
输出:
5050
1.分析问题
- 已知:给定一个整数n。
- 未知:计算从1累加到n的和。
- 关系:递归。
2.定义变量
- 定义变量n用于存储用户输入的数值。
- 定义变量sum用于存储计算结果。
int n, sum;
3.输入数据
- 通过标准输入(cin)接收用户输入的整数n。
cin>>n;
4.数据计算
- 4.1定义一个名为mySum的递归函数,接受一个整数n作为参数
int mySum(int n){
// 基本情况:当n等于1时,返回1(因为1+0=1)
if(n==1){
return 1;
}
// 递归步骤:当n不等于1时,返回n加上mySum(n-1)的结果
// 这意味着每次调用mySum都会将问题规模缩小为n-1,并不断递归直到达到基本情况
else{
return n + mySum(n - 1);
}
}
- 4.2 调用mySum函数计算累加和,并将结果存入sum
sum = mySum(n);
5.输出结果
- 将计算得到的累加和输出到标准输出。
cout << sum;
// 主函数结束,返回0表示程序执行成功
return 0;
完整代码如下:
#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间
// 定义一个名为mySum的递归函数,接受一个整数n作为参数
int mySum(int n){
// 基本情况:当n等于1时,返回1(因为1+0=1)
if(n==1){
return 1;
}
// 递归步骤:当n不等于1时,返回n加上mySum(n-1)的结果
// 这意味着每次调用mySum都会将问题规模缩小为n-1,并不断递归直到达到基本情况
else{
return n + mySum(n - 1);
}
}
int main(){
// 数据定义部分
int n, sum; // 定义整数变量n表示要累加到的数值,sum用于存储计算结果
// 数据输入部分
cin >> n; // 从标准输入读取一个整数赋值给n
// 数据计算部分
sum = mySum(n); // 调用mySum函数计算累加和,并将结果存入sum
// 输出结果部分
cout << sum; // 将计算得到的累加和输出到标准输出
return 0; // 主函数返回0,表示程序正常结束
}
问题二:1241 - 角谷猜想
类型:有规律的循环、递归。
题目描述:
日本一位中学生发现一个奇妙的定理,请角谷教授证明,而教授无能为力,于是产生了角谷猜想。
猜想的内容:任给一个自然数,若为偶数则除以 2 ,若为奇数则乘 3 加 1 ,得到一个新的自然数后按上面的法则继续演算。若干次后得到的结果必为 1 。
请编写代码验证该猜想:求经过多少次运算可得到自然数 1 。
如:输入 22 ,则计算过程为。
22/2=11
11×3+1=34
34/2=17
17×3+1=52
52/2=26
26/2=13
13×3+1=40
40/2=20
20/2=10
10/2=5
5×3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
经过 15 次运算得到自然数 1 。
输入:
一行,一个正整数 n 。( 1≤n≤20000 )
输出:
一行,一个整数,表示得到 1 所用的运算次数。
样例:
输入:
22
输出:
15
1.分析问题
- 已知:一个正整数 n 。
- 未知:得到 1 所用的运算次数。
- 关系:角谷猜想。
2.定义变量
- 定义并读入一个整数n;
//二、数据定义
int n;
3.输入数据
//三、数据输入
cin>>n;
4.数据计算
-
定义全局变量c用于记录操作次数。
-
定义一个名为op的递归函数,参数为需要进行运算的整数n。
-
当n不等于1时,进入递归:
-
如果n是偶数,则对n进行除以2的操作,并以结果作为新的n调用op函数;
-
如果n是奇数,则对n进行乘以3再加1的操作,并以结果作为新的n调用op函数;
-
每进行一次上述操作(无论是除以2还是乘以3加1),全局计数器c加1。
int c=0;
void op(int n){
if(n!=1){
if(n%2==0){
op(n/2);
}else{
op(n*3+1);
}
++c;
}
}
- 调用op(n)开始执行角谷猜想的计算流程;
//四、数据计算
op(n);
5.输出结果
- 输出操作次数c,即从输入的n到达1所需经过的步骤数。
//五、输出结果
cout<<c;
return 0;
完整代码如下:
#include <bits/stdc++.h> // 引入C++标准库的头文件,包含大部分常用函数和数据结构
using namespace std; // 使用std命名空间,方便调用其中的标准库函数
int c = 0; // 定义全局变量c,用于记录执行操作(变换)的次数
// 定义递归函数op,参数为整数n
void op(int n) {
if (n != 1) { // 如果当前数值n不等于1,则继续进行以下操作
if (n % 2 == 0) { // 如果n是偶数
op(n / 2); // 将n除以2后作为新的输入值调用op函数(遵循角谷猜想的规则)
} else { // 否则,即当n是奇数时
op(n * 3 + 1); // 根据角谷猜想将n乘以3并加1后作为新的输入值调用op函数
}
++c; // 在每次执行完一次操作(无论是否改变n的值)后,计数器c增加1
}
}
int main() {
// 分析问题:实现角谷猜想(Collatz Conjecture),即对于任意正整数n,通过特定规则变换,最终都能到达1
int n; // 定义变量n,用于存储用户输入的初始数值
// 数据输入
cin >> n;
// 数据计算
op(n); // 调用op函数对给定的n执行角谷猜想的操作流程
// 输出结果
cout << c; // 输出从初始数值n到1所经历的操作次数
return 0; // 程序正常结束,返回0
}
问题三:1108 - 正整数N转换成一个二进制数
类型:字符串、进制转换
题目描述:
输入一个不大于 32767 的整数 n ,将它转换成一个二进制数。
输入:
输入只有一行,包括一个整数 n (0≤n≤32767)。
输出:
输出只有一行。
样例:
输入:
100
输出:
1100100
输入:
0
输出:
0
1.分析问题
- 已知:整数 n。
- 未知:转换成一个二进制数。
- 关系:进制转换、递归。
2.定义变量
- 定义一个字符串 s 来存储转换后的二进制数。
- 定义整数变量 n,用于接收用户输入的待转换的十进制数。
//二、数据定义
int n;
string s="";
3.输入数据
通过 cin>>n; 从标准输入读取一个十进制整数 n。
//三、数据输入
cin>>n;
4.数据计算
- 4.1定义一个名为binary的递归函数,接受一个整数n和一个空字符串s作为参数。
string binary(int n, string s){
char c; // 用于存储n对2取余的结果(0或1)并转换为字符
// 基本情况:当n等于0时,返回当前已经拼接好的二进制字符串s
if(0 == n){
return s;
}
// 递归步骤:当n不等于0时,计算n除以2的商,并将其与n对2取余的结果(c)一起传递给下一次函数调用
else{
c = n % 2 + '0'; // 将余数转换为字符'0'或'1'
return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边
}
}
- 4.2 调用binary函数进行二进制转换。
s=binary(n,s);
5.输出结果
- 判断字符串 s 是否为空(即 “”==s),如果为空说明输入的十进制数是0,则直接输出0;否则输出转换得到的二进制字符串 s。
//五、输出结果
if(""==s){
cout<<0;
}else{
cout<<s;
}
return 0;
完整代码如下:
#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间
// 定义一个名为binary的递归函数,接受一个整数n和一个空字符串s作为参数
string binary(int n, string s){
char c; // 用于存储n对2取余的结果(0或1)并转换为字符
// 基本情况:当n等于0时,返回当前已经拼接好的二进制字符串s
if(0 == n){
return s;
}
// 递归步骤:当n不等于0时,计算n除以2的商,并将其与n对2取余的结果(c)一起传递给下一次函数调用
else{
c = n % 2 + '0'; // 将余数转换为字符'0'或'1'
return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边
}
}
int main(){
// 数据定义部分
int n; // 输入的十进制整数
string s = ""; // 初始化一个空字符串,用于存储转换后的二进制数
// 数据输入部分
cin >> n; // 从标准输入读取一个整数赋值给n
// 数据计算部分
s = binary(n, s); // 调用binary函数进行二进制转换
// 输出结果部分
// 判断字符串 s 是否为空(即 ""==s),如果为空说明输入的十进制数是0,则直接输出0;.
if ("" == s){
cout << 0;
}
// 其他情况下,输出已转换好的二进制字符串s
else{
cout << s;
}
return 0; // 主函数返回0,表示程序正常结束
}
问题四:1088 - 求两个数M和N的最大公约数
类型:需要找规律的循环。
题目描述:
求两个正整整数 M 和 N 的最大公约数(M,N都在长整型范围内)
输入:
输入一行,包括两个正整数。
输出:
输出只有一行,包括1个正整数。
样例:
输入:
45 60
输出:
15
1.分析问题
- 已知:两个正整数。
- 未知:最大公约数。
- 关系:递归 、辗转相除法原理(即欧几里得算法),gcd(m, n) = gcd(n, m % n)。
2.定义变量
- 定义变量m、n存储输入的两个整数,result用于存储计算得到的最大公约数。
//二、数据定义
long long int m,n,result;
3.输入数据
//三、数据输入
cin>>m>>n;
4.数据计算
- 4.1 调用gcd函数计算m和n的最大公约数
//四、数据计算
result=gcd(m,n);
- 4.2 定义一个名为gcd的递归函数,接受两个长整型参数m和n
long long int gcd(long long int m, long long int n){
// 基本情况:当m能被n整除时(即m%n等于0),返回n作为最大公约数
if(0 == m % n){
return n;
}
// 递归步骤:当m不能被n整除时,继续调用gcd函数,并将n和m对n取余的结果作为新的参数传递给下一次函数调用
else{
return gcd(n, m % n); // 调用gcd函数,此时的问题规模变为了求解n和m%n的最大公约数
}
}
5.输出结果
- 输出计算得到的最大公约数。
- 主函数返回0,表示程序正常结束。
//五、输出结果
cout<<result;
return 0;
完整代码如下:
#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间
// 定义一个名为gcd的递归函数,接受两个长整型参数m和n
long long int gcd(long long int m, long long int n){
// 基本情况:当m能被n整除时(即m%n等于0),返回n作为最大公约数
if(0 == m % n){
return n;
}
// 递归步骤:当m不能被n整除时,继续调用gcd函数,并将n和m对n取余的结果作为新的参数传递给下一次函数调用
else{
return gcd(n, m % n); // 调用gcd函数,此时的问题规模变为了求解n和m%n的最大公约数
}
}
int main(){
// 数据定义部分
long long int m, n, result; // 定义变量m、n存储输入的两个整数,result用于存储计算得到的最大公约数
// 数据输入部分
cin >> m >> n; // 从标准输入读取两个正整数赋值给m和n
// 数据计算部分
result = gcd(m, n); // 调用gcd函数计算m和n的最大公约数
// 输出结果部分
cout << result; // 输出计算得到的最大公约数
return 0; // 主函数返回0,表示程序正常结束
}
三、练习
问题一:1083 - 回文数
问题二:1084 - 因子求和
问题三:1244 - 请问一个正整数能够整除几次2
问题四:1307 - 数的计数
问题五:1087 - 两个数M和N的最小公倍数
四、感谢
如若本文对您的学习或工作有所启发和帮助,恳请您给予宝贵的支持——轻轻一点,为文章点赞;若觉得内容值得分享给更多朋友,欢迎转发扩散;若认为此篇内容具有长期参考价值,敬请收藏以便随时查阅。
每一次您的点赞、分享与收藏,都是对我持续创作和分享的热情鼓励,也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇,共同攀登知识的高峰!