《算法设计与分析-递归算法.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-递归算法.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、6.1递归的概念一、在日常生活中，递归一词较常用于描述以一、在日常生活中，递归一词较常用于描述以自相似方法重复事物的过程。自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。中嵌套的图像是以无限递归的形式出现的。2德罗斯特效应（英语：德罗斯特效应（英语：Droste effectDroste effect）是递归的一）是递归的一种视觉形式。图中女性手持种视觉形式。图中女性手持的物体中有一幅她本人手持的物体中有一幅她本人手持同一物体的小图片，进而小同一物体的小图片，进而小图片中还有更小的一幅她手图片中还有更小
2、的一幅她手持同一物体的图片，依此类持同一物体的图片，依此类推。推。3二、在数学与计算机科学中，递归是指在函数二、在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。的定义中使用函数自身的方法。例：第例：第5 5个人的年龄比第个人的年龄比第4 4个的年龄大个的年龄大2 2岁，有岁，有4 4个人的年龄比第个人的年龄比第3 3个的年龄大个的年龄大2 2岁，有岁，有3 3个人个人的年龄比第的年龄比第2 2个的年龄大个的年龄大2 2岁，有岁，有2 2个人的年龄个人的年龄比第比第1 1个的年龄大个的年龄大2 2岁，第岁，第1 1个的年龄个的年龄1010岁。岁。4例：阶乘的定义。例：阶乘的定义。
3、56在下面二种情况中存在算法调用自己的情况：在下面二种情况中存在算法调用自己的情况：（1 1）问题的定义是递推的）问题的定义是递推的阶乘函数的阶乘函数的常见定义常见定义是：是：7也可定义为：也可定义为：写成函数形式，则为：写成函数形式，则为：这种函数定义的方法是这种函数定义的方法是用阶乘函数自己本身定义了用阶乘函数自己本身定义了阶乘函数阶乘函数，称上式为阶乘函数的，称上式为阶乘函数的递推定义式递推定义式。8（2）问题的解法存在自调用）问题的解法存在自调用 一一个个典典型型的的例例子子是是在在有有序序数数组组中中查查找找一一个个数数据据元元素素是是否否存在的存在的折半查找算法折半查找算法。如下例
4、中查找元素如下例中查找元素1717。第一次第一次:下标下标01234567元素值元素值134517183133lowmidhighxamid第二次第二次:下标下标01234567元素值元素值134517183133lowmidhighxamid第三次第三次:下标下标01234567元素值元素值134517183133lowhighx=amidmidBSrch=4mid=(low+high)/296.2递归算法的执行过程 例例6-1 6-1 给出按照给出按照阶乘函数的递推定义式阶乘函数的递推定义式计算阶乘函数的计算阶乘函数的递归算法，并给出递归算法，并给出n=3n=3时递归算法的执行过程。时递归
5、算法的执行过程。设计：按照阶乘函数的递推定义式计算阶乘函数的递归设计：按照阶乘函数的递推定义式计算阶乘函数的递归算法如下：算法如下：longintFact(intn)intx;longinty;if(n0)/nhigh)return-1;/查找不成功查找不成功mid=(low+high)/2;if(x=amid)returnmid;/查找成功查找成功elseif(xamid)returnBSearch(a,x,low,mid-1);/在下半区查找在下半区查找elsereturnBSearch(a,x,mid+1,high);/在上半区查找在上半区查找14测试代码设计如下：测试代码设计如下：#i
6、ncludemain(void)inta=1,3,4,5,17,18,31,33;intx=17;intbn;bn=BSearch(a,x,0,7);if(bn=-1)printf(x不在数组不在数组a中中);elseprintf(x在数组在数组a的下标的下标%d中中,bn);15BSearch(a,x,0,7)BSearch(a,x,0,7)的递归调用过程如下图所示，其的递归调用过程如下图所示，其中，中，实箭头实箭头表示过程表示过程调用，虚箭头调用，虚箭头表示过程的表示过程的返回值返回值。BSearch(a,x,0,7)mid=3 return BSearch(a,x,4,7)main()x
7、=17 bn=BSearch(a,x,0,7)BSearch(a,x,4,7)mid=5 return BSearch(a,x,4,4)BSearch(a,x,4,4)mid=4 return 4444166.3递归算法的设计方法 递递归归算算法法既既是是一一种种有有效效的的算算法法设设计计方方法法，也也是是一一种种有有效效的的分分析析问问题题的的方方法法。递递归归算算法法求求解解问问题题的的基基本本思思想想是是：对对于于一一个个较较为为复复杂杂的的问问题题，把把原原问问题题分分解解成成若若干干个个相相对对简简单单且且类类同同的的子子问问题题，这这样样较较为为复复杂杂的的原原问问题题就就变变成
8、成了了相相对对简简单单的的子子问问题题；而而简简单单到到一一定定程程度度的的子子问问题题可可以直接求解；这样，原问题就可递推得到解。以直接求解；这样，原问题就可递推得到解。17 并并不不是是每每个个问问题题都都适适宜宜于于用用递递归归算算法法求求解解。适适宜宜于用递归算法求解的问题的于用递归算法求解的问题的充分必要条件充分必要条件是：是：（1 1）问问题题具具有有某某种种可可借借用用的的类类同同自自身身的的子子问问题题描描述述的的性质；性质；（2 2）某某一一有有限限步步的的子子问问题题（也也称称作作本本原原问问题题）有有直直接接的解存在。的解存在。18 当当一一个个问问题题存存在在上上述述两
9、两个个基基本本要要素素时时，设设计计该该问问题的题的递归算法的方法递归算法的方法是：是：（1 1）把把对对原原问问题题的的求求解解设设计计成成包包含含有有对对子子问问题题求求解解的的形式。形式。（2 2）设计递归出口。）设计递归出口。19 例例6-3 6-3 设设计计模模拟拟汉汉诺诺塔塔问问题题求求解解过过程程的的算算法法。汉汉诺诺塔塔问问题题的的描描述述是是：设设有有3 3根根标标号号为为A A，B B，C C的的柱柱子子，在在A A柱柱上上放放着着n n个个盘盘子子，每每一一个个都都比比下下面面的的略略小小一一点点，要要求求把把A A柱柱上上的的盘盘子子全全部部移移到到C C柱柱上上，移移
10、动动的的规规则则是是：（1 1）一一次次只只能能移移动动一一个个盘盘子子；（2 2）移移动动过过程程中中大大盘盘子子不不能能放放在在小小盘盘子子上上面面；（3 3）在在移移动动过过程程中中盘盘子子可可以放在以放在A A，B B，C C的任意一个柱子上。的任意一个柱子上。问题分析问题分析：可以用递归方法求解：可以用递归方法求解n n个盘子的汉诺塔问个盘子的汉诺塔问题。题。20基本思想基本思想：1 1个个盘盘子子的的汉汉诺诺塔塔问问题题可可直直接接移移动动。n n个个盘盘子子的的汉汉诺诺塔塔问问题题可可递递归归表表示示为为，首首先先把把上上边边的的n-1n-1个个盘盘子子从从A A柱柱移移到到B
11、B柱柱，然然后后把把最最下下边边的的一一个个盘盘子子从从A A柱柱移移到到C C柱柱，最最后把移到后把移到B B柱的柱的n-1n-1个盘子再移到个盘子再移到C C柱。柱。4 4个盘子汉诺塔问题的递归求解示意图如下图所示。个盘子汉诺塔问题的递归求解示意图如下图所示。21n-1n原柱原柱A辅助柱辅助柱B目标柱目标柱C22 算法设计：首先，盘子的个数算法设计：首先，盘子的个数n n是必须的一个输入参是必须的一个输入参数，对数，对n n个盘子个盘子,我们可从上至下依次编号为我们可从上至下依次编号为1,2,1,2,n,n；其；其次，输入参数还需有次，输入参数还需有3 3个柱子的代号个柱子的代号,我们令我
12、们令3 3个柱子的参个柱子的参数名分别为数名分别为fromPegfromPeg，auxPegauxPeg和和toPegtoPeg；最后，汉诺塔问题；最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是的求解是一个处理过程，因此算法的输出是n n个盘子从柱个盘子从柱子子fromPegfromPeg借助柱子借助柱子auxPegauxPeg移动到柱子移动到柱子toPegtoPeg的移动步骤，的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：我们设计每一步的移动为屏幕显示如下形式的信息：Move Disk i from Peg X to Peg YMove Disk i from Peg X
13、 to Peg YMove Disk i from Peg X to Peg YMove Disk i from Peg X to Peg Y这样，汉诺塔问题的这样，汉诺塔问题的递归算法可设计如下递归算法可设计如下：23voidtowers(intn,charfromPeg,chartoPeg,charauxPeg)if(n=1)/递归出口递归出口printf(%s%c%s%cn,movedisk1frompeg,fromPeg,topeg,toPeg);return;/把把n-1个圆盘从个圆盘从fromPeg借助借助toPeg移至移至auxPegtowers(n-1,fromPeg,auxP
14、eg,toPeg);/把圆盘把圆盘n由由fromPeg直接移至直接移至toPegprintf(%s%d%s%c%s%cn,movedisk,n,frompeg,fromPeg,topeg,toPeg);/把把n-1个圆盘从个圆盘从auxPeg借助借助fromPeg移至移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);24测试代码如下测试代码如下：#includevoidmain(void)Towers(4,A,C,B);程序运行的输出信息如下：程序运行的输出信息如下：25Move Disk 1 from Peg A to Peg BMove Disk 2 from
15、 Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 3 from Peg A to Peg BMove Disk 1 from Peg C to Peg AMove Disk 2 from Peg C to Peg BMove Disk 1 from Peg A to Peg BMove Disk 4 from Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 2 from Peg B to Peg AMove Disk 1 from Peg C to Peg AMove D
16、isk 3 from Peg B to Peg CMove Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B to Peg C26结结合合本本节节和和6.26.2节节的的讨讨论论，我我们们可可总总结结如如下下：递递归归算算法法的的执执行行过过程程是是不不断断地地自自调调用用，直直到到到到达达递递归归出出口口才才结结束束自自调调用用过过程程；到到达达递递归归出出口口后后，递递归归算算法法开开始始按按最最后后调调用用的的过过程程最最先先返返回回的的次次序序返返回回；返返回回到到最最外外层层
17、的的调调用用语语句句时时递归算法执行过程结束。递归算法执行过程结束。276.4递归过程和运行时栈 对于非递归函数，调用函数在调用被调用函对于非递归函数，调用函数在调用被调用函数前，系统要数前，系统要保存保存以下两类以下两类信息信息：（1 1）调用函数的返回地址（从而能执行下一）调用函数的返回地址（从而能执行下一语句）；语句）；（2 2）调用函数的局部变量值。）调用函数的局部变量值。当执行完被调用函数，返回调用函数前，系当执行完被调用函数，返回调用函数前，系统首先要统首先要恢复恢复调用函数的调用函数的局部变量值局部变量值，然后，然后返回返回调用函数的调用函数的返回地址返回地址。递归函数被调用时，
18、系统要做的工作和非递递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在归函数被调用时系统要作的工作在形式上形式上类同，类同，但保存信息的但保存信息的内容内容和和方法方法不同。不同。28保存内容：保存内容：每一层递归调用所需要保存的信息构成一个每一层递归调用所需要保存的信息构成一个工作记录工作记录，通常包括如下内容：通常包括如下内容：（1 1）本次递归调用中的局部变量值；）本次递归调用中的局部变量值；（2 2）返回地址，即本次递归过程调用语句的后继语句）返回地址，即本次递归过程调用语句的后继语句的地址；的地址；（3 3）本次调用中与形参结合的实参值，包括函数名、）本次调用中与形
19、参结合的实参值，包括函数名、引用参数与数值参数等。引用参数与数值参数等。工作记录工作记录 局部变量局部变量 返回地址返回地址 参参 数数29保存方法保存方法:递归函数被调用时，系统在运行递归函数前也要保存上递归函数被调用时，系统在运行递归函数前也要保存上述两类信息。但因为递归的函数的运行特点，是最后被调用述两类信息。但因为递归的函数的运行特点，是最后被调用的函数要最先被返回，若按非递归函数那样保存信息，显然的函数要最先被返回，若按非递归函数那样保存信息，显然要出错。要出错。由于堆栈的后进先出特性正好与递归函数调用和返回的由于堆栈的后进先出特性正好与递归函数调用和返回的过程吻合，因此，高级程序设
20、计语言利用堆栈保存递归函数过程吻合，因此，高级程序设计语言利用堆栈保存递归函数调用的信息，系统用于保存递归函数调用信息的堆栈称为调用的信息，系统用于保存递归函数调用信息的堆栈称为运运行时栈行时栈。运行时栈示意图运行时栈示意图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m参参数数m局部变量局部变量2返回地址返回地址2参参数数2局部变量局部变量1返回地址返回地址1参参数数130 递归函数被调用时，在每进入下一层递归调用时，系递归函数被调用时，在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返
21、回一层递归调用，就退栈一个工运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。作记录。因为栈顶的工作记录必定是当前正在运行的递归函数因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以的工作记录，所以栈顶的工作记录栈顶的工作记录也称为也称为活动记录活动记录。工作记录工作记录活动记录活动记录运行时栈示意图运行时栈示意图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m参参数数m局部变量局部变量2返回地址返回地址2参参数数2局部变量局部变量1返回地址返回地址1参参数数1我们以计算阶乘的递归函数为例，说明递归函数调用我们以计算阶乘的递归函数为例，说明递归函数调用时运行时栈中工作
22、记录的变化过程。时运行时栈中工作记录的变化过程。31longFact(intn)intx;longy;Ifn=0return1;elsex=n-1;y=Fact(x);returnn*y;由于函数的地址是系统动态分配的，调用函数的返回地址因此也由于函数的地址是系统动态分配的，调用函数的返回地址因此也是动态变化的，不好给出具体数值，故下图中没有给出调用函数的是动态变化的，不好给出具体数值，故下图中没有给出调用函数的返回地址。返回地址。32栈顶栈顶321栈底栈底0nxyFact初始时初始时运行时栈的变化过程运行时栈的变化过程栈顶栈顶321栈底栈底03*nxyFact调用调用Fact(3)栈顶栈顶3
23、212*栈底栈底032*nxyFact调用调用Fact(2)栈顶栈顶321*121*栈底栈底032*nxyFact调用调用Fact(1)栈顶栈顶30*1210121*栈底栈底032*nxyFact调用调用Fact(0)栈顶栈顶321011121*栈底栈底032*nxyFact返回返回Fact(0)栈顶栈顶3212112栈底栈底032*nxyFact返回返回Fact(1)栈顶栈顶321栈底栈底03226nxyFact返回返回Fact(2)栈顶栈顶321栈底栈底0nxyFact返回返回Fact(3)longFact(intn)intx;longy;Ifn=0return1;elsex=n-1;y=
24、Fact(x);returnn*y;336.5递归算法的效率分析 我们先以斐波那契我们先以斐波那契(Fibonacci)(Fibonacci)数列递归算法的数列递归算法的执行效率为例来讨论递归算法的执行效率问题。执行效率为例来讨论递归算法的执行效率问题。斐波那契数列斐波那契数列Fib(n)Fib(n)的递推定义是：的递推定义是：如如Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(4)=3,Fib(5)=5,Fib(4)=3,Fib(5)=5,Fib(n)=,Fib(n)=34求第求第n n项
25、斐波那契数列的项斐波那契数列的递归函数过程递归函数过程如下：如下：longFib(intn)if(n=0|n=1)returnn;/递归出口递归出口elsereturnFib(n-1)+Fib(n-2);/递归调用递归调用35 求求Fib(5)Fib(5)的递归计算过程如图所示。的递归计算过程如图所示。Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)斐波那契数列斐波那契数列Fib(5)Fib(5)的递归调用树的递归调用树36为了计算为了计算Fib(5)，需要先计算
26、，需要先计算Fib(4)和和Fib(3)；而；而计算计算Fib(4)又需要计算又需要计算Fib(3)（再一次计算）和（再一次计算）和Fib(2)，.由上图可知，为了计算由上图可知，为了计算Fib(5)，需要计算，需要计算1次次Fib(4)，2次次Fib(3)，3次次Fib(2)，5次次Fib(1)，3次次Fib(0).加上加上Fib(5)1次，所有的递归调用次数达到次，所有的递归调用次数达到15次。（图中次。（图中15个点表示个点表示15次运算）次运算）更一般地，设更一般地，设Fib(n)需要总的递归调用次数为需要总的递归调用次数为NumCall(n)，那么，那么NumCall(n)等于多少？
27、等于多少？NumCall(n)=NumCall(n-1)+NumCall(n-2)+1NumCall(0)=1,NumCall(1)=1 可以求得可以求得NumCall的通项。也可以由下面的关系得的通项。也可以由下面的关系得到到NumCall的通项。的通项。NumCall(n)=2*Fib(n+1)-1。可以证明，计算斐波那契数列的递归函数可以证明，计算斐波那契数列的递归函数Fib(n)的的时间复杂度时间复杂度为为O(2n)。37计算斐波那契数列计算斐波那契数列Fib(n)问题，我们也可根据公式问题，我们也可根据公式写出写出循环方式求解的函数如下循环方式求解的函数如下：3839longFib2
28、(intn)longintoneBack,twoBack,current;inti;if(n=0|n=1)returnn;elseoneBack=1;twoBack=0;for(i=2;i=n;i+)current=oneBack+twoBack;twoBack=oneBack;oneBack=current;returncurrent;40上述循环方式的计算斐波那契数列的函数上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为的时间复杂度为O(n)。对比循环结构的。对比循环结构的Fib2(n)和递归结构的和递归结构的Fib(n)可发现可发现:循环结构循环结构的的Fib2(n)算法
29、在计算第算法在计算第n项的斐波那项的斐波那契数列时契数列时保存了保存了当前已经计算得到的当前已经计算得到的第第n-1项和第项和第n-2项的斐波那契数列项的斐波那契数列，因此其，因此其时间复杂度为时间复杂度为O(n)；而而递归结构递归结构的的Fib(n)算法在计算第算法在计算第n项的斐波项的斐波那契数列时，那契数列时，必须首先计算第必须首先计算第n-1项和第项和第n-2项的斐项的斐波那契数列波那契数列，而某次递归计算得出的斐波那契数列，而某次递归计算得出的斐波那契数列，如如Fib(n-1)、Fib(n-2)等等无法保存无法保存，下一次要用到，下一次要用到时还需要重新递归计算，因此其时还需要重新递
30、归计算，因此其时间复杂度为时间复杂度为O(2n)。下面我们再看看汉诺塔的时间复杂度。下面我们再看看汉诺塔的时间复杂度。设移动设移动n个盘子的步数为个盘子的步数为H(n)，我们再看看示意图。，我们再看看示意图。4142n-1n这一步这一步实际有实际有H(n-1)步步这只这只需需1步步这一步又需这一步又需要要H(n-1)步步故移动故移动n个圆盘的总步数个圆盘的总步数H(n)=H(n-1)+1+H(n-1)=2H(n-1)+1原柱原柱A辅助柱辅助柱B目标柱目标柱C即有即有 H(n)=2H(n-1)+1 S(1)=1可以解得：可以解得：H(n)=2n-1因此因此汉诺塔的汉诺塔的时间复杂度为时间复杂度为
31、O(2n)。43446.6递归算法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而低级有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如需要采用问题的非递归结构算法。一般来说，存在如下下两种情况的递归算法两种情况的递归算法。（1 1）存在）存在不借助堆栈的循环结构的非递归算法不借助堆栈的循环结构的非递归算法，如，如阶乘计算问题、斐波那契数列的计算问题、折半查找阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。问题等。（2 2）存在）存在借助堆栈的循
32、环结构的非递归算法借助堆栈的循环结构的非递归算法，所有，所有递归算法都可以借助堆栈转换成循环结构的非递归算递归算法都可以借助堆栈转换成循环结构的非递归算法，如汉诺塔问题可以借助堆栈的循环结构实现非递法，如汉诺塔问题可以借助堆栈的循环结构实现非递归算法。归算法。45 对于第一种情况，可以直接选用循环结构对于第一种情况，可以直接选用循环结构的算法。的算法。对于第二种情况，可以把递归算法转换成对于第二种情况，可以把递归算法转换成相应的非递归算法相应的非递归算法，此时有两种转换方法：，此时有两种转换方法：一一种方法是借助堆栈种方法是借助堆栈，用非递归算法形式化模拟，用非递归算法形式化模拟递归算法的执行
33、过程；递归算法的执行过程；另一种方法是另一种方法是根据要求根据要求解问题的特点，解问题的特点，设计借助堆栈的循环结构算法设计借助堆栈的循环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻后进先出特点正好和递归函数的运行特点相吻合。合。通常，一个递归算法的模拟算法的复杂度通常，一个递归算法的模拟算法的复杂度与其本身的复杂度一样。与其本身的复杂度一样。46 例例6-6 6-6 借助堆栈模拟系统的运行时进栈、借助堆栈模拟系统的运行时进栈、出栈过程，把汉诺塔问题的递归算法转化为非出栈过程，把汉诺塔问题的递归算法转化为非递
34、归算法，并分析非递归算法的时间复杂度。递归算法，并分析非递归算法的时间复杂度。476.7设计举例6.7.1 6.7.1 一般递归算法设计举例一般递归算法设计举例 例例6-5 6-5 设计一个输出如下形式数值的递归算法。设计一个输出如下形式数值的递归算法。n n n .nn n n .n.3 3 3 3 3 3 2 22 21 148问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1。当当参参数数减减到到0时时不不再再输输出出任任何何数数据据值值，
35、因因此此递递归归的的出出口口是是当当参参数数n0时空语句返回。时空语句返回。voidDisplay(intn)inti;for(i=1;i=n;i+)coutsetw(s)n;cout0)Display(n-1);/递归递归/n=0为递归出口，递归出口为空语句为递归出口，递归出口为空语句49例例6-6设设计计求求解解委委员员会会问问题题的的算算法法。委委员员会会问问题题是是：从从一一个个有有n个个人人的的团团体体中中抽抽出出k(kn)个个人人组组成成一一个个委委员员会会，计计算算共共有多少种构成方法。有多少种构成方法。问问题题分分析析：从从n个个人人中中抽抽出出k(kn)个个人人的的问问题题是
36、是一一个个组组合合问问题题。即即求求组组合合数数公公式式C(n,k)。由由于于要要所所用用递递归归算算法法,大大家家容容易易想到公式想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),这这个个公公式式大大家家可可以以这这样样理理解解:把把n个个人人固固定定位位置置后后，从从n个个人人中中抽抽出出k个个人人的的问问题题可可分分解解为为两两部部分分之之和和：第第一一部部分分是是第第一一个个人人包包括括在在k个个人人中中，第第二二部部分分是是第第一一个个人人不不包包括括在在k个个人人中中。对对于于第第一一部部分分，则则问问题题简简化化为为从从n-1个个人人中中抽抽出出k-1个个人人的的问
37、问题题；对对于于第第二二部部分分，则则问问题题简简化化为为从从n-1个个人人中中抽抽出出k个个人人的的问题。问题。50当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是，这是算法的递归出口。因此，委员会问题的算法的递归出口。因此，委员会问题的递推定义式递推定义式为：为：intComm(intn,intk)if(n1|kn)return0;if(k=0)return1;if(n=k)return1;returnComm(n-1,k-1)+Comm(n-1,k);51例例6-7求两个正整数求两个正整数n和和m最大公约数的递推定义式为：最大公约数的递推定义式为：
38、要求：要求：（1）编写求解该问题的递归算法；）编写求解该问题的递归算法；（2）分分析析当当调调用用语语句句为为Gcd(30,4)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（3）分分析析当当调调用用语语句句为为Gcd(5,97)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。52解：（解：（1）递归算法如下：递归算法如下：intGcd(intn,intm)if(n0|mn)returnGcd(m,n);elsereturnGcd(m,n%m);53（2）调调用用语语句句为为Gcd(30,4)时时，因因mn，
39、递递归归调调用用Gcd(4,2)；因因mn，递递归归调调用用Gcd(97,5)；因因mn，递递归归调调用用Gcd(5,2)；因因mn，递递归归调调用用Gcd(2,1)；因因mn，递递归归调调用用Gcd(1,0)；因因m=0，到到达达递递归归出出口口，函函数数最最终终返返回回值值为为n=1，即，即5和和97的最大公约数为的最大公约数为1。（4）循环结构算法循环结构算法int Gcd2(int n,int m)int tn,tm,temp;if(n 0|m n)tn=m;tm=n;else tn=n;tm=m;While tm!=0 temp=tn;tn=tm;tm=temp%tm;return
40、tn;54556.7.2 6.7.2 回溯法及其设计举例回溯法及其设计举例 回溯法是递归算法的一种特殊形式，回溯法的回溯法是递归算法的一种特殊形式，回溯法的基本思基本思想想是：对一个包括有很多结点，每个结点有若干个搜索分是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支其他尚未搜索过的分支；如果发现这个结点也无法再继续；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。为止。56 例例6-10 6-10 设计求解迷宫问题的算法并用设计求解迷宫问题的算法并用实际例子测试。实际例子测试。