songzi 2008-4-30 23:16
递归算法【较详细】（常用算法）
递归算法及其应用[b][font=Verdana][size=9pt][[/size][/font][font=Verdana][size=9pt]递归的描述[/size][/font][font=Verdana][size=9pt]][/size][/font][/b]
[font=Verdana][size=9pt] 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：[/size][/font][font=Verdana][size=9pt]1[/size][/font][font=Verdana][size=9pt]）该问题能够被递归形式描述；[/size][/font][font=Verdana][size=9pt]2[/size][/font][font=Verdana][size=9pt]）存在递归结束的边界条件。[/size][/font]
[font=Verdana][size=9pt] 递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。[/size][/font][font=Verdana][size=9pt]
[b][[/b][/size][/font][b][font=Verdana][size=9pt]例[/size][/font][font=Verdana][size=9pt]1][/size][/font][/b]
[font=Verdana][size=9pt]给出一棵二叉树的中序与后序排列。求出它的先序排列。[/size][/font][font=Verdana][size=9pt]
[b][[/b][/size][/font][b][font=Verdana][size=9pt]分析[/size][/font][font=Verdana][size=9pt]][/size][/font][/b]
[font=Verdana][size=9pt]通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，有可以通过对比左子树的中序与后序排列，找出左子树的根节点[/size][/font][font=Verdana][size=9pt]……[/size][/font][font=Verdana][size=9pt]可见，该问题能够被递归描述。当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。由此可见，递归算法中常常隐含了分治思想。程序如下：[/size][/font][font=Verdana][size=9pt]
program chu01_3;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]var z,h: string;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]procedure find(a,b:string);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]var
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]s,l : integer;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]l:=length(b);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if l=1 then Write(b) {[/size][/font][font=Verdana][size=9pt]边界条件及递归返回段[/size][/font][font=Verdana][size=9pt]}
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]else
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]begin {[/size][/font][font=Verdana][size=9pt]递归前进段[/size][/font][font=Verdana][size=9pt]}
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Write(b[l]);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]s:=pos(b[l],a);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if s-1>0 then find(copy(a,1,s-1),copy(b,1,s-1)); {[/size][/font][font=Verdana][size=9pt]递归左子树[/size][/font][font=Verdana][size=9pt]}
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if l-s>0 then find(copy(a,s+1,l-s),copy(b,s,l-s)); {[/size][/font][font=Verdana][size=9pt]递归右子树[/size][/font][font=Verdana][size=9pt]}[/size][/font]
[font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]end;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]end;
begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Readln(z);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Readln(h);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Find(z,h);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Readln;
end.[/size][/font]
[b][font=Verdana][size=9pt][[/size][/font][font=Verdana][size=9pt]递归的应用[/size][/font][font=Verdana][size=9pt]][/size][/font][/b][font=Verdana][size=9pt]
1.[/size][/font][font=Verdana][size=9pt]经典递归[/size][/font]
[font=Verdana][size=9pt] 例如[/size][/font][font=Verdana][size=9pt]hanoi[/size][/font][font=Verdana][size=9pt]塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。[/size][/font][font=Verdana][size=9pt]
2.[/size][/font][font=Verdana][size=9pt]递归与递推[/size][/font]
[font=Verdana][size=9pt] 利用递归的思想建立递推关系，如由兔子生崽而来的[/size][/font][font=Verdana][size=9pt]fibonacci[/size][/font][font=Verdana][size=9pt]数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。[/size][/font][font=Verdana][size=9pt]
3.[/size][/font][font=Verdana][size=9pt]分治[/size][/font]
[font=Verdana][size=9pt] 不少分治方法是源于递归思想，或是递归分解[/size][/font][font=Verdana][size=9pt]+[/size][/font][font=Verdana][size=9pt]合并处理。[/size][/font][font=Verdana][size=9pt]
4.[/size][/font][font=Verdana][size=9pt]回溯[/size][/font]
[font=Verdana][size=9pt] 规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。[/size][/font][font=Verdana][size=9pt]
5.[/size][/font][font=Verdana][size=9pt]动态规划[/size][/font]
[font=Verdana][size=9pt] 动态规划的子问题重叠性质与递归有某种相似之处。递归[/size][/font][font=Verdana][size=9pt]+[/size][/font][font=Verdana][size=9pt]动态修改查表是一种不错的建立动态规划模型的方法。[/size][/font][font=Verdana][size=9pt]
6.[/size][/font][font=Verdana][size=9pt]其他[/size][/font]
[font=Verdana][size=9pt] 其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题还是很方便的。[/size][/font][font=Verdana][size=9pt]
[b][[/b][/size][/font][b][font=Verdana][size=9pt]例[/size][/font][font=Verdana][size=9pt]2][/size][/font][/b]
[font=Verdana][size=9pt]求把一个整数[/size][/font][font=Verdana][size=9pt]n[/size][/font][font=Verdana][size=9pt]无序划分成[/size][/font][font=Verdana][size=9pt]k[/size][/font][font=Verdana][size=9pt]份互不相同的正整数之和的方法总数。[/size][/font][font=Verdana][size=9pt]
[b][[/b][/size][/font][b][font=Verdana][size=9pt]分析[/size][/font][font=Verdana][size=9pt]][/size][/font][/b]
[font=Verdana][size=9pt]这是一道动态规划题，动态方程如下：[/size][/font]
[font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]f[i-1,j]+f[i,j-i]+1 [/size][/font][font=Verdana][size=9pt]（[/size][/font][font=Verdana][size=9pt](j mod i=0) and (j div i=1)[/size][/font][font=Verdana][size=9pt]）[/size][/font]
[font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]f[i,j]:= f[i-1,j] (i>=j)
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]f[i-1,j]+f[i,j-i] [/size][/font][font=Verdana][size=9pt]（[/size][/font][font=Verdana][size=9pt]else[/size][/font][font=Verdana][size=9pt]）[/size][/font]
[font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]s:=f(k,n-k)
[/size][/font][font=Verdana][size=9pt]本题可以用循环来实现递推[/size][/font][font=Verdana][size=9pt],[/size][/font][font=Verdana][size=9pt]也可以考虑用递归求解。主过程如下：[/size][/font]
[font=Verdana][b][size=9pt]方案一：[/size][/b][/font][font=Verdana][size=9pt]
Procedure work(I,j:longint; var s:longint);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Var t:longint;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Begin
If (i=1) or (j=1) then s:=1
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Else if (i=0) or (j=0) then s:=0
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]Else begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if (j mod i=0) and (j div i=1) then
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]work(i-1,j,s);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]t:=s;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]work(i,j-1,s);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]s:=s+t+1;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]end
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]else if (i>=j) then
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]work(i-1,j)
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]else begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]work(i-1,j,s);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]t:=s;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]work(I,j-1,s);
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]s:=s+t;
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]end; [/size][/font]
[font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]End;
[/size][/font][font=Verdana][b][size=9pt]方案二：[/size][/b][/font][font=Verdana][size=9pt]procedure search(v,w,last:byte);
var i:byte;
begin
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if w=0 then inc(count)
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]else
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if w=1 then
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]if v>=last then search(0,0,0) else
[/size][/font][font=Verdana][size=9pt] [/size][/font][font=Verdana][size=9pt]else for i:=last to v-1 do search(v-i,w-1,i);
end;
[/size][/font][font=Verdana][size=9pt] 可以看出，方案一的程序较为冗长，消耗栈空间较大；而方案二较为简洁明了，所用的栈空间也较小，效率较高。因此，使用递归算法也有一个优化问题。算法的简洁与否直接制约了程序的可行性和效率。[/size][/font][font=Verdana][size=9pt]
[b][[/b][/size][/font][b][font=Verdana][size=9pt]总结[/size][/font][font=Verdana][size=9pt]][/size][/font][/b]
[font=Verdana][size=9pt] 递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。但是，递归在每一次执行时都要为局部变量、返回地址分配栈空间，这就降低了运行效率，也限制了递归的深度。因此，在必要的时候可以只使用递归的思想来求解，而程序则转用非递归的方式书写。[/size][/font]