递归算法

.


原文：http://leihong511.blog.163.com/blog/static/47256469200962353527696/


递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。

我们先来看看大家熟知的一个的故事：

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说……

上面的故事本身是递归的，用递归算法描述：

procedure bonze-tell-story；

begin

  if 讲话被打断 then 故事结束

  else begin

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；

bonze-tell-story；

end

end;

从上面的递归事例不难看出，递归算法存在的两个必要条件：

（1）    必须有递归的终止条件；

（2）    过程的描述中包含它本身；

在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；

例1：汉诺塔问题，如下图，有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。移动时有如下要求：

（1）    一次只能移动一个盘子；

（2）    不允许把大盘放在小盘上边；

（3）    盘子只能放在三根柱子上；

算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：

如果只有一个盘子，只需一步，直接把它从A柱移动到C柱；

如果是二个盘子，共需要移动3步:

（1）    把A柱上的小盘子移动到B柱;

（2）    把A柱上的大盘子移动到C柱；

（3）    把B柱上的大盘子移动到C柱；

如果N比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存，按这种思路，就可以把N个盘子的移动过程分作3大步：

（1）    把A柱上面的N-1个盘子移动到B柱；

（2）    把A柱上剩下的一个盘子移动到C柱；

（3）    把B柱上面的N-1个盘子移动到C柱；

其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。

递归过程：

procedure Hanoi(N,A,B,C:integer;)；{以B柱为中转柱将N个盘子从A柱移动到C柱}

begin

  if N=1 then write(A,’->’,C){把盘子直接从A移动到C}

else begin

  Hanoi(N-1,A,C,B)；{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱}

  write(A,’->’,C)；{把剩下的一个盘子从A移动到C}

  Hanoi(N-1,B,A,C)； { 以A柱为中转柱将N-1个盘子从B柱移动到C柱}

end;

end;

从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。

在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。

例2求先序排列 (NOIP2001pj)

[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

[样例] 输入：BADC BDCA   输出：ABCD

算法分析：我们先看看三种遍历的定义：

先序遍历是先访问根结点，再遍历左子树，最后遍历右子树；

中序遍历是先遍历左子树，再访问根结点，最后遍历右子树；

后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；

从遍历的定义可知，后序排列的最后一个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可以由后序排列求得根结点，再由根结点在中序排列的位置确定左子树和右子树，把左子树和右子树各看作一个单独的树。这样，就把一棵树分解为具有相同性质的二棵子树，一直递归下去，当分解的子树为空时，递归结束，在递归过程中，按先序遍历的规则输出求得的各个根结点，输出的结果即为原问题的解。

源程序

program noip2001_3;

var　z,h : string;

procedure make(z,h:string); {z为中序排列,h为后序排列}

var　s,m : integer;

begin

  m:=length(h);{m为树的长度}

　write(h[m]); {输出根节点}

　s:=pos(h[m],z); {求根节点在中序排列中的位置}

　if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)); {处理左子树}

　if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)); {处理右子树}

end;

begin

　readln(z);

　readln(h);

　make(z,h);

end.

递归算法不仅仅是用于求解递归描述的问题，在其它很多问题中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现，从而使编写的程序更加简洁。

比如上期回溯法所讲的例2《数的划分问题》，若用递归来求解，程序非常短小且效率很高，源程序如下

var

  n,k:integer;

  tol:longint;

procedure make(sum,t,d:integer);

var i:integer;

begin

  if d=k then inc(tol)

  else for i:=t to sum div 2 do make(sum-i,i,d+1);

end;

begin

  readln(n,k);

tol:=0;

  make(n,1,1);

  writeln(tol);

end.

 

有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契(Fibonacci)数列，它的递归定义为：

F(n)=1          (n=1,2)

F(n)=F(n-2)+F(n-1) (n>2)

用递归过程描述为：

Funtion fb(n:integer):integer;

Begin

  if n<3 then fb:=1 

else fb:=fb(n-1)+fb(n-2);

End;

上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为O（2n）,把它改为非递归：

x:=1;y:=1;

for i:=3 to n do

begin

  z:=y;y:=x+y;x:=z;

end;

修改后的程序，它的时间复杂度为O（n）。

我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。


.