第4讲 递归专题讲座

1第4讲递归递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。4.1递归概述一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。使用递归要注意以下几点：（1）递归就是在过程或函数里调用自身；（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。例如有函数r如下：intr(inta){b=r(a−1);returnb;}这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。例4-1用递归法计算n!。n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。（1）描述递归关系递归关系是这样的一种关系。设{U1,U2,U3,…,Un,…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。注意到，当n≥1时，n!=n*(n−1)!（n=0时，0!=1），这就是一种递归关系。对于特定的2k!，它只与k与(k−1)!有关。（2）确定递归边界在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#includestdio.hintf(intx){return(f(x−1));}main(){printf(f(5));}它没有规定递归边界，运行时将无限循环，会导致错误。（3）写出递归函数并译为代码将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即n!=n*(n−1)!当n1时n!=1当n=1时再将这种关系翻译为代码，即一个函数：longf(intn){longg;if(n0)printf(n0,输入错误！);elseif(n==1)g=1;elseg=n*f(n−1);return(g);}（4）完善程序主要的递归函数已经完成，设计主程序调用递归函数即可。#includestdio.hlongf(intn){longg;if(n0)printf(n0,输入错误！);elseif(n==1)g=1;elseg=n*f(n-1);return(g);}voidmain(){intn;longy;printf(计算n!，请输入n:);scanf(%d,&n);3y=f(n);printf(%d!=%ld\n,n,y);}程序中给出的函数f是一个递归函数。主函数调用f后即进入函数f执行，如果n0,n==0或n=1时都将结束函数的执行，否则就递归调用f函数自身。由于每次递归调用的实参为n−1，即把n−1的值赋予形参n，最后当n−1的值为1时再作递归调用，形参n的值也为1，将使递归终止，然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为5，即求5!。在主函数中的调用语句即为y=f(5)，进入f函数后，由于n=5，不等于0或1，故应执行f=f(n−1)*n，即f=f(5−1)*5。该语句对f作递归调用即f(4)。进行4次递归调用后，f函数形参取得的值变为1，故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为1*2=2，f(3)的返回值为2*3=6，f(4)的返回值为6*4=24，最后返回值f(5)为24*5=120。综上，得出构造一个递归方法基本步骤，即描述递归关系、确定递归边界、写出递归函数并译为代码，最后将程序完善。例4-2计算阿克曼函数阿克曼(Ackerman)函数a(n，m)递归定义如下：1,))1,(,1(0)1,1(01),(nmnmamanmamnnma试输出阿克曼函数的(m≤3,n≤10)的值。解：a函数是一个随着变量m,n变化的双递归函数。当m=0时，a(0,n)=n+1，这是递归终止条件；当n=0时，a(m,0)=a(m-1,1)；这是n=0时的递归表达式当m,n≥1时，a(m,n)=a(m-1,a(m,n-1))，这是递归表达式。试以a(1,3)为例说明函数的递归过程：a(1,3)=a(0,a(1,2))=a(0,a(0,a(1,1)))=a(0,a(0,a(0,a(1,0))))=a(0,a(0,a(0,a(0,1))))=a(0,a(0,a(0,2)))=a(0,a(0,3))=a(0,4)=5a函数及其调用描述如下：inta(intm,intn){if(m==0)returnn+1;elseif(n==0)returna(m-1,1);elsereturna(m-1,a(m,n-1));}#includestdio.hvoidmain(){intm,n;4printf(a(m,n));for(n=0;n=10;n++)printf(n=%1d,n);printf(\n);for(m=0;m=3;m++){printf(m=%d,m);for(n=0;n=10;n++)printf(%5d,a(m,n));printf(\n);}printf(\n);}程序运行求示例：a(m,n)n=0n=1n=2n=3n=4n=5n=6n=7n=8n=9n=10m=01234567891011m=123456789101112m=2357911131517192123m=351329611252535091021204540938189若采用递推求a(3,10)，由上表可知a(3,9)=4093，则a(3,10)=a(2,a(3,9))=a(2,4093)n的取值是未知的且非常大，可见递推完成的难度。4.2排队购票1.问题提出一场球赛开始前，售票工作正在紧张的进行中。每张球票为50元，现有30个人排队等待购票，其中有20个人手持50元的钞票，另外10个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这30个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数。（约定：拿同样面值钞票的人对换位置后为同一种排队。）2．递归设计要点我们考虑一般情形：有m+n个人排队等待购票，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（这里正整数m，n从键盘输入）。这是一道典型的组合计数问题，考虑用递推求解。令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。我们分情况来讨论这个问题。(1)n=05n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置后为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。(2）mn当mn时，即排队购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，所以这时排队总数为0，即f(m,n)=0。(3）其它情况我们思考m+n个人排队购票，第m+n个人站在第m+n-1个人的后面，则第m+n个人的排队方式可由下列两种情况获得：1）第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。2）第m+n个人手持50元的钞票，则在他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。由加法原理得到f(m,n)的递推关系：f(m,n)=f(m,n-1)+f(m-1,n)初始条件：当mn时，f(m,n)=0当n=0时，f(m,n)=13.购票排队递归程序实现//购票排队longf(intj,inti){longy;if(i==0)y=1;elseif(ji)y=0;//确定初始条件elsey=f(j-1,i)+f(j,i-1);//实施递归return(y);}#includestdio.hvoidmain(){intm,n;printf(inputm,n:);scanf(%d,%d,&m,&n);printf(f(%d,%d)=%ld.\n,m,n,f(m,n));}运行程序，inputm,n:15,12，得f(15,12)=4345965.4.购票排队递推程序实现//购票排队#includestdio.hvoidmain()6{intm,n,i,j;longf[100][100];printf(inputm,n:);scanf(%d,%d,&m,&n);for(j=1;j=m;j++)//确定初始条件f[j][0]=1;for(j=0;j=m;j++)for(i=j+1;i=n;i++)f[j][i]=0;for(i=1;i=n;i++)for(j=i;j=m;j++)f[j][i]=f[j-1][i]+f[j][i-1];//实施递推printf(f(%d,%d)=%ld.\n,m,n,f[m][n]);}运行程序，inputm,n:20,10，得f(20,10)=15737865.比较以上两个程序，递推程序的运行速度要快于递归程序。4.3汉诺塔问题汉诺塔（Hanoi），又称河内塔问题，是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。后来，这个传说就演变为汉诺塔游戏：木桩A木桩B木桩C木桩A木桩B木桩C123N123N图1图35-1汉诺塔游戏示意图7（1）有三根桩子A、B、C。A桩上有n个碟子，最大的一个在底下，其余一个比一个小，依次叠上去。（2）每次移动一块碟子，小的只能叠在大的上面。（3）把所有碟子从A桩全部移到C桩上，如图35-1所示。试求解n个圆盘A桩全部移到C桩上的移动次数，并求出n个圆盘的移动过程。4.3.1求移动次数1.递归关系当n=1时，只一个盘，移动一次即完成。当n=2时，由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，首先把小盘从A桩移到B桩；然后把大盘从A桩移到C桩；最后把小盘从B桩移到C桩，移动3次完成。设移动n个盘的汉诺塔需g(n)次完成。分以下三个步骤：(1)首先将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次；(2)然后将A桩上第n个盘子移到C桩上（1次）；(3)最后，将B桩上的n-1个盘子借助A桩移到C桩上，需g(n-1)次。因而有递归关系：g(n)=2*g(n-1)+1初始条件(递归出口)：g(1)=1.2.递归求解汉诺塔移动次数的程序设计//汉诺塔n盘移动次数#includestdio.hvoidmain(){doubleg(intm);//确定初始条件intn;printf(请输入盘片数n:);scanf(%d,&n);if(n=40)printf(%d