函数的递归调用与分治策略

1、函数的递递归调用用与分治治策略递归方法法是算法法和程序序设计中中的一种种重要技技术。递递归方法法即通过过函数或或过程调调用自身身将问题题转化为为本质相相同但规规模较小小的子问问题。递递归方法法具有易易于描述述和理解解、证明明简单等等优点，在动态态规划、贪心算算法、回回溯法等等诸多算算法中都都有着极极为广泛泛的应用用，是许许多复杂杂算法的的基础。递归方方法中所所使用的的“分而治治之”的策略略也称分分治策略略。递归方法法的构造造构造递归归方法的的关键在在于建立立递归关关系。这这里的递递归关系系可以是是递归描描述的，也可以以是递推推描述的的。下面面由一个个求n的的阶乘的的程序为为例，总总结出构构造递

2、归归方法的的一般步步骤。例1从键盘盘输入正正整数NN（0=N=1时时，N!=N*(N-1)!（N=1时，0!=1），这就是是一种递递归关系系。对于于特定的的K!，它只与与K与(K-11)!有有关。步骤22确定定递归边边界 在在步骤11的递归归关系中中，对大大于k的的Un的的求解将将最终归归结为对对Uk的的求解。这里的的Uk称称为递归归边界（或递归归出口）。在本本例中，递归边边界为kk=0，即0!=1。对于任任意给定定的N!，程序序将最终终求解到到0!。确定递归归边界十十分重要要，如果果没有确确定递归归边界，将导致致程序无无限递归归而引起起死循环环。例如如以下程程序：#inccludde int

3、 f(iint x) reeturrn(ff(x-1);mainn() coout=1时n!= 11 当当N=00时再将这种种关系翻翻译为代代码，即即一个函函数：longg f(intt n) if (n=0) rretuurn(1); elsse rretuurn(n*ff(n-1);步骤44完善善程序 主要的的递归函函数已经经完成，将程序序依题意意补充完完整即可可。/exx1.ccpp#inccludde longg f(intt n) if (n=0) rretuurn(1); elsse rretuurn(n*ff(n-1);mainn() intt n; cinnnn; couute

4、nddl=33）。从从键盘输输入N，输出AA(N)。分析递归关关系十分分明显，由A(N)的的表达式式给出。需要注注意的是是本例中中对于NN=33，A(N)的的值与AA(N-1)和和A(NN-2)都有关关。代码/exx2.ccpp#inccludde longg fiibonnaccci(iint x) if ( (x=1) | (x=2) ) rretuurn(1); elsse rretuurn(fibbonaaccii(x-1)+fibbonaaccii(x-2);mainn() intt n; cinnnn; couutenddlfibbonaaccii(n); 例33Haanoii塔问

5、题题。 问题题描述在霍比比特人的的圣庙里里，有一一块黄铜铜板，上上面插着着3根宝宝石针（分别为为A号，B号和和C号）。在AA号针上上从下到到上套着着从大到到小的nn个圆形形金片。现要将将A针上上的金片片全部移移到C针针上，且且仍按照照原来的的顺序叠叠置。移移动的规规则如下下：这些些金片只只能在33根针间间移动，一次只只能一片片，且任任何时候候都不允允许将较较大的金金片压在在较小的的上面。从键盘盘输入nn，要求求给出移移动的次次数和方方案。分析由金片片的个数数建立递递归关系系。当nn=1时时，只要要将唯一一的金片片从A移移到C即即可。当当n11时，只只要把较较小的(n-11)片按按移动规规则从A

6、A移到BB，再将将剩下的的最大的的从A移移到C（即中间间“借助”B把金金片从AA移到CC），再再将B上上的(nn-1)个金片片按照规规则从BB移到CC（中间间“借助”A）。本题的特特点在于于不容易易用数学学语言写写出具体体的递归归函数，但递归归关系明明显，仍仍可用递递归方法法求解。代码/exx3.ccpp#inccludde hanooi(iint n,ccharr t11,chhar t2,chaar tt3) if (n=1) ccoutt1 tt1 tt3enddl; elsse haanoii(n-1,tt1,tt3,tt2); cooutn t1 t3enndl; haanoii(n

7、-1,tt2,tt1,tt3); mainn() intt n; couutnn; couutAnnsweer:eendll; hannoi(n,A,B,CC);函数递归归调用的的应用与与分治策策略许多算法法都采用用了分治治策略求求解，而而可以说说分治与与递归是是一对孪孪生兄弟弟，它们们经常同同时被应应用于算算法的设设计中。下面讨讨论著名名的Caatallan数数问题，人们在在对它的的研究中中充分应应用了分分治策略略。例4Cattalaan数问问题。问题描描述一一个凸多多边形，通过不不相交于于n边形形内部的的对角线线，剖分分为若干干个三角角形。求求不同的的剖分方方案总数数H(nn)。HH(n)

8、即为CCataalann数。例例如，nn=5时时H(55)=55。分析Cattalaan数问问题有着着明显的的递归子子问题特特征。在在计算CCataalann数时虽虽然可以以推导出出只关于于n的一一般公式式，但在在推导过过程中却却要用到到递归公公式。下下面讨论论三种不不同的解解法，其其中第三三种解法法没有使使用递归归，它是是由前两两种解法法推导而而出的。解法11对于于多边形形V1VV2Vn，对角线线V1VVi（ii=3,4,n-1）将将其分为为两部分分，一部部分是ii边形，另一部部分是nn-i+1边形形。因此此，以对对角线VV1Vii为一个个剖分方方案的剖剖分方案案数为HH(i)*H(n-ii

9、+1)。还有有一种的的特殊情情形，是是对角线线V2VVn将其其分为一一个三角角形V11V2VVn和一一个n-2+11边形。为了让让它同样样符合粗粗体字给给出的公公式，规规定H(2)=1。于于是得到到公式：H(n)=H(ii)*HH(n-i+11) （i=22,3,n-1） -公式式(1)H(2)=1有了这个个递归关关系式，就可以以用递推推法或递递归法解解出H(n)。解法22从VV1向除除了V22和Vnn外的nn-3个个顶点可可作n-3条对对角线。每一条条对角线线V1VVi把多多边形剖剖分成两两部分，剖分方方案数为为H(ii)*HH(n-i+22)，由由于Vii可以是是V3VV4Vn-1中的的任

10、一点点，且VV1可换换成V22，V33，Vnn中任一一点也有有同样的的结果。考虑到到同一条条对角线线在2个个顶点被被重复计计算了一一次，于于是对每每个由顶顶点和对对角线确确定的剖剖分方案案都乘以以1/22，故有有H(n)=n(1/2)HH(i)*H(n-ii+2) （ii=3,4,n-1）把(1/2)提提到外面，H(n)=n/(2*(n-3)H(ii)*HH(n-i+22) （i=33,4,n-1） -公式式(2)规定H(2)=H(33)=11，这是是合理的的。由公式(2)和和H(22)=11，同样样可以用用递推法法或递归归法解出出H(nn)。解法33 把把公式(1)中中的自变变量改为为n+1

11、1，再将将刚刚得得出的公公式(22)代入入公式(1)，得到H(n+1)=H(ii)*HH(n-i+22) （i=22,3,n） 由公式式(1)H(n+1)=2*HH(n)+H(ii)*HH(n-i+22) （i=33,4,n-1） 由由H(22)=11H(n+1)=(4nn-6)/n*H(nn) 由公公式(22)H(n)=(44n-110)/(n-1)*H(nn-1) -公公式(33)这是一个个较之前前两种解解法更为为简单的的递归公公式，还还可以继继续简化化为H(n)=1/(n-1)*C(nn-2,2n-4) -公式式(4)这就不需需要再使使用递归归算法了了。然而而在程序序设计上上，公式式(4

12、)反而显显得更加加复杂，因为要要计算阶阶乘。因因此最后后给出由由公式(3)作作为理论论依据范范例程序序代码。代码相相当简单单，这都都归功于于刚才的的推导。如果用用前两种种解法中中的递归归关系，程序会会变得复复杂且容容易写错错。因此此，有时时对具体体问题将将递归关关系公式式进行必必要的化化简也是是至关重重要的。代码/exx4.ccpp#inccludde #deffinee MAAXN 1000longg f(intt x) iff (xx=33) retturnn(1); ellse retturnn(44*x-10)*f(x-11)/(x-11);mainn() innt nn; coout

13、n; iff ( (n=33) ) couutThhe aanswwer is:f(nn);本例编程程时还有有一个细细节问题题需要注注意。注注意函数数f中的的斜体部部分，按按照公式式(4)计算时时一定要要先进行行乘法再再进行除除法运算算，因为为(4*x-110)并并不总能能整除(x-11)，如如果先进进行除法法则除出出的小数数部分将将自动被被舍去，从而导导致得到到不正确确的解。数学上许许多有重重要意义义的计数数问题都都可以归归结为对对Cattalaan数的的研究。可以看看到，本本例中的的递归关关系经简简化还是是相当简简单的。下面讨讨论一个个递归关关系略为为复杂的的例子。例5快速排排序问题题。快

14、速排序序是程序序设计中中经常涉涉及的一一种排序序算法。它的最最好时间间复杂度度为O(nloog2nn)，最最差为OO(n22)，是是一种不不稳定的的排序方方法（大大小相同同的数在在排序后后可能交交换位置置）。算法描描述快快速排序序的一种种基本思思想是：要将nn个数按按由小到到大排列列，在待待排序的的n个数数中选取取任一个个数（在在本例中中取第一一个），称为基基准数，在每一一次快速速排序过过程中设设置两个个指示器器i和jj，对基基准数左左边和右右边的数数同时从从最左（i）和和最右（j）开开始进行行扫描（i逐11递增，j逐11递减），直到到找到从从左边开开始的某某个i大大于或等等于基准准数，从从右

15、边开开始的某某个j小小于或等等于基准准数。一一旦发现现这样的的i和jj（暂且且称之为为一个“逆序对对”），则则把第ii个数和和第j个个数交换换位置，这样它它们就不不再是逆逆序对了了，紧接接着再将将i递增增1，jj递减11。如此此反复，在交换换过有限限个逆序序对后，i和jj将越来来越靠近近，最后后“相遇”，即ii和j指指向同一一个数，暂且称称之为相相遇数（极端情情况下，如果一一开始就就不存在在逆序对对，i和和j将直直接“相遇”）。相相遇后就就保证数数列中没没有逆序序对了（除了在在上述的的极端情情况下基基准数和和自身也也算构成成一个逆逆序对，注意粗粗体字给给出的逆逆序对的的定义）。继续续扫描，非极

16、端端情况下下，由于于数列中中已经没没有逆序序对，ii递增11（如果果相遇数数小于基基准数）或者jj递减11（如果果相遇数数大于基基准数）后即算算完成了了一趟快快速排序序，这时时第1到到第j个个数中的的每个都都保证小小于或等等于基准准数，第第i到第第n个数数中的每每个保证证大于或或等于基基准数。此时，递归调调用函数数，对第第1到第第j个数数和第ii到第nn个数分分别再进进行一趟趟快速排排序。如如果在极极端情况况下，程程序认为为基准数数和自身身构成逆逆序对，则将基基准数与与自身交交换（这这其实没没有作用用）之后后i递增增1，jj递减11（注意意斜体字字给出的的对逆序序对的处处理方法法），同同样对第

17、第1到第第j个数数和第ii到第nn个数分分别再进进行一趟趟快速排排序。最后的问问题就是是确定递递归边界界。由于于被排序序的数列列将不断断被划分分为两个个至少含含一个数数的子列列（因为为在每趟趟排序最最后进行行递归调调用函数数时ij），最后后子列的的长度将将变为11。这就就是递归归的边界界。在程程序实现现是，本本着“能排则则排”的原则则，只要要第一个个数小于于j（或或者第ii个数小小于最后后一个数数），即即进行递递归。主程序序（递归归函数体体）voidd QuuickkSorrt(RRecTTypee R ,intt s,intt t) innt ii=s,j=tt,k; ReecTyype t

18、emmp; iff (ssii&RRj.keeyttempp.keey) j-; iif(iij) RRi=Rj; ii+; whhilee( iij&Ri.keyyteemp.keyy) i+; iif(iij) RRj=Ri; jj-; RRi=teemp; QQuicckSoort(R,ss,i-1); QQuicckSoort(R,ii+1,t); 例66“九宫阵阵”智力游游戏。问题描描述一一个99方阵阵，由99个“九宫格格”组成，每个九九宫格又又由33共99个小格格子组成成。请在在每个空空白小格格子里面面填上119的的数字，使每个个数字在在每个九九宫格内内以及在在整个九九宫阵中中的每

19、行行、每列列上均出出现一次次。（1）编编程将下下面图中中的九宫宫阵补充充完整。（2）讨讨论是否否可能给给出“九宫阵阵”的全部部解？分析本题可可利用回回溯法解解决，其其基本思思想为深深度优先先搜索（DFSS），这这也是一一种以分分治策略略为基础础的算法法。回溯溯法与纯纯粹的DDFS不不同的是是，它在在搜索过过程中不不断杀死死不合题题意的结结点。这这一点保保证了解解法的效效率。首先考虑虑如何得得出全部部解的情情况。解空间树树容易构构造，只只需按顺顺序（从从第一行行第一个个数字开开始到第第一行最最后一个个，然后后第二行行，一一直到最最后一行行最后一一个数字字）“尝试”填入数数字即可可。为了解决决这个

20、问问题，我我们需要要先编写写一个函函数chheckk，其原原型为iint cheeck(intt i,intt j,intt k)，用于于求第ii行第jj列能否否填上数数字k。如果可可以，返返回1，否则返返回0。由于我我们是按按顺序填填入数字字的，看看起来一一个数字字后面的的数字并并不在判判断能否否填的范范围内。但为了了解决题题中某个个特解问问题的方方便，还还是引入入较为严严谨的判判断方法法。函数chheckk代码如如下：int cheeck(intt i,intt j,intt k) innt ll,m,pi,pj; /1. Cheeck thee liine foor (l=11;l=9;

21、l+) if ( (l!=j) & (ail!=0) & (aail=kk) ) rretuurn(0); /2. Cheeck thee coolummn foor (l=11;l=9;l+) if ( (l!=i) & (alj!=0) & (aalj=kk) ) rretuurn(0); /3. Cheeck thee 3xx3 mmatrrix /3.11 Fiirsttly wee wiill havve tto cchecck tthe parrentt_i(pi) annd ppareent_j(ppj) iff (ii=33) ppi=11; ellse if (i=6) pi

22、i=4; ellse pi=7; iff (jj=33) ppj=11; ellse if (j=6) pjj=4; ellse pj=7; /3.22 Noow wwe ccan cheeck it foor (l=00;l=2;l+) ffor (m=0;mm=22;m+) iff ( (ppi+ll)!=i) & (ppj+mm)!=j) ) if ( ( api+lpj+m!=0 ) & ( api+lpj+m=k ) ) reeturrn(00); reeturrn(11);结合注释释很容易易就能接接受函数数的思想想，不予予过多说说明。下面考虑虑程序最最重要的的部分，即递归归函数。思

23、路是是这样的的：假设设某一格格能填入入某数，把这个个格子看看成解空空间树的的一个结结点，由由它可以以扩展出出9个儿儿子，即即下一格格填什么么数（由由1到99逐个尝尝试）。对下一一格，同同样这样样考虑。不断用用函数cchecck函数数考察某某一个能能否填入入某数，一旦函函数chheckk返回00，则杀杀死这个个结点。如果能一一直填到到最后一一个数，结点仍仍未被杀杀死，则则这是一一个解。这种思想想可用伪伪代码表表示如下下：procceduure baccktrrackk(i,j,kk:inntegger); iff chheckk(i,j,kk)=ttruee thhen beeginn aai,

24、j=k; GGeneeratte_nnextt_i_andd_j; iif ii100 thhen bbegiin foor ll:=11 too 9 do baccktrrackk(i,j,ll);endelsee Doo_Ouutpuut;ai,j:=0; ennd;注意斜体体的“aii,j:=00”必不可可少！当当对某个个结点(x,yy)扩展展的过程程中，可可能在扩扩展到(x+mm,y+n)时时它的子子树被完完全杀死死（每个个结点都都被杀死死，亦即即按照(x,yy)及之之前的填填数方案案填数，无解）。这时时需要保保证(xx,y)以后所所填的数数被重新新置零，这个语语句的作作用即在在每个结

25、结点被杀杀死时都都将其置置零。将伪代码码翻译为为C+代码：backktraack(intt i,intt j,intt k) innt ll; iif (cheeck(i,jj,k)=11) aiijj=kk; /Fiill in thee okkay sollutiion /GGeneeratte nnextt i,j if (j9) j+; eelsee i+; jj=1; /EEnd of Genneraate nexxt ii,j if (i10) foor (l=11;l=9;l+) baccktrrackk(i,j,ll); elsse ooutpput(); aiijj=00;

26、/*Whhen faiils andd gooes uppperwwardds, thee vaaluee muust be cleeareed*/ 函数ouutpuut()用双重重循环完完成输出出。在主主函数mmainn()对对baccktrrackk(1,1,ii)进行行一个循循环，ii从1取取到9，即可完完成整个个程序。运行时时发现九九宫格的的解相当当多，即即使保存存到文件件中也不不现实。这就回回答了第第2个问问题。对于第11个问题题，将这这个程序序略加改改动，即即赋予全全局数组组a以初初值，并并在过程程baccktrrackk中产生生下一个个i和jj时跳过过有初值值的部分分，即可可将程

27、序序转化为为求填有有部分空空缺的九九宫格程程序。最后给出出填充有有部分空空缺的九九宫格的的完整源源代码。#inccludde usinng nnameespaace stdd;int a11111=00;int cheeck(intt i,intt j,intt k) innt ll,m,pi,pj; /1. Cheeck thee liine foor (l=11;l=9;l+) if ( (l!=j) & (ail!=0) & (aail=kk) ) rretuurn(0); /2. Cheeck thee coolummn foor (l=11;l=9;l+) if ( (l!=i) &

28、 (alj!=0) & (aalj=kk) ) rretuurn(0); /3. Cheeck thee 3xx3 mmatrrix /3.11 Fiirsttly we willl hhavee too chheckk thhe ppareent_i(ppi) andd paarennt_jj(pjj) iff (ii=33) ppi=11; ellse if (i=6) pii=4; ellse pi=7; iff (jj=33) ppj=11; ellse if (j=6) pjj=4; ellse pj=7; /3.22 Noow wwe ccan cheeck it foor (l=00;l=2;l+) ffor (m=0;mm=22;m+) iff ( (ppi+ll)!=i) & (ppj+mm)!=j) ) if ( ( api+lpj+m!=0 ) & ( api+lpj+m=k ) ) rretuurn(0); reeturrn(11); voiid ooutpput() innt ii,j; cooutOOne sollutiion is:enddl