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

摘 要：递推和递归问题是计算机高级语言程序设计课程中的重点和难点问题。以卖票问题为例，对递推和递归方法进行了探讨，并通过C程序进行了验证。

关键词：递推；递归；C程序

中图分类号：TP311.5 文献标识码：A 文章编号：16727800（2013）003005701

作者简介：张春燕（1982-），女，硕士，无锡科技职业学院讲师，研究方向为数据库开发、算法设计。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）的递推关系：

4 购票排队递归程序实现

5 购票排队递推程序实现

6 结语

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

参考文献：

＼[1＼] 卢开澄， 卢华明.组合数学＼[M＼].第4版.北京：清华大学出版社，2006.

＼[2＼] 谭浩强.C程序设计＼[M＼].北京：清华大学出版社，1991.

（责任编辑：余 晓）

相关热词搜索： 递归 语言程序设计 方法