2020-2021学年信息学奥赛资料 第十七课 函数递归调用（适用于高中）课件（15张PPT）

第十七课 函数递归调用

目 标
01、理解函数的递归调用。
02、 应用递归法解决一些实际问题。
函数的递归调用
函数调用自己，这种调用称为“递归”调用，这样的函数称为“递归函数”。
例1、阅读程序，写出程序的运行结果。利用单步跟踪，体会函数递归调用执行的过程。
#include
using namespace std;
void p(int n){
if(n > 0){
p(n-1);
for(int i = 0; i < n; i++) cout << n;
cout << endl;
}
}
int main(){
p(5);
return 0;}
递归的调用
一个问题要想用递归的方法（函数）来解决，必须要符合两个条件。
（1） 可以把这个问题转化成一个新问题，而新问题的解法和原问题的解法完全相同，只是问题规模变小了；
（2） 必须要有一个明确的递归结束条件（递归边界）。
例2、求阶乘
【问题描述】
编程求 n 阶乘的值，n! = 1×2×3×…×(n-1)×n。
【输入格式】
一行一个正整数 n，1≤n≤20。
【输出格式】
一行一个正整数，表示 n! 的值。
【输入样例】
5
【输出样例】
120
【问题分析】
求 n! 的值带有明显的递归思想。要想求出 n!，就要先求（n-1）!，因为（n-1）! 乘以 n 就是 n!；而要求（n-1）! 又要先求出（n-2）!，因为（n-2）！乘以（n-1）就是（n-1）!；……要求 2! 又要先求出 1!，因为 2 乘以 1 ！就是 2!；而 1 ！是已知的，就是 1。所以，阶乘问题的递归公式为：
#include
using namespace std;
long long jc(int n){
if(n == 1) return 1; // 递归边界
return jc(n-1) * n; // 递归公式
}
int main(){
int n;
cin >> n;
cout << jc(n) << endl;
return 0;
}
求 5 ！的递归调用过程如下:
例3、求最大公约数
【问题描述】
输入两个正整数 m 和 n，求它们的最大公约数。
【输入格式】
一行两个正整数 m 和 n，用一个空格隔开，2≤m，n≤10000。
【输出格式】
一行一个正整数，表示 m 和 n 的最大公约数。
【输入样例】
24 36
【输出样例】
12
【问题分析】
用欧几里得“辗转相除法”演示求最大公约数的过程，发现（m，n）的最大公约数与（n，m % n）的最大公约数是一样的，但是数据规模变小了。所以，最大公约数问题的递归公式为：
#include
using namespace std;
int gcd(int m,int n){
if(n == 0) return m;
else return gcd(n,m % n);
}
int main(){
int m,n;
cin >> m >> n;
cout << gcd(m,n) << endl;
return 0;
}
例4、分解质因子
【问题描述】
输入一个正整数 n，用递归方法从小到大输出它的所有质因子（因子是质数）。
【输入格式】
一行一个正整数 n，2≤n≤10000。
【输出格式】
一行若干个正整数，两数之间用一个空格隔开，从小到大输出。
【输入样例】
18
【输出样例】
2 3 3
【问题分析】
显然，如果 n 等于 1，就没法再分解了。如果 n 大于 1，从整数 p（p 从 2 开始）开始试除，如果能被 p 整除，就得到一个质因子 p。问题就转化成对于整数 n/p，从 p 开始继续分解质因子。
如果不能被 p 整除，问题就转化为对于整数 n，从 p+1 开始分解质因子。所以，递归公式为：
#include
using namespace std;
bool first = true;
void zyz(int n,int p){
if(n > 1){
if(n % p == 0){
if(first){
cout << p;
first = false;
}
else cout << “ “ << p;
zyz(n/p,p);
}
else zyz(n,p+1);
}
}
int main(){
int n;
cin >> n;
zyz(n,2);
cout << endl;
return 0;
}