递归算法的设计方法和技巧
魏晚霞 摘 要 编写递归算法时，应将原问题转换为1个或多个子问题，并找出停止条件；给出了3个设计的递归子程序实例，将堆排序调用的筛选过程sift改写为1个递归过程是其中1例。 关键词 递归 递归的准则 原问题 子问题
1 前言 1个直接或间接地调用自身的过程叫递归过程，1个使用函数自身给出定义的函数叫递归函数。递归能使程序设计者将主要精力集中在算法的关键步骤上。递归过程不仅结构清晰、易读，而且它的正确性容易得到证明。虽然递归过程运行时在时间、空间上的开销都比非递归过程大，但在很多时候，程序结构简单清晰比运行时间的缩短、空间的减少更有意义。2 使用递归的准则 如果待解决的问题具备下列两个特性，就可以考虑使用递归。 1)复杂的问题可以转换为简单些的1个或几个子问题； 2)最简单的问题可以直接解决。3 递归算法的设计方法和技巧 先向着假定解的方向前进简单的一小步，再看剩余的问题是否为规模小些的、简单些的、与原问题性质相同的子问题，换句话说，就是判断一下能否用解决原问题的方法来解决剩余的问题。对于一些本身具有递归特性的数据结构，可以很容易地先将原问题转换成1个或几个子问题，再找到由这个（些）子问题的解求出原问题的解的途径。这方面比较典型的例子有求二*树的叶子数、求二*树的高度、求二*树中第k层的结点个数等。 还必须找出标志问题被解决（或可以直接解决）的停止条件。有时候，停止条件满足时，只执行一个无关的过程调用语句。 当然，还应验证递归总能终止，即经过有限步后，停止条件满足，递归终止。实际中，我们通常选取几组极端情况下的数据，手工执行递归过程，看是否能得到正确的结果。4 设计递归算法举例 下列过程或函数均用Pascal语言编写，都已上机通过。 例1：写一个求数组a［1..n］的最大元素的递归函数。FUNCTION max1(i,j:INTEGER):INTEGER; VAR m2:INTEGER; BEGIN IF i=j THEN max1:=a［i］ ELSE BEGIN M2:=max1(i+1,j); IF m2>a［i］THEN max1:=m2 ELSE max1:=a［i］ END END； 函数max1(i,j)求数组a［i..j］中的最大元素。在主程序中执行语句x:=max1(1,n)后，x为a［1..n］中的最大元素。 停止条件为i=j，此时数组只有1个元素，数组的最大元素就是a［i］。停止条件不满足时，即i＜j时，数组至少有两个元素。数组a［i+1..j］比数组a［i..j］少1个元素a［i］，执行语句m2:=max1(i+1,j)后，m2为
数组a［i+1..j］中的最大元素。最后，通过比较m2与a［i］，得到数组a［i..j］中的最大元素。 例2：写1个求二*树的叶子数的递归函数。FUNCTION counf(bt:bitreptr):INTEGER; BEGIN IFbt=NIL THENcounf:=0 ELSE IF(bt↑．lchild=NIL)AND(bt↑．rchild=NIL) THENconuf:=1 ELSEcounf:=counf(bt↑．lchild)+counf(bt↑．rchild) END; 函数counf(bt)求得以bt↑为根结点的二*树的叶子数。若已知tree↑为某二*树的根结点，则在主程序中执行语句S:=counf(tree)之后，S为该二*树的叶子数。 停止条件为bt=NIL(空二*树)与(bt≠NIL)AND(bt↑．lchild=NIL)AND(bt((rchild=NIL)(只有1个结点的二*树)。对于其它情况，即二*树的根结点至少存在1棵子树叶，二*树的叶子数为它的左子树的叶子数与右子树的叶子数之和。 例3：将堆排序调用的筛选过程sift［1］改写为一个递归过程。PROCEDURE Sifre(VARr:listtype;k,m:INTEGER);VARj,x:INTEGER;t:redtype;BEGIN j:=2*k;x:=r［k］．key;t:=r［k］; IF j≤m THEN BEGIN IFj＜m THEN IF r［j］．key>r［j+1］．keyTHEN j:=j+1; IFx>r［j］．key THEN BEGIN r［k］:=r［j］; r［j］:=t; siftre(r,j,m) END ENDEND; rectype为记录类型，数组r的元素为记录。已知r［k+1..m］中各元素满足堆的性质，过程siftre(r,k,m)调整r［k］，使［k..m］中各元素满足堆的性质。 停止条件有两个，一个是j