递推和递归方法在Ｃ语言程序设计中的应用

## 1.递归和递推算法
递归作为一种算法在程序设计语言中广泛应用。它是调用一个函数的过程中又出现直接或者间接地调用该函数本身。递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法。递推是序列计算机中的一种常用算法。递推法的特点是从一个已知的事实出发,按照一定规律推出下一个事实,再从这个新的已知事实出发,再向下推出一个新的事实。
## 2.问题提出
一场球赛开始前,售票工作正在紧张进行中,每张球票为50元,现有m+n个人排队等待购票,其中有m个人手持50元的钞票,另外n个人手持100元的钞票。假设开始售票时售票处没有零钱,求出这m+n个人排队购票,使售票处不至出现找不开钱的局面的不同排队种数(这里正整数m、n从键盘输入)。这个问题用一般的解决方法非常麻烦,下面用递归和递推方法解决。
## 3 购票问题分析
这是一道组合计数问题。令f(m,n)表示有m个人手持50元的钞票,n个人手持100元的钞票时共有的方案总数。
(1)n=0。n=0意味着排队购票的所有人手中拿的都是50元的钞票,那么这m个人的排队总数为1,即f(m,0)=1。
(2)m (3)其它情况。m+n个人排队购票,第m+n个人站在第m+n-1个人的后面,则第m+n个人的排队方式可由两种情况获得:①第m+n个人手持100元的钞票,则在他之前的m+n-1个人中有m个人手持50元的钞票,有n-1个人手持100元的钞票,此种情况共有f(m,n-1);②第m+n个人手持50元的钞票,则在他之前的m+n-1个人中有m-1个人手持50元的钞票,有n个人手持100元的钞票,此种情况共有f(m-1,n)。
由加法原理得到f(m,n)的递推关系:
f(m,n)=f(m,n-1)+f(m-1,n)
初始条件:
当m 当n=0时,f(m,n)=1

## 4.购票排队递归程序实现

```c

#include

long f(int j, int i)
{
long y=0;
if(i==0) y=1;
else if(j else y=f(j-1,i)+f(j,i-1);/*实施递归*/
return y;
}

int main()
{
int m,n;
printf("input m n:");
scanf("%d%d",&m,&n);
printf("f(%d,%d)=%ld.\n",m,n,f(m,n));

}

```

## 购票排队递推程序实现

```c

#include
void main()
{
int m,n,i,j;
long f[100][100];
printf(“inputm,n:”);
scanf(“%d,%d”,&m,&n);
for(j=1;j<=m;j++)
f[j][0]=1;
for(j=0;j<=m;j++)
for(i=j+1;i<=n;i++)
f[j][i]=0;
for(i=1;i<=n;i++)
for(j=i;j<=m;j++)
f[j][i]=f[j-1][i]+f[j][i-1];
printf(“f(%d,%d)=%ld.\n”,m,n,f[m][n]);
}
```

## 6结语
递归和递推算法解决问题结构清晰、可读性强,而且容易用数学归纳法来证明算法的正确性,为设计算法、调试程序带来很大方便。且递推程序的运行速度要快于递归程序.