主题递归算法及其应用.pdfVIP

：递归算法及其应用

[递归的描述]

由上面的例子可以看出，一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不

满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：

1）该问题能够被递归形式描述；2）存在递归结束的边界条件。

递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。

[例2]给出一棵二叉树的中序与后序排列。求出它的先序排列。

[分析]通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，有可以通过对比左

子树的中序与后序排列，找出左子树的根节点……可见，该问题能够被递归描述。当找到最后一个根节点

时，递归无法再进行下去，这就是递归结束的边界条件。由此可见，递归算法中常常隐含了分治思想。程

序如下：

programchu01_3;

varz,h:string;

procedurefind(a,b:string);

var

s,l:integer;

begin

l:=length(b);

ifl=1thenWrite(b){边界条件及递归返回段}

else

begin{递归前进段}

Write(b[l]);

s:=pos(b[l],a);

ifs-10thenfind(copy(a,1,s-1),copy(b,1,s-1));{递归左子树}

ifl-s0thenfind(copy(a,s+1,l-s),copy(b,s,l-s));{递归右子树}

end;

end;

begin

Readln(z);

Readln(h);

Find(z,h);

Readln;

end.

[递归的应用]

1.经典递归

例如hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用

递归做很自然。

2.递归与递推

利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更

为简单，有时可以直接用循环实现。

3.分治

不少分治方法是源于递归思想，或是递归分解+合并处理。

4.回溯

规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。

5.动态规划

动态规划的子问题性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模

型的方法。

6.其他

其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题

还是很方便的。

[例3]求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。

[分析]这是一道动态规划题，动态方程如下：

f[i-1,j]+f[i,j-i]+1（(jmodi=0)and(jdivi=1)）

f[i,j]:=f[i-1,j](i=j)

f[i-1,j]+f[i,j-i]（else）

s:=f(k,n-k)

本题可以用循环来实现递推,也可以考虑用递归求解。主过程如下：

方案一：

Procedurework(I,j:longint;vars:longint);

Vart:longint;

Begin

If(i=1)or(j=1)thens:=1

Elseif(i=0)or(j=0)thens:=0

Elsebegin

if(jmodi=0)a