第三讲 递归与回溯法.doc

第三讲 递归与回溯法一、递归的概念什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求 (N-1)!这就是一个递归的描述因此，可以编写如下递归程序：program Factorial; var N: Integer; T: Longint; function Fac(N: Integer): Longint; begin if N = 0 then Fac := 1 else Fac := N * Fac(N - 1) end; begin Write('N = '); Readln(N); T := Fac(N); Writeln('N! = ',T); end.图3-1 递归调用示例图图3-1展示了N=3的执行过程由上述程序可以看出，递归是一个反复执行直到递归终止的过程。

设一个未知函数f，用其自身构成的已知函数g来定义：为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2) ，…一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用递归过程是借助于一个递归工作栈来实现的，问题向一极推进，这一过程叫做递推；问题逐一解决，最后回到原问题，这一过程叫做回归递归的过程正是由递推和回归两个过程组成递归有如下特点： ①它直接或间接的调用了自己 ②一定要有递归终止的条件，这个条件通常称为边界条件与递推一样，每一个递推都有其边界条件但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a然后返回调用函数返回的过程中，中间结果相继出栈恢复，f(1)=g(1,a)àf(2)=g(2,f(1))à……à直至求出f(n)=g(n,f(n-1))。

递归按其调用方式分直接递归——递归过程P直接自己调用自己；间接递归——即P包含另一过程D，而D又调用P；由此可见，递归算法的效率往往很低，费时和费内存空间但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适递归算法适用的一般场合为：① 数据的定义形式按递归定义如裴波那契数列的定义： 对应的递归程序为function fib(n: Integer): Integer; begin if n = 0 then fib := 1 {递归边界} else if n = 1 then fib := 2 {递归边界} else fib := fib(n – 2) + fib(n – 1); {递归} end;这类递归问题可转化为递推算法，递归边界为递推的边界条件例如上例转化为递推算法即为unction fib(n: Integer): Integer; begin f[0] := 1; f[1] := 2; {递推边界} for I := 2 to n do f[I] := f[I – 1] + f[I – 2]; fib := f(n); end;② 数据之间的关系（即数据结构）按递归定义。

如树的遍历，图的搜索等③ 问题解法按递归算法实现例如回溯法等对于②和③，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的浪费下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别二、应用举例例1、楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶编一递归程序，计算共有多少种不同走法？提示：如N级楼梯有S(N)种不同走法，则有：S(N)=S(N-2)+S(N-1)输入：N输出：所有的走法例2、新汉诺（hanoi）塔问题设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称之为初始状态问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态移动时有如下要求：① 一次只移动一个盘；② 不允许把大盘移到小盘上边；输入：输入文件第1行是状态中圆盘总数；第2~4行是分别是初始状态中A、B、C柱上的圆盘个数和从上到下每个圆盘的编号；第5~7行是分别是目标状态A、B、C柱上的圆盘个数和从上到下每个圆盘的编号输出：每行写一步的移动方案，格式为：Move I圆盘 form P柱 to Q柱。

最后输出最少步数输入样例（如图）：63 1 2 32 4 51 606 1 2 3 4 5 6 0样例所描述的状态如图3-2所示图3-2 样例图=输出样例：分析：要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响根据上面的分析可设计如下过程 Move(K, W);表示把编号K的圆盘从当前所在柱移动到W柱的过程下面对样例进行分析图3-3 样例移动过程将6号盘移动到B柱，在此之前一定将经历如图3-3所示的状态要移动6号盘首先要把1~5号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上显然这里要将它们移动到A柱然后再将6号盘移到位此时状态如图3-4所示图3-4 样例移动过程同时我们注意到：把1~5盘移动到目标的过程和将6号盘移动到B柱的过程，从形式上是一样的，只是盘的编号不同而已显然这是个递归过程，可以采用递归法实现。

算法设计如下:procedure Move(K, W)；{编号K的圆盘从当前所在柱移动到W柱} begin if K号盘已经在W立柱上 then Exit； {递归边界} for I := K - 1 downto 1 do Move(I, 过渡立柱); {将编号小于K的盘都移到过渡立柱上去} 输出当前移动方案; 将K号盘移到W立柱上; Inc(Step); {累计步数} end;程序设计如下： program New_Hanoi; const Inp = ‘hanoi.in’; Outp = ‘hanoi.out’; MaxN = 64; {最大圆盘数} Stake: array [1 .. 3] of Char =(‘A’, ‘B’, ‘C’); type Tnode = array [1 .. MaxN] of Byte; {记录圆盘所处的立柱编号} var N: Integer; {圆盘数} Now, {当前状态} Goal: Tnode; {目标状态} Step: Longint; {步数} procedure Init; {读入数据} var I, J, L, X: Integer; begin Assign(Input, Inp); Reset(Input); Readln(N); {读入圆盘数} for I := 1 to 3 do begin {读入初始状态} Read(L); for J := 1 to L do begin Read(X); Now[X] := I; end; Readln; end; for I := 1 to 3 do begin {读入目标状态} Read(L); for J := 1 to L do begin Read(X); Goal[X] := I; end; Readln; end; Close(Input); end; procedure Main; varI: Integer; procedure Move(K: Integer; W: Byte); var I, J: Word; begin if Now[K] = W then Exit; {若达到目标，则退出} J := 6 – Now[K] – W; {计算过渡立柱编号} for I := K – 1 downto 1 do {将圆盘移动到过渡立柱} Move(I, J); Write(‘Move‘,K,‘ From ‘,Stake[Now[K]],‘ to ‘,Stake[W]);Writeln(‘.’); Now[K] := W; {将K号盘移动到目标位置} Inc(Step); {累计步数} end; begin Assign(Output, Outp); Rewrite(Output); for I := N downto 1 do {从大到小对每一个圆盘进行处理} Move(I, Goal[I]); Writeln(Step); {输出总步数} Close(Output); end; Begin Init; Main; End.例3、背包问题：已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。

若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大分析：本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可另外，为了优化程序，我们定义一个函数如下：F[I]表示选第I~N个物品能得到的总效益不难推出：F[N]=PnF[I]=F[I+1]+Pi （I=1…N-1）假设当前已选到第I号物品，如果当。