1、1 引言递归程序处理的问题可以分成两类：第一类是数学上的递归函数，要求算得一个函数值，例如阶乘函数和Fibonacci函数；第二类问题具有递归特征，目的可能是求出满足某种条件的操作序列，例如Hanoi塔和八皇后问题。

2、第一类问题的程序设计是简单的、机械的，而第二类问题则不然，由于涉及面广，没有统一的规则可循，所以编程过程往往比较复杂，而且编得的程序也不大好理解。

(相关资料图)

3、究其原因在于，第一类问题已经有了现成的函数公式，第二类则没有。

4、如果我们对于第二类问题也能写出它的递归公式，那么编码过程会大大简化，而且还可以改善程序的可读性。

5、本文将借助两个程序实例讨论这种方法。

6、2 公式化方法程序设计可以分成两个阶段：逻辑阶段和实现阶段。

7、逻辑阶段要确定算法，不必考虑编程语言和实现环境。

8、通常算法可以用自然语言、流程图、NS图等工具来表示，对于第二类问题能在逻辑阶段得出它的递归公式，那么至少有这样几个好处：1. 把逻辑阶段同实现阶段截然分开，大大简化程序设计。

9、2. 用数学方法推导递归公式，要比用其他方法设计算法要简单得多。

10、3. 由于公式是算法的最精确最简洁的描述形式，有了递归公式，编码工作就变得异常简单，而且程序的可读性也会很好。

11、所谓递归程序设计的公式化方法，首先要把问题表示成数学意义下的递归函数，那么关键是确定函数值的意义，尽管问题本身未必需要计算什么函数值。

12、函数值的选取可能不是唯一的，但是愈能表现问题本质愈好。

13、Hanoi塔问题要求显示为把若干个盘子从一柱搬到另一柱要采取的动作，我们可以把动作的个数取为函数值。

14、于是得到有四个自变量的递归函数h(d，f，t，u)，其意义是以u柱（using）为缓冲把d个盘子（disks）从f柱（from）搬到t柱（to）。

15、容易得到下面的递归公式：h(1,f,t,u)=1h(d,f,t,u)= h(d-1,f,u,t)+ h(1,f,t,u)+ h(d-1,u,t,f), 如果d>1其实际意义非常明显：搬动一个盘子只需一个动作；而把f柱上的d个盘子从f柱搬到t柱，需要先把上面的d-1个盘子从f柱搬到u柱，再把最下面的一个盘子从f柱搬到t柱，最后把已在u柱上的d-1盘子搬到t柱，因此总的动作个数等于三组动作之和。

16、有了递归公式，编程就变得极为简单。

17、程序的结构是一个多分支结构，恰好同递归公式一一对应，编程几乎变成了机械的翻译。

18、在下面的程序中，递归函数与递归公式的差别只有当d为1时不仅要把动作个数v置为1，同时还要显示此动作。

19、main(){ int d,v,h(int,int,int,int);printf("disks = ");scanf("%d",&d);v=h(d,1,2,3);printf("%d actions for %d disks!",v,d);}int h(int d,int f,int t,int u){ int i,v;if(d==1){v=1;printf("%d->%d ",f,t);}else v=h(d-1,f,u,t)+h(1,f,t,u)+h(d-1,u,t,f);return v;}此程序的运行会话如下：disks = 31->2 1->3 2->3 1->2 3->1 3->2 1->27 actions for 3 disks!3 例子：八皇后问题八皇后问题[2]是一个更有代表性更复杂的递归例题，要求在8×8的国际象棋棋盘上摆放8个皇后，使她们不致互相攻击。

20、我们采取的算法仍然是从棋盘第一行开始每行放一个皇后，对于每一行都从该行的第一列开始放置，并判断它同前面的那些皇后是否互相攻击，如是就换成下一列，否则继续放置下一个皇后，直至放好8个皇后。

21、依照这种思想，我们定义一个有9个自变量的函数:q（k,a1,a2,a3,a4,a5,a6,a7,a8）其中k表示已放置的皇后个数，而ai（此处i<=k）表示第i行上的皇后所在列的列号，因此这9个自变量能够代表求解过程中任一时刻的状态，而函数值定义为从此状态出发能得到的解的个数。

22、按照这一思想不难得到下面的递归公式：q（k,a1,...,ak,0,...0）= 0 如果有0

23、将上面的递归公式很容易地翻译成如下程序：main(){ int a[9],v,q(int,int *);v=q(0,a);printf("There are %d solutions!",v);}int q(int k,int *a){ int i,u,v;for(i=1,u=1;i

24、在q( )中首先计算ak是否同其前的所有ai相容，若是变量u非0。

25、q( )与递归公式严格对应，呈现出有三个选择的分支结构。

26、在u非0且k为8的情况下，置函数值v为1，并显示已得到的解。

27、显然这个程序编写起来最为简单，而且最好理解。

28、下面给出该程序的交互会话，为节省版面只列出92个解中的4个：15863724 16837425 ... 83162574 84136275There are 92 solutions!4 结束语公式化方法是一种简单而有效的设计思想，它把程序设计和程序理解的难点都集中到递归公式上。

29、从上面的例子可以看到这种思想能够简化程序设计，而且得到的程序显然好于通常的程序。

30、这种思想有普遍性，至少适用多数递归程序的设计。

31、由递归公式设计出的程序具有标准的分支结构，编写和理解都要简单得多。

32、上面的两个例题在求得函数值的同时，很容易地得到了要求的序列，但对于一般的问题未必总是这样。

33、笔者曾给出一种伴随序列法，可以用来得到某些问题（如显示所有从m个数中取n个数的组合）要求的序列。

本文到此分享完毕，希望对大家有所帮助。

标签：