第三讲递归与回溯法

1第三讲递归与回溯法一、递归的概念什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求(N-1)!。这就是一个递归的描述。因此，可以编写如下递归程序：programFactorial;varN:Integer;T:Longint;functionFac(N:Integer):Longint;beginifN=0thenFac:=1elseFac:=N*Fac(N-1)end;beginWrite('N=');Readln(N);T:=Fac(N);Writeln('N!=',T);end.图3-1展示了N=3的执行过程。由上述程序可以看出，递归是一个反复执行直到递归终止的过程。设一个未知函数f，用其自身构成的已知函数g来定义：为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2)，…010)!1(*!nnnnn图3-1递归调用示例图001,nannfngnf2一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。递归过程是借助于一个递归工作栈来实现的，问题向一极推进，这一过程叫做递推；问题逐一解决，最后回到原问题，这一过程叫做回归。递归的过程正是由递推和回归两个过程组成。递归有如下特点：①它直接或间接的调用了自己。②一定要有递归终止的条件，这个条件通常称为边界条件。与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。递归算法适用的一般场合为：①数据的定义形式按递归定义。如裴波那契数列的定义：2120121nffnnfnnn对应的递归程序为functionfib(n:Integer):Integer;beginifn=0thenfib:=1{递归边界}elseifn=1thenfib:=2{递归边界}elsefib:=fib(n–2)+fib(n–1);{递归}end;这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为unctionfib(n:Integer):Integer;begin递归按其调用方式分直接递归——递归过程P直接自己调用自己；间接递归——即P包含另一过程D，而D又调用P；3f[0]:=1;f[1]:=2;{递推边界}forI:=2tondof[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柱上的圆盘个数和从上到下每个圆盘的编号。输出：每行写一步的移动方案，格式为：MoveI圆盘formP柱toQ柱。最后输出最少步数。输入样例（如图）：6312324516061234560样例所描述的状态如图3-2所示。=图3-2样例图4输出样例：分析：要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响。根据上面的分析可设计如下过程Move(K,W);表示把编号K的圆盘从当前所在柱移动到W柱的过程。下面对样例进行分析。将6号盘移动到B柱，在此之前一定将经历如图3-3所示的状态要移动6号盘首先要把1~5号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上。显然这里要将它们移动到A柱。然后再将6号盘移到位。此时状态如图3-4所示。图3-3样例移动过程5同时我们注意到：把1~5盘移动到目标的过程和将6号盘移动到B柱的过程，从形式上是一样的，只是盘的编号不同而已。显然这是个递归过程，可以采用递归法实现。算法设计如下:procedureMove(K,W)；{编号K的圆盘从当前所在柱移动到W柱}beginifK号盘已经在W立柱上thenExit；{递归边界}forI:=K-1downto1doMove(I,过渡立柱);{将编号小于K的盘都移到过渡立柱上去}输出当前移动方案;将K号盘移到W立柱上;Inc(Step);{累计步数}end;程序设计如下：programNew_Hanoi;constInp=‘hanoi.in’;Outp=‘hanoi.out’;MaxN=64;{最大圆盘数}Stake:array[1..3]ofChar=(‘A’,‘B’,‘C’);typeTnode=array[1..MaxN]ofByte;{记录圆盘所处的立柱编号}varN:Integer;{圆盘数}Now,{当前状态}Goal:Tnode;{目标状态}Step:Longint;{步数}procedureInit;{读入数据}varI,J,L,X:Integer;beginAssign(Input,Inp);Reset(Input);Readln(N);{读入圆盘数}forI:=1to3dobegin{读入初始状态}图3-4样例移动过程6Read(L);forJ:=1toLdobeginRead(X);Now[X]:=I;end;Readln;end;forI:=1to3dobegin{读入目标状态}Read(L);forJ:=1toLdobeginRead(X);Goal[X]:=I;end;Readln;end;Close(Input);end;procedureMain;varI:Integer;procedureMove(K:Integer;W:Byte);varI,J:Word;beginifNow[K]=WthenExit;{若达到目标，则退出}J:=6–Now[K]–W;{计算过渡立柱编号}forI:=K–1downto1do{将圆盘移动到过渡立柱}Move(I,J);Write(‘Move‘,K,‘From‘,Stake[Now[K]],‘to‘,Stake[W]);Writeln(‘.’);Now[K]:=W;{将K号盘移动到目标位置}Inc(Step);{累计步数}end;beginAssign(Output,Outp);Rewrite(Output);forI:=Ndownto1do{从大到小对每一个圆盘进行处理}Move(I,Goal[I]);Writeln(Step);{输出总步数}Close(Output);end;BeginInit;Main;End.例3、背包问题：7已知一个容量大小为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号物品，如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去。参考程序：Programexam;VarW,P:Array[1..50]OfInteger;F:Array[1..50]OfInteger;Ou,Out:Array[1..50]OfBoolean;{Ou，Out数组记录选择物品的具体方案}M:Integer;N,U:Byte;Ans,Now:Integer;{Ans记录最优解，Now记录当前效益值}ProcedureInit;{初始化}VarI:Byte;BeginFillchar(Out,Sizeof(Out),False);Ou:=Out;Assign(Input,'Input.txt');Reset(Input);Readln(M,N);ForI:=1ToNDoReadln(W[I],P[I]);Close(Input);{读入数据}F[N+1]:=0;ForI:=NDownto1DoF[I]:=F[I+1]+P[I];{计算函数F的值}Ans:=0;Now:=0;End;ProcedureSearch(I:Integer;J:Byte);{递归求解}VarK:Byte;BeginIfNow+F[J]=AnsThenExit;{如果没有必要搜索下去，则返回到上一级}IfNowAnsThenBegin{修改最优解}Ans:=Now;8Out:=Ou;End;ForK:=JToNDo{选取物品}IfW[K]=IThenBeginNow:=Now+P[K];Ou[K]:=True;Search(I-W[K],K+1);Now:=Now-P[K];Ou[K]:=False;End;End;BeginInit;Search(M,1);Assign(Output,'Output.txt');{输出}Rewrite(Output);Writeln(Ans);ForU:=1ToNDoIfOut[U]ThenWrite(U,'');Writeln;Close(Output);End.例4、寻找国都名给出一个矩阵及一些国都名：okdublindublinalpgocevtokyorasmusmblondonoslondonromeyiblglrcbonnkrzurichparisoaibxmuzoslotpqglamvlima要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。输入：在文本文件input.txt中