第十七课 函数递归调用 目 标 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; } ... ...
~~ 您好，已阅读到文档的结尾了 ~~
