第五课 递归与回溯法
什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。
例如，我们可以这样定义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.
图13展示了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))。
由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。
递归算法适用的一般场合为：
① 数据的定义形式按递归定义。
如裴波那契数列的定义：
对应的递归程序为
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;
这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为
function 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皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。
例15：N皇后问题
在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。
分析：
由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。
下面是放置第I个皇后的的递归算法：
Procedure Try(I:integer)；
{搜索第I行皇后的位置}
var
j:integer;
begin
if I=n+1 then 输出方案；
for j:=1 to n do
if 皇后能放在第I行第J列的位置 then begin
放置第I个皇后；
对放置皇后的位置进行标记；
Try（I+1）
对放置皇后的位置释放标记；
End;
End;
N皇后问题的递归算法的程序如下：
program N_Queens;
const
MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数}
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total); Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Try(I: Integer);
{搜索第I个皇后的可行位置}
var
J: Integer;
begin
if I = N + 1 then Out; {N个皇后都放置完毕，则输出解}
for J := 1 to N do
if A[J] and B[J + I] and C[J – I] then begin
X[I] := J;
A[J] := False;
B[J + I] := False;
C[J – I] := False;
Try(I + 1); {搜索下一皇后的位置}
A[J] := True;
B[J + I] := True;
C[J – I] := True;
end;
end;
begin
Write(‘Queens Numbers = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, Sizeof(C), True);
Try(1);
Writeln(‘Total = ‘, Total);
end.
N皇后问题的非递归算法的程序：
program N_Queens;
const MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total);
Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Main;
var
K: Integer;
begin
X[1] := 0; K := 1;
while K > 0 do begin
if X[K] <> 0 then begin
A[X[K]] := True;
B[X[K] + K] := True;
C[X[K] – K] := True;
end;
Inc(X[K]);
while(X[K]<=N)and not(A[X[K]]and B[X[K]+K]and C[X[K]–K])do
Inc(X[K]); {寻找一个可以放置的位置}
if X[K] <= N then
if K = N then Out
else begin
A[X[K]] := False;
B[X[K] + K] := False;
C[X[K] – K] := False;
Inc(K);
X[K] := 0; {继续放置下一个皇后}
end
else Dec(K); {回溯}
end;
end;
begin
Write(‘Queens Number = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, SizeofI, True);
Main;
Writeln(‘Total = ‘, Total);
end.
使用递归可以使蕴含复杂关系的问题，结构变得简洁精炼。看看下面的例题。
例16:新汉诺（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柱。
最后输出最少步数。
输入样例（如图）：
6
3 1 2 3
2 4 5
1 6
0
6 1 2 3 4 5 6
0
样例所描述的状态如图15所示。
输出样例：
分析：
要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响。
根据上面的分析可设计如下过程
Move(K, W);
表示把编号K的圆盘从当前所在柱移动到W柱的过程。
下面对样例进行分析。
将6号盘移动到B柱，在此之前一定将经历如图16所示的状态
要移动6号盘首先要把1~5号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上。显然这里要将它们移动到A柱。然后再将6号盘移到位。此时状态如图17所示。
同时我们注意到：把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;
var
I: 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.
例17背包问题：
已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大
分析：本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。
另外，为了优化程序，我们定义一个函数如下：
F[I]表示选第I~N个物品能得到的总效益。不难推出：
F[N]=Pn
F[I]=F[I+1]+Pi （I=1…N-1）
假设当前已选到第I号物品，如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去。
参考程序：
Program exam17;
Var W,P :Array [1..50] Of Integer;
F :Array [1..50] Of Integer;
Ou,Out :Array [1..50] Of Boolean;
{Ou，Out数组记录选择物品的具体方案}
M :Integer;
N,U :Byte;
Ans,Now :Integer; {Ans记录最优解，Now记录当前效益值}
Procedure Init; {初始化}
Var I :Byte;
Begin
Fillchar(Out,Sizeof(Out),False);
Ou:=Out;
Assign(Input,'Input.txt');
Reset(Input);
Readln(M,N);
For I:=1 To N Do
Readln(W[I],P[I]);
Close(Input); {读入数据}
F[N+1]:=0;
For I:=N Downto 1 Do
F[I]:=F[I+1]+P[I]; {计算函数F的值}
Ans:=0;
Now:=0;
End;
Procedure Search(I:Integer; J:Byte); {递归求解}
Var K :Byte;
Begin
If Now+F[J]<=Ans Then Exit; {如果没有必要搜索下去，则返回到上一级}
If Now>Ans Then Begin {修改最优解}
Ans:=Now;
Out:=Ou;
End;
For K:=J To N Do {选取物品}
If W[K]<=I Then Begin
Now:=Now+P[K];
Ou[K]:=True;
Search(I-W[K],K+1);
Now:=Now-P[K];
Ou[K]:=False;
End;
End;
Begin
Init;
Search(M,1);
Assign(Output,'Output.txt'); {输出}
Rewrite(Output);
Writeln(Ans);
For U:=1 To N Do
If Out[U] Then Write(U,' ');
Writeln;
Close(Output);
End.
例18寻找国都名
给出一个矩阵及一些国都名：
o k d u b l i n dublin
a l p g o c e v tokyo
r a s m u s m b london
o s l o n d o n rome
y i b l g l r c bonn
k r z u r i c h paris
o a i b x m u z oslo
t p q g l a m v lima
要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。
输入：在文本文件input.txt中的第一行有一个整数M和N，表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵。字符矩阵后有一个整数K，表示国家都名的个数，接下来的K行，每一行都是一个国都名。
输出：在文本文件output.txt中共有K行，第I行写入第I个国都名的起始位置及方向。起始位置用坐标表示，方向定义见图18。如没有找到国都名，输出‘No found’。
分析：将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。
在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了。
参考程序如下：
program exam18;
Const
Fx : Array[1..8,1..2] Of Shortint {定义八个方向}
=((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1));
max = 100; {最大字符矩阵}
Finp = 'Input.Txt'; {输入文件名}
Fout = 'Output.Txt'; {输出文件名}
Var
A :Array[0..max+1,0..max+1] of Char;
{为了节约边界条件的判断，故增加边界范围}
B :Array[1..max,1..max] Of Boolean;
{标志数组，标志已经搜索过的路径}
S,
W :String;
N,M,I,J,K :Integer;
printed :Boolean;
Procedure Init;
Var
I,J :Integer;
Begin
Assign(Input,Finp); Reset(Input);
{采用重定向的手段，将输入文件与标准输入联系起来，
这样对标准输入（键盘）的操作，相当对输入文件的操作}
Assign(Output,Fout);Rewrite(Output);
{采用重定向的手段，将输出文件与标准输出联系起来，
这样对标准输出（屏幕）的操作，相当对输出文件的操作}
Readln(M,N);
For I:=1 To M Do Begin
For J:=1 To N Do Read(A[I,J]);
Readln;
End;
End;
Procedure Out;
Begin
write('(',J,',',k,')'); {输出起始位置的坐标}
Writeln('':5,W); {输出路径}
printed:=True {置已经打印的标志}
End;
Procedure Work(T,X,Y:Integer);
{搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标}
Var I : Integer;
Begin
If T=Length(S)+1 Then begin {搜索完，打印输出}
Out;
exit
end;
For I:=1 To 8 Do {八个方向进行搜索}
Begin
X:=X+Fx[I,1]; Y:=Y+Fx[I,2]; {坐标变化}
If (A[X,Y]=S[T])And(B[X,Y]) Then
Begin
W:=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;
Begin
Init;
Readln(N);
For I:=1 To N Do {对所有的国都名进行处理}
Begin
Readln(S); {读入第I个国都名}
printed:=False;
Fillchar(B,Sizeof(B),True);{未搜索之前清标志数组}
For J:=1 To N Do begin {对字符矩阵进行搜索}
For K:=1 To N Do Begin
If printed Then Break; {已经打印了，跳出内循环}
If A[J,K]=S[1] Then Work(2,J,K);{从第一个字符开始搜}
End;
If printed Then Break; {已经打印了，跳出外循环}
end;
If Not printed Then Writeln('No found');
End;
Close(Input);
Close(Output);
End.
例19采用递归方法，求N个元素中取出M个的排列，。
（1）每个元素只能取一次。
（2）每个元素可以取任意多次（即可重复的排列）。
分析：此题用简单的递归搜索。设x[I]排列中的第I个元素，依次搜索每一个x[I]即可
program exam19;
const finp ='input.txt';
fout ='output.txt';
maxn =10;
var n,m :integer;
x :array[1..maxn]of integer; { x数组记录当前排列}
used:array[1..maxn]of boolean; {used[I]=True时表明第I个元素在当前排列中，反之亦然}
procedure init; {初始化输入}
var i :integer;
begin
write(‘input n, m:’); readln(n,m);
fillchar(used,sizeof(used),false)
end;
procedure pailie(i:integer); {搜索}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln; {输出一组解}
end else
for j:=1 to n do
if not used[j] then begin
used[j]:=true; {修改used[I]}
x[i]:=j; {记录x[i]}
pailie(i+1); {继续搜索排列的下一个}
used[j]:=false {还原used[I]}
end
end;
Begin
init;
pailie(1);
End.
（2）只需要将pailie过程中used标志数组 去掉即可，这样，已经取过的数据可以继续取。
修改如下：
procedure pailie(i:integer); {搜索x[I]}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln;{找到一组解，输出}
end else
for j:=1 to n do begin {枚举x[I]}
x[i]:=j; {记录x[I]}
pailie(i+1) {继续搜索x[I+1]}
end
end;
- 版权所有 www.hnsz.net all rights reserved.power by 现代教育技术中心------淮南第三中学
- 皖ICP备2021013132号-1 网页设计、网站制作均由淮南三中信息中心提供支持
