实验八 函数的递归算法
- 格式：rtf
- 大小：17.25 KB
- 文档页数：2
实验八 函数的递归算法
一、实验目的
1. 掌握函数的嵌套调用、递归调用。
2. 掌握递归法编程。
二、实验内容
1. 函数嵌套调用是在被调用的函数内再调用其它函数，而递归调用是在被调函数内调用
自身。嵌套调用的层数没有限制，而递归调用函数必须包含使递归终止的语句。
范例：求组合数，
[分析] 求组合数要用到求阶乘，可将求阶乘定义为一个函数，在求组合数的函数中嵌套
调用阶乘函数。由于n!=n*(n-1)!，求阶乘是一个典型的递归算法，在此用递归方法实现。
#include
using namespace std;
long com(int ,int), fac(int); //函数声明
int main(){
int m,n;
cout<<"Please input two numbers m,n(m cin>>m>>n; if(m<=n) cout<<"C(m,n)="< else cout<<"Input Error!\n"; return 0; } long com(int i,int j){ long cmb; // att： A cmb= fac(j)/(fac(i)*fac(j-i)); //在com函数内嵌套调用fac函数 return cmb; } long fac(int i){ long fcl; // att：B if(i==0||i==1) fcl =1; //使递归结束的语句 else fcl = i*fac(i-1); //递归调用 return fcl; } 这里因阶乘极易溢出，n最大取12，否则运算中会发生溢出。 [注意] 在函数内定义局部变量时，变量名不应与函数名相同，例如，在A行，不可定 义变量名为com，在B处，不可为fac；还有一种常见错误如下： long fac(int i){ if(i==0||i==1) fac(i) =1; else fac(i) = i*fac(i-1); return fac(i); } 编译这样的程序，会出现"Left_value required"的错误，这是为什么？ 2. 用欧几里德算法计算两个数的最大公约数，分别用递推（while循环实现）和递归两种方法实现。并计算两个数的最小公倍数。 [提示] 欧几里德算法参见教材【例2.21】 3. 修改题1，使其不易溢出。考虑到： =(n*(n-1)*...*(n-m+1))/m! =(n/1)*(n-1)/2* ...*(n-(m-2))/(m-1)* (n-(m-1))/m= Cm-1n*(n-(m-1))/m 可以用递归的方法计算。 这里n可以用到40。
