如何有效地确定递归公式（要求效率不能太低）最好介绍几个例子是来求那个递归公式的

Question

如何有效地确定递归公式（要求效率不能太低）
最好介绍几个例子是来求那个递归公式的

Answer 1

1 引言
递归程序处理的问题可以分成两类：第一类是数学上的递归函数,要求算得一个
函数值,例如阶乘函数和Fibonacci函数；第二类问题具有递归特征,目的可能是求
出满足某种条件的操作序列,例如Hanoi塔和八皇后问题.第一类问题的程序设计是
简单的、机械的,而第二类问题则不然,由于涉及面广,没有统一的规则可循,所以
编程过程往往比较复杂,而且编得的程序也不大好理解.究其原因在于,第一类问题
已经有了现成的函数公式,第二类则没有.如果我们对于第二类问题也能写出它的递
归公式,那么编码过程会大大简化,而且还可以改善程序的可读性.本文将借助两个
程序实例讨论这种方法.
2 公式化方法
程序设计可以分成两个阶段：逻辑阶段和实现阶段.逻辑阶段要确定算法,不必
考虑编程语言和实现环境.通常算法可以用自然语言、流程图、NS图等工具来表示,
对于第二类问题能在逻辑阶段得出它的递归公式,那么至少有这样几个好处：
1.把逻辑阶段同实现阶段截然分开,大大简化程序设计.
2.用数学方法推导递归公式,要比用其他方法设计算法要简单得多.
3.由于公式是算法的最精确最简洁的描述形式,有了递归公式,编码工作就变得异常
简单,而且程序的可读性也会很好.
所谓递归程序设计的公式化方法,首先要把问题表示成数学意义下的递归函数,那么
关键是确定函数值的意义,尽管问题本身未必需要计算什么函数值.函数值的选取可
能不是唯一的,但是愈能表现问题本质愈好.
Hanoi塔问题要求显示为把若干个盘子从一柱搬到另一柱要采取的动作,我们可以
把动作的个数取为函数值.于是得到有四个自变量的递归函数h(d,f,t,u),其意义
是以u柱（using）为缓冲把d个盘子（disks）从f柱（from）搬到t柱（to）.容易得
到下面的递归公式：
h(1,f,t,u)=1
h(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柱,因此总的动作个数等于三组动作之和.
有了递归公式,编程就变得极为简单.程序的结构是一个多分支结构,恰好同递归
公式一一对应,编程几乎变成了机械的翻译.在下面的程序中,递归函数与递归公式的
差别只有当d为1时不仅要把动作个数v置为1,同时还要显示此动作.
main()
{ int d,v,h(int,int,int,int);
printf("disks = ");scanf("%d",&d);
v=h(d,1,2,3);
printf("\n%d actions for %d disks!\n",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 = 3
1->2 1->3 2->3 1->2 3->1 3->2 1->2
7 actions for 3 disks!
3 例子：八皇后问题
八皇后问题[2]是一个更有代表性更复杂的递归例题,要求在8×8的国际象棋棋盘上摆
放8个皇后,使她们不致互相攻击.我们采取的算法仍然是从棋盘第一行开始每行放一
个皇后,对于每一行都从该行的第一列开始放置,并判断它同前面的那些皇后是否互相
攻击,如是就换成下一列,否则继续放置下一个皇后,直至放好8个皇后.依照这种思想,
我们定义一个有9个自变量的函数:
q（k,a1,a2,a3,a4,a5,a6,a7,a8）
其中k表示已放置的皇后个数,而ai（此处i