《C++语言中学版》递推算法特点

一个问题的求解需要一系列的计算，而已知条件和所求问题之间具有某种相互联系。如果可以找到计算过程之间的数量关系，通过这个关系可以从条件推出要解决的问题(也叫顺推)或者从问题推出已知条件(也叫逆推)，这种关系被称为递推式。这种算法可以将比较复杂的运算分成若干步重复的简单运算，充分发挥计算机运算速度快的特点。

例13－5　对13.4.1中的数字序列，编程求第n项的数值。

分析:由上面的分析可以得到xn＝xn－1＋xn－2，这就是此题的数量关系式，也叫递推式。同时，有初值x＝0，y＝5。根据递推算法导出程序如下:

例13－6　长青小学五年级一班的学生为了保护环境，利用星期日去上山植树，需要组织一部分男学生去山下水库抬水浇树(两人一组)，先将这些学生排成两列纵队，可以有多少种不同组合方法(根据个子高低，每位同学只能同同一排或前后同学组合)。

分析:先来看一下如果只安排两名男生，甲和乙，只有一种方法:

若有4名男生，方法一:甲1乙1，甲2乙2；方法二:甲1甲2，乙1乙2。

若有6名男生:

组合方法有:

方法一:甲1乙1，甲2乙2，甲3乙3。

方法二:甲1乙1，甲2甲3，乙2乙3。

方法三:甲1甲2，乙1乙2，甲3乙3。

因此得出队列的排数与组合的方法数有如下关系:

两列纵队有　一排(2个人)　组合方法一种即:x1＝1

　　　　　　两排(4个人)　　　　　　两种即:x2＝2

　　　　　　三排(6个人)　　　　　　三种即:x3＝x1＋x2

　　　　　　⋮　　　　　　 ⋮　　　　　　　　　　⋮(www.xing528.com)

最终导出有n排时(有2n个人)，组合方法有xn种，xn＝xn－1＋xn－2。

此题的递推式是从问题推到已知:从xn＝xn－1＋xn－2，推到x n－1＝x n－2＋x n－3，……推到x2＝2，x1＝1。

程序如下:

思考:读者自己能找出还有哪些问题可以用递推算法来解决?

递归就是函数或过程的调用，递归包括直接递归和间接递归。能用递归算法来求解的问题一般应该满足三个条件，即:需要解决的问题可以化为子问题，而子问题的求解方法与原问题的求解方法相同，只有数量的差别；递归调用的次数有限；有递归结束的条件。因此，分析每一个问题首先要按以上三条来检查一下是否适合应用递归算法。

例13－7　用递归方法编写程序，根据n的值运算f的结果，关系式如下(也是斐波那契数列中第n个数的求解关系式):

算法1:利用递归

程序如下:

这是一个直接调用函数本身的直接递归法，它是根据从大到小的处理方法，也就是先把fib(n)拆分为fib(n－1)和fib(n－2)，一直拆分到fib(0)和fib(1)结束，递归次数最多2n－1次。

递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。但是，递归在每次执行时都要为局部变量返回地址分配栈空间，这就降低了运行效率，也影响了递归算法的应用。

算法2:

递推算法按从小到大顺序讨论。

程序如下:

通过这两个程序的比较可以看到，递推算法比递归算法效率要高得多。