2023学年完整公开课版递归与深搜

递归长沙市雅礼中学朱全民重点内容递归的概念递归的表示递归实现方法用递归实现简单回溯算法实现递归时应注意的几个方面递归与递推的区别和联系递归的概念先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。递归的特点与应用场合用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归的实现方法递归是借助于一个递归工作栈来实现.1.递推:问题向一极推进，这一过程叫做递推；这一过程相当于压栈.2.回归:问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈.一个简单的实例将n个不同颜色的球,分别放到n个不同的盒子中去,问有多少种放法?分析:

显然所有的方法数为n!

这样,对于任意输入的整数n,我们只要算出n!即可．设f(n)=n!,则有，用递归实现Varn:integer;t:longint;functionf(n:integer):longint; begin ifn=0thenf:=1 elsef:=n*f(n-1) end;begin write(‘n=’);readln(n); t:=f(n); writeln(‘n!=’,t);end.N=3时的递归过程递归的表示Hanoi塔问题进制转换问题快速排序归并排序Ｎ皇后问题背包问题地图着色问题……用递归实现回溯算法回溯法也叫试探法，每次试着往前走，一直走到不通，然后撤回，重新试探．procedurerun（当前状态）；

vari：integer；beginif当前状态为边界thenbeginif当前状态为最佳目标状态then记下最优结果；

exit；{回溯}end；

fori←算符最小值to算符最大值dobegin

算符i作用于当前状态，扩展出一个子状态；

if(子状态满足约束条件)and(子状态满足最优性要求)thenrun(子状态)end；end；回溯法的几个重要因素(1)状态:作为递归的值参。(2)边界条件:作为递归的结束条件。(3)递归范围:作为for循环的初值和终值。(4)约束条件:满足解的条件。(5)最优性要求：满足最优解的条件。C目标柱A源柱汉诺塔B工作柱1.移动1个盘：hanoi(1,A,B,C);A->C：write(1,A,’->’,C);

2.移动2个盘：hanoi(2,A,B,C);

小盘：A->B：hanoi(1,A,C,B);

大盘：A->C：write(2,A,’->’,C);

小盘：B->C：hanoi(1,B,A,C);C目标柱A源柱B工作柱B工作柱C目标柱A源柱B工作柱C目标柱A源柱hanoi(2,a,c,b);writeln(3,a,'->',c);B工作柱C目标柱A源柱hanoi(2,b,a,c)3.移动3个盘：hanoi(3,A,B,C);

上面2个盘：A->Bhanoi(2,A,C,B);

第3个盘：A->Cwrite(3,A,’->’,C);B上的2个盘：B->Chanoi(2,B,A,C);汉诺塔4.移动n个盘：hanoi(n,A,B,C);

上面(n-1)个盘：A->Bhanoi(n-1,A,C,B);

第n个盘：A->Cwrite(n,A,’->’,C);B上的(n-1)个盘：B->Chanoi(n-1,B,A,C);C目标柱A源柱B工作柱总任务：将n个盘由A柱移到C柱分任务1：将n-1个盘由A柱移到B柱分任务2：将第n个盘由A柱移到C柱分任务3：将B柱的n-1个盘由B柱移到C柱汉诺塔varn:integer;procedurehanoi(n:integer;a,b,c:char);beginifn>0thenbegin

hanoi(n-1,a,c,b);writeln(n,a,'->',c);hanoi(n-1,b,a,c)endend;

beginread(n);{设n=3}

hanoi(n,'a','b','c');end.hanoi(2,a,c,b);writeln(3,a,'->',c);hanoi(3,'a','b','c');hanoi(2,b,a,c)hanoi(2,a,c,b);hanoi(1,a,b,c);writeln(2,a,'->',b);hanoi(1,c,a,b)hanoi(1,a,b,c);writeln(1,a,'->',c);hanoi(1,c,a,b)writeln(1,c,'->',b);hanoi(2,b,a,c)hanoi(1,b,c,a);writeln(2,b,'->',c);hanoi(1,a,b,c)hanoi(1,b,c,a);writeln(1,b,'->',a);hanoi(1,a,b,c)writeln(1,a,'->',c);⑦①②③④⑤⑥汉诺塔N皇后问题

在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。基本思想由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；按行放置皇后，每一行放一皇后；对每一行所放置的皇后按列进行试探；若某个位置能放，则放，否则试放下一个位置若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。若n个皇后都放好了，则得到了一个解。算法基本框架ProcedureTry(i:integer)；{搜索第i行皇后的位置}var j:integer;beginifi=n+1then输出方案；

forj:=1tondoif皇后能放在第i行第j列的位置thenbegin

放置第i个皇后；对放置皇后的位置进行标记；

Try（i+1）对放置皇后的位置释放标记；

end;end;边界条件设置怎样判断某列放置了皇后

a:array[1..MaxN]ofBoolean; {竖线被控制标记}怎样判断某对角线上放置了皇后

b:array[2..MaxN*2]ofBoolean; {左上到右下斜线被控制标记}c:array[1-MaxN..MaxN-1]ofBoolean;{左下到右上斜线被控制标记}程序ProcedureTry(i:integer)；var j:integer;beginifi=n+1thenprint；

forj:=1tondoifa[j]andb[i+j]andc[i-j]thenbegina[i]:=j;a[j]:=false;b[i+j]:=false;c[i-j]:=false;Try(i+1)a[j]:=true;b[i+j]:=true;c[i-j]:=true;end;end;procedurepr;{输出结果}vark:integer;beginfork:=1to8dowrite(k:3,':',q[k]);writeln;end;q[1]:=1;a[1]:=f;b[0]:=f;c[2]:=f;q[4]:=2;a[2]:=f;b[-2]:=f;c[6]:=f;q[5]:=4;a[4]:=f;b[-1]:=f;c[9]:=f;回溯：向前走，碰壁回头q[4]:=7;a[7]:=f;b[3]:=f;c[11]:=f;q[2]:=3;a[3]:=f;b[1]:=f;c[5]:=f;q[3]:=5;a[5]:=f;b[2]:=f;c[8]:=f;q[5]:=8;a[8]:=f;b[3]:=f;c[13]:=f;proceduretry(i:integer);

{递归调用}varj:integer;begin

forj:=1to8doifa[j]andb[j-i]andc[j+i]thenbeginq[i]:=j;a[j]:=false;b[j-i]:=false;c[j+i]:=false;ifi<8thentry(i+1)

{递归调用}elsepr;{过程调用}

a[j]:=true;b[j-i]:=true;c[j+i]:=true;

{回溯}end;end;begin{主程序}forj:=1to8doa[j]:=true;forj:=-7to7dob[j]:=true;{给数组赋初值}forj:=2to16doc[j]:=true;

try(1);{过程调用}end.递归调用示意图try(1)try(2)try(2)try(3)try(3)try(4)try(4)try(5)try(5)try(6)end;end;end;end;end;

回溯

回溯forend;forend;forend;forend;forend;try(7)try(8)end;

回溯forend;

回溯

回溯

回溯

回溯try(8)prend;forend;

回溯1234567812345678ijQQQQQQQtry(6)try(7)

回溯end;forend;思考题1:0,1背包问题已知一个容量大小为M重量的背包和N种物品，第i种物品的重量为Wi，若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大。输入数据：从文件的第一行读入M和N,接下来N行,第i+1行的两个数分别表示第i种物品的重量和效益。输出数据：第一行输出一个数，表示背包所装物品的最大效益。第二行输出若干个数字，分别表示所装物品的标号。基本思想按物品顺序选择放置背包；每个物品有选和不选两种可能性；按顺序将第某件物品放进包；如果第i件物品能放进包，则放，并更新当前最优值；如果第i件物品不能放进包，则有可能是前面的物品不能，则需要回溯；若每件物品都试探了一次，则输出最优解。思考题2：寻找国都名给出一个矩阵及一些国都名：okdublin dublinalpgocev tokyorasmusmblondonoslondon romeyiblglrcbonnkrzurich parisoaibxmuzoslotpqglamv lima要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。搜索的方向算法思想将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了

ConstFx:Array[1..8,1..2]OfShortint{定义八个方向}=((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1));

ProcedureWork(T,X,Y:Integer);{搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标}VarI:Integer;BeginIfT=Length(S)+1Thenbegin{搜索完，打印输出}Out;exitend;ForI:=1To8Do{八个方向进行搜索}BeginX:=X+Fx[I,1];Y:=Y+Fx[I,2];{坐标变化}If(A[X,Y]=S[T])And(B[X,Y])ThenBeginW:=W+Chr(I+48);{记录路径}B[X,Y]:=False;{设置已经搜索}Work(T+1,X,Y);{继续搜索下一个}Delete(W,Length(W),1);{恢复原路径}B[X,Y]:=True;{恢复标志}End;X:=X-Fx[I,1];Y:=Y-Fx[I,2];{返回后，坐标恢复}End;End;设置剪枝条件设F[i]表示选第i~n个物品全部放到背包能得到的总效益。显然，

F[n]=PnF[i]=F[i+1]+Pi （i=1..n-1）假设当前已选到第i号物品,如果，当前搜索的效益值+F[i+1]<当前的最优值，则没有必要继续搜索下去。算法框架ProcedureSearch(i:byte;weight:integer); VarK:byte;BeginIfNow+F[i]<=AnsThenExit; {剪枝条件}IfNow>AnsThenAns:=Now;{修改最优解} ForK:=itonDo {选取物品}IfW[k]<=weightThenBeginNow:=Now+P[k];Out[k]:=True;Search(k+1,weight-W[k]);Now:=Now-P[k];Out[k]:=False;End;End;思考题3:构造字串生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时‘abcba’满足条件‘abcbc’不满足条件输入：n，p输出：所有满足条件的字串分析状态：待扩展的字母序号i。由于该变量的存储量太大，因此我们将s设为全局变量；边界条件：产生了一个满足条件的字串，即i=n+1；搜索范围：从’a’开始的后p个字符；约束条件：当前字串没有相邻子串相等的情况proceduresolve(i:integer)；

vari,j,k:integer；t:longint;beginifi=n+1then{若产生了一个满足条件的字串，则输出}beginwriteln(s)；inc(t)；exit{回溯}end；

fork←1topdo{搜索每一个可填字母}begins←s+chr(64+k)；j←1；{检查当前字串是否符合条件}while(j<=idiv2)and(copy(s,length(s)-j+1,j)<>copy(s,length(s)-2*j+1,j))doinc(j)；

ifj>idiv2thensol