《第6章 递算法》由会员分享，可在线阅读，更多相关《第6章 递算法（56页珍藏版）》请在金锄头文库上搜索。
1、6.1递归的概念递归的概念一、在日常生活中，递归一词较常用于一、在日常生活中，递归一词较常用于描述以自相似方法重复事物的过程。描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出镜中嵌套的图像是以无限递归的形式出现的。现的。 甘僳腐渍枉鞘摊皖戮筑实嫂湛焕匡欢秽宗谅扎鸿贷淀俘己冰惩正胸唆逸隔第6章递算法第6章递算法2德罗斯特效应（英语：德罗斯特效应（英语：Droste effectDroste effect）是递归）是递归的一种视觉形式。图中的一种视觉形式。图中女性手持的物体中有一女性手持的物体中有一幅她本人手
2、持同一物体幅她本人手持同一物体的小图片，进而小图片的小图片，进而小图片中还有更小的一幅她手中还有更小的一幅她手持同一物体的图片，依持同一物体的图片，依此类推。此类推。擅钉订开馈王脆脂稻爆侠殿威疡盛弛频奸石械愈农亭迎烧斡权淳估槐阂疗第6章递算法第6章递算法3二、在数学与计算机科学中，递归是指在函数二、在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。的定义中使用函数自身的方法。例：第例：第5 5个人的年龄比第个人的年龄比第4 4个的年龄大个的年龄大2 2岁，有岁，有4 4个人的年龄比第个人的年龄比第3 3个的年龄大个的年龄大2 2岁，有岁，有3 3个人个人的年龄比第的年龄比第2 2
3、个的年龄大个的年龄大2 2岁，有岁，有2 2个人的年龄个人的年龄比第比第1 1个的年龄大个的年龄大2 2岁，第岁，第1 1个的年龄个的年龄1010岁。岁。袁襟静曼撵桂悉斥粹斧赫姿础趴臆置沫汾獭鲜抽鳖夜某官舱伎盗凋瘟虱打第6章递算法第6章递算法4例：阶乘的定义。例：阶乘的定义。羊竭姨转蚤拔谋锐美掣魄膊纂蔑故消拾座振疥鳃捎嫁漾辊揖搀忌挟剩庄彝第6章递算法第6章递算法5在下面二种情况中存在算法调用自己的情况：在下面二种情况中存在算法调用自己的情况：（1 1）问题的定义是递推的）问题的定义是递推的阶乘函数的阶乘函数的常见定义常见定义是：是：抓崖粉哲准邵窝永坝抢峭躁艺冯房兴潮聘型污侄肩贯始豪笆怯友郸密廉
4、拎第6章递算法第6章递算法6也可定义为：也可定义为：写成函数形式，则为：写成函数形式，则为： 这种函数定义的方法是这种函数定义的方法是用阶乘函数自己本身定义了用阶乘函数自己本身定义了阶乘函数阶乘函数，称上式为阶乘函数的，称上式为阶乘函数的递推定义式递推定义式。靛前梅舰周管高侧拳滑峦腆绝怪缴鸥缝窖饼子癌钨茧抄醋蹬闽鞭颁姓族搜第6章递算法第6章递算法7（2）问题的解法存在自调用）问题的解法存在自调用 一一个个典典型型的的例例子子是是在在有有序序数数组组中中查查找找一一个个数数据据元元素素是是否否存在的存在的折半查找算法折半查找算法。 如下例中查找元素如下例中查找元素1717。第一次第一次:下标下标
5、01234567元素值元素值134517183133lowmidhighxamid第二次第二次:下标下标01234567元素值元素值134517183133lowmidhighxamid第三次第三次:下标下标01234567元素值元素值134517183133lowhighx=amidmidBSrch=4mid=(low+high)/2楚燎接溶朵茨太普勋络化图吾美度品栏目踞献中龟羞挣陡挑鉴根寒奢奔洛第6章递算法第6章递算法86.2递归算法的执行过程递归算法的执行过程 例例6-1 6-1 给出按照给出按照阶乘函数的递推定义式阶乘函数的递推定义式计算阶乘函数的计算阶乘函数的递归算法，并给出递归算法
6、，并给出n = 3n = 3时递归算法的执行过程。时递归算法的执行过程。 设计：按照设计：按照阶乘函数的递推定义式阶乘函数的递推定义式计算阶乘函数的递归计算阶乘函数的递归算法如下：算法如下： 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);/在上半
7、区查找在上半区查找蓬肃纠睁烟劫浙沿握贝搪身抿榔髓迄哩碱蜂筹于批豢惑懒笼贰奖敷缎杂龚第6章递算法第6章递算法13测试代码设计如下：测试代码设计如下：#includemain(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);云厄浚骏貌吉嗅谋怯拙阶稳彤删胖月刻滨渡闷漳宁烁鞠峻漳契慰社捣卡啮第6章递算法第6章递算法14BSearch(a, x, 0,7)BSearch(a, x, 0,7)的递归调
8、用过程如下图所示，其的递归调用过程如下图所示，其中，中，实箭头实箭头表示过程表示过程调用，虚箭头调用，虚箭头表示过程的表示过程的返回值返回值。 BSearch(a, x, 0, 7) mid=3 return BSearch(a, x, 4, 7)main() x=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 4444胡搪邵爱弊窥茶臀檄衷稍型体呵桓膀屹玩摹益株近碾贵拜赂蝶轰陡慎沮译第6章递算法第6章递算法156.3递归
9、算法的设计方法递归算法的设计方法 递递归归算算法法既既是是一一种种有有效效的的算算法法设设计计方方法法，也也是是一一种种有有效效的的分分析析问问题题的的方方法法。递递归归算算法法求求解解问问题题的的基基本本思思想想是是：对对于于一一个个较较为为复复杂杂的的问问题题，把把原原问问题题分分解解成成若若干干个个相相对对简简单单且且类类同同的的子子问问题题，这这样样较较为为复复杂杂的的原原问问题题就就变变成成了了相相对对简简单单的的子子问问题题；而而简简单单到到一一定定程程度度的的子子问问题题可可以直接求解；这样，原问题就可递推得到解。以直接求解；这样，原问题就可递推得到解。蒲惩薄株坏岂割嘱媚枯乡亡健
10、呛均韭赵馈涕选肃昨科睦绘笼复组习担泪览第6章递算法第6章递算法16 并并不不是是每每个个问问题题都都适适宜宜于于用用递递归归算算法法求求解解。适适宜宜于用递归算法求解的问题的于用递归算法求解的问题的充分必要条件充分必要条件是：是：（1 1）问问题题具具有有某某种种可可借借用用的的类类同同自自身身的的子子问问题题描描述述的的性质；性质；（2 2）某某一一有有限限步步的的子子问问题题（也也称称作作本本原原问问题题）有有直直接接的解存在。的解存在。膊嫩楚极苹蚊薪疟溃呀桓剑灾委讽樊湃嚷棵敌串僻责型酞湿间庙彝桃腐砧第6章递算法第6章递算法17 当当一一个个问问题题存存在在上上述述两两个个基基本本要要素素
11、时时，设设计计该该问问题的题的递归算法的方法递归算法的方法是：是：（1 1）把把对对原原问问题题的的求求解解设设计计成成包包含含有有对对子子问问题题求求解解的的形式。形式。（2 2）设计递归出口。）设计递归出口。工父被棒村荤漂婶铅桂邮难少距秽异佑跟悟慢忧嫂崭幕盖麦娄顷赔仁粤撬第6章递算法第6章递算法18 例例6-3 6-3 设设计计模模拟拟汉汉诺诺塔塔问问题题求求解解过过程程的的算算法法。汉汉诺诺塔塔问问题题的的描描述述是是：设设有有3 3根根标标号号为为A A，B B，C C的的柱柱子子，在在A A柱柱上上放放着着n n个个盘盘子子，每每一一个个都都比比下下面面的的略略小小一一点点，要要求求
12、把把A A柱柱上上的的盘盘子子全全部部移移到到C C柱柱上上，移移动动的的规规则则是是：（1 1）一一次次只只能能移移动动一一个个盘盘子子；（2 2）移移动动过过程程中中大大盘盘子子不不能能放放在在小小盘盘子子上上面面；（3 3）在在移移动动过过程程中中盘盘子子可可以放在以放在A A，B B，C C的任意一个柱子上。的任意一个柱子上。问题分析问题分析：可以用递归方法求解：可以用递归方法求解n n个盘子的汉诺塔问个盘子的汉诺塔问题。题。训者历封排脂项霹酶棕媚典曝冈身渠很舶吗粤沛溜贵柄沙疟天淹车搭娃插第6章递算法第6章递算法19基本思想基本思想：1 1个个盘盘子子的的汉汉诺诺塔塔问问题题可可直直接
13、接移移动动。n n个个盘盘子子的的汉汉诺诺塔塔问问题题可可递递归归表表示示为为，首首先先把把上上边边的的n-1n-1个个盘盘子子从从A A柱柱移移到到B B柱柱，然然后后把把最最下下边边的的一一个个盘盘子子从从A A柱柱移移到到C C柱柱，最最后把移到后把移到B B柱的柱的n-1n-1个盘子再移到个盘子再移到C C柱。柱。4 4个盘子汉诺塔问题的递归求解示意图如下图所示。个盘子汉诺塔问题的递归求解示意图如下图所示。 蚁窑锗翠裙治腥敲敞麦伏筋丈困耿惨胁甘课接昏翰倡转锤攫愉乎单承害沦第6章递算法第6章递算法20n-1n原柱原柱A辅助柱辅助柱B目标柱目标柱C拧番婿爷燥牛夏蠢铡雨紫扁漫投堂纳枫疚樊箩丝
14、诲淌释候喷舀玻滋暑粉猎第6章递算法第6章递算法21 算法设计：首先，盘子的个数算法设计：首先，盘子的个数n n是必须的一个输入参是必须的一个输入参数，对数，对n n个盘子个盘子, ,我们可从上至下依次编号为我们可从上至下依次编号为1,2,1,2,n,n；其；其次，输入参数还需有次，输入参数还需有3 3个柱子的代号个柱子的代号, ,我们令我们令3 3个柱子的参个柱子的参数名分别为数名分别为fromPegfromPeg，auxPegauxPeg和和toPegtoPeg；最后，汉诺塔问题；最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是的求解是一个处理过程，因此算法的输出是n n个盘子从柱个盘
15、子从柱子子fromPegfromPeg借助柱子借助柱子auxPegauxPeg移动到柱子移动到柱子toPegtoPeg的移动步骤，的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：我们设计每一步的移动为屏幕显示如下形式的信息：Move Disk i from Peg X to Peg YMove Disk i from Peg X to Peg YMove Disk i from Peg X to Peg YMove Disk i from Peg X to Peg Y这样，汉诺塔问题的这样，汉诺塔问题的递归算法可设计如下递归算法可设计如下： 消耶温罗杰宠战绵坪邮蝗凰县掣桐若虽被磅芳腕
16、雪泰砰蜕禾污聊巳桨旱苑第6章递算法第6章递算法22voidtowers(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,auxPeg,toPeg);/把圆盘把圆盘n由由fromPeg直接移至直接移至toPegprintf(%s%d%s%c%s%cn,movedisk,n,frompeg,fromP
17、eg,topeg,toPeg);/把把n-1个圆盘从个圆盘从auxPeg借助借助fromPeg移至移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);按炒撼兽糙糖浅豌簿木携单晦秦牛把仲惭翱挠污慨裕邢溯代速礼玻折权搐第6章递算法第6章递算法23测试代码如下测试代码如下：#includevoidmain(void)Towers(4,A,C,B);程序运行的输出信息如下：程序运行的输出信息如下：浅咙吹隋悬瞥锡蹈雪遇鸳心返笼矿锗牧棋秋咎漳靛钡畅余窝反匆咖霄箱进第6章递算法第6章递算法24Move Disk 1 from Peg A to Peg BMove Disk 2 f
18、rom 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 AMov
19、e Disk 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 C斌巳燎盛躺衷冤禁德充慈媒梗揭蓖硕钡吮培饰扮乡怪然皖仙邵雄颗非箔追第6章递算法第6章递算法25结结合合本本节节和和6.26.2节节的的讨讨论论，我我们们可可总总结结如如下下：递递归归算算法法的的执执行行过过程程是是不不断断地地自自调调用用，直直到到到到达达递递归归出出口口才才结结束束自自调调用用过过程程；到到达达递递归归出出口口后后，递递归归算算法法开开始始
20、按按最最后后调调用用的的过过程程最最先先返返回回的的次次序序返返回回；返返回回到到最最外外层层的的调调用用语语句句时时递归算法执行过程结束。递归算法执行过程结束。 玩你蜡了腾寺孺厕困系斯侨喀檄梅吏显靶蝉易靠廷账稗加座借葡旦悸窘痔第6章递算法第6章递算法266.4递归过程和运行时栈递归过程和运行时栈 对于非递归函数，调用函数在调用被调用函对于非递归函数，调用函数在调用被调用函数前，系统要数前，系统要保存保存以下两类以下两类信息信息： （1 1）调用函数的返回地址（从而能执行下一）调用函数的返回地址（从而能执行下一语句）；语句）； （2 2）调用函数的局部变量值。）调用函数的局部变量值。 当执行完
21、被调用函数，返回调用函数前，系当执行完被调用函数，返回调用函数前，系统首先要统首先要恢复恢复调用函数的调用函数的局部变量值局部变量值，然后，然后返回返回调用函数的调用函数的返回地址返回地址。递归函数被调用时，系统要做的工作和非递递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在归函数被调用时系统要作的工作在形式上形式上类同，类同，但保存信息的但保存信息的内容内容和和方法方法不同。不同。缝千驼且反衙抛鸣杯轩喝泞孜军茄辅竟熏银澡仗挟猿终锹挤茫搁褐车岗锗第6章递算法第6章递算法27保存内容：保存内容： 每一层递归调用所需要保存的信息构成一个每一层递归调用所需要保存的信息构成一个工作
22、记录工作记录，通常包括如下内容：通常包括如下内容： （1 1）本次递归调用中的局部变量值；）本次递归调用中的局部变量值； （2 2）返回地址，即本次递归过程调用语句的后继语句）返回地址，即本次递归过程调用语句的后继语句的地址；的地址； （3 3）本次调用中与形参结合的实参值，包括函数名、）本次调用中与形参结合的实参值，包括函数名、引用参数与数值参数等。引用参数与数值参数等。工作记录工作记录 局部变量局部变量 返回地址返回地址 参参 数数谷弧婆仓速钙火吕猴祥故霄痘递采牌溉烘馆锚稼淋磕褥钵纠慨轨赡押谷煤第6章递算法第6章递算法28保存方法保存方法: : 递归函数被调用时，系统在运行递归函数前也要保
23、存上递归函数被调用时，系统在运行递归函数前也要保存上述两类信息。但因为递归的函数的运行特点，是最后被调用述两类信息。但因为递归的函数的运行特点，是最后被调用的函数要最先被返回，若按非递归函数那样保存信息，显然的函数要最先被返回，若按非递归函数那样保存信息，显然要出错。要出错。 由于堆栈的后进先出特性正好与递归函数调用和返回的由于堆栈的后进先出特性正好与递归函数调用和返回的过程吻合，因此，高级程序设计语言利用堆栈保存递归函数过程吻合，因此，高级程序设计语言利用堆栈保存递归函数调用的信息，系统用于保存递归函数调用信息的堆栈称为调用的信息，系统用于保存递归函数调用信息的堆栈称为运运行时栈行时栈。 运
24、行时栈示意图运行时栈示意图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m参参数数m局部变量局部变量2返回地址返回地址2参参数数2局部变量局部变量1返回地址返回地址1参参数数1姜穴败惦诺尺菇郑几诛验篇闪拟棉莽益累蓉萝玩篙啄相能镍授陶沛吝凳俭第6章递算法第6章递算法29 递归函数被调用时，递归函数被调用时，在每进入下一层递归调用时，系在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。作记录。 因为栈顶的工作
25、记录必定是当前正在运行的递归函数因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以的工作记录，所以栈顶的工作记录栈顶的工作记录也称为也称为活动记录活动记录。 工作记录工作记录活动记录活动记录运行时栈示意图运行时栈示意图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m参参数数m局部变量局部变量2返回地址返回地址2参参数数2局部变量局部变量1返回地址返回地址1参参数数1踏舷恿厘峡椽器锤蓬否吨拦别瞅鹅幕量争冉媳搁盗内摆炔唇菏童梢楼拐讫第6章递算法第6章递算法30我们以计算阶乘的递归函数为例，说明递归函数调用我们以计算阶乘的递归函数为例，说明递归函数调用时运行时栈中工作记录的变化过程
26、。时运行时栈中工作记录的变化过程。longFact(intn)intx;longy;Ifn=0return1;elsex=n-1;y=Fact(x);returnn*y;阎娘器酋刀崩辜空哨揍鳃槽昼烯肠体责耀袋扎勉污埋切态摹憨鹏捏翼迪楔第6章递算法第6章递算法31由于函数的地址是系统动态分配的，调用函数的返回地址因此由于函数的地址是系统动态分配的，调用函数的返回地址因此也是动态变化的，不好给出具体数值，故下图中没有给出调用函数也是动态变化的，不好给出具体数值，故下图中没有给出调用函数的返回地址。的返回地址。栈顶栈顶321栈底栈底0nxyFact初始时初始时运行时栈的变化过程运行时栈的变化过程栈顶
27、栈顶321栈底栈底03*nxyFact调用调用Fact(3)栈顶栈顶3212*栈底栈底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)i
28、ntx;longy;Ifn=0return1;elsex=n-1;y=Fact(x);returnn*y;慕琅阑拎摔辊飞冬都钧配骂箭确椽玄逾串链呈曙即衍台替曙瘩抨沿采说曝第6章递算法第6章递算法326.5递归算法的效率分析递归算法的效率分析 我们先以斐波那契我们先以斐波那契(Fibonacci)(Fibonacci)数列递归算法的数列递归算法的执行效率为例来讨论递归算法的执行效率问题。执行效率为例来讨论递归算法的执行效率问题。 斐波那契数列斐波那契数列Fib(n)Fib(n)的递推定义是：的递推定义是：如如Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(0)=0
29、,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(4)=3,Fib(5)=5,Fib(n)=Fib(4)=3,Fib(5)=5,Fib(n)=足昂蚊倡甫半惹畴齐慷更强播医毅瓶怒侗封卸徊吧捌娥禄是光垄垛糕瞄盒第6章递算法第6章递算法33求第求第n n项斐波那契数列的项斐波那契数列的递归函数过程递归函数过程如下：如下： longFib(intn)if(n=0|n=1)returnn;/递归出口递归出口elsereturnFib(n-1)+Fib(n-2);/递归调用递归调用蓄识装啥薄赡捆颓盐狐舜褒乳缉焰辙赴裴珠仁启汗下妥膝歌钾稼朽傻矣烤第6章递算法第6章递算法34 求求Fib(5)F
30、ib(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)的递归调用树的递归调用树冕和瑚闰庄郑职歼樱阎帛筹谁拔毛托匝绽滇钦孰困蜕昌坑型肘铝巧汐原倔第6章递算法第6章递算法35为了计算为了计算Fib(5)，需要先计算，需要先计算Fib(4)和和Fib(3)；而；而计算计算Fib(4)又需要计算又需要计算Fib(3)（再一次计算）和（再一次计算）和Fib(2)，.由上图可
31、知，为了计算由上图可知，为了计算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)等于多少？等于多少？猖豆纽搂翼陵昼犯辨茧虐桔吟雍镀啤涅缝吠变黔酉堆圣媚董官霄视磊恫蕴第6章递算法第6章递算法36NumCall(n)=NumCall(n-1)+Num
32、Call(n-2)+1NumCall(0)=1,NumCall(1)=1可以求得可以求得NumCall的通项。也可以由下面的关系得的通项。也可以由下面的关系得到到NumCall的通项。的通项。NumCall(n)=2*Fib(n+1)-1。可以证明，计算斐波那契数列的递归函数可以证明，计算斐波那契数列的递归函数Fib(n)的的时间复杂度时间复杂度为为O(2n)。芜哉竿冠颈谊呸厄舌老刷凋琅一业弄虏峨矿军赏吼笺衅穗夹雌存扭殿曲苇第6章递算法第6章递算法37计算斐波那契数列计算斐波那契数列Fib(n)问题，我们问题，我们也可根据公式写出也可根据公式写出循环方式求解的函数循环方式求解的函数如下如下：砷
33、悸门苗际业渭陪仆千寓拽睬毫陀酷汰刚刻泳辉粪捧椎蒙含踞杠戏哗疮伴第6章递算法第6章递算法38longFib2(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;潦瓷果拇篮怨停彻常锄桓频藏豌游室涝山架稳摆侧铣戎接彬比遣郁据割践第6章递算法第6章递算法39上述循环方式的计算斐波那契数列的函数上述循环方式的计算斐波那契
34、数列的函数Fib2(n)的时间复杂度为的时间复杂度为O(n)。对比循环结构的。对比循环结构的Fib2(n)和递归结构的和递归结构的Fib(n)可发现可发现:循环结构循环结构的的Fib2(n)算法在计算第算法在计算第n项的斐波那项的斐波那契数列时契数列时保存了保存了当前已经计算得到的当前已经计算得到的第第n-1项和第项和第n-2项的斐波那契数列项的斐波那契数列，因此其，因此其时间复杂度为时间复杂度为O(n)；而而递归结构递归结构的的Fib(n)算法在计算第算法在计算第n项的斐波项的斐波那契数列时，那契数列时，必须首先计算第必须首先计算第n-1项和第项和第n-2项的斐项的斐波那契数列波那契数列，而
35、某次递归计算得出的斐波那契数列，而某次递归计算得出的斐波那契数列，如如Fib(n-1)、Fib(n-2)等等无法保存无法保存，下一次要用到，下一次要用到时还需要重新递归计算，因此其时还需要重新递归计算，因此其时间复杂度为时间复杂度为O(2n)。让巡筷账贿蔗阁莉直韭陵摸炙郎韩赋猾采救墩蓉敲敏注孪胜满娘语郭鞠钒第6章递算法第6章递算法40下面我们再看看汉诺塔的时间复杂下面我们再看看汉诺塔的时间复杂度。度。设移动设移动n个盘子的步数为个盘子的步数为H(n)，我们，我们再看看示意图。再看看示意图。娥玲耗拨务笺锯吕宙搁泌唯畦馆娱执炸颁酷挤哗匡犹舆宁秉娶舱猜笛瞪洱第6章递算法第6章递算法41n-1n这一步
36、这一步实际有实际有H(n-1)步步这只这只需需1步步这一步又需这一步又需要要H(n-1)步步故移动故移动n个圆盘的总步数个圆盘的总步数H(n)=H(n-1)+1+H(n-1)=2H(n-1)+1原柱原柱A辅助柱辅助柱B目标柱目标柱C荧魏髓展笼们根俯抑掉威区碧嗓齐瞅云臻粟足查跑泡江钉芍换刽娘沟歹梯第6章递算法第6章递算法42即有即有H(n)=2H(n-1)+1S(1)=1可以解得：可以解得：H(n)=2n-1因此因此汉诺塔的汉诺塔的时间复杂度为时间复杂度为O(2n)。于庙浊抗桥邀满磕敌友兑栖鼎跪鹃莎蝉枉笛朵赡昨禄林硫弛俺寐豺束酚造第6章递算法第6章递算法436.6递归算法到非递归算法的转换递归算
37、法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而低级有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如需要采用问题的非递归结构算法。一般来说，存在如下下两种情况的递归算法两种情况的递归算法。 （1 1）存在）存在不借助堆栈的循环结构的非递归算法不借助堆栈的循环结构的非递归算法，如，如阶乘计算问题、斐波那契数列的计算问题、折半查找阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。问题等。 （2 2）存在）存在借助堆栈的循环结构的非递归算法借助堆栈的
38、循环结构的非递归算法，所有，所有递归算法都可以借助堆栈转换成循环结构的非递归算递归算法都可以借助堆栈转换成循环结构的非递归算法，如汉诺塔问题可以借助堆栈的循环结构实现非递法，如汉诺塔问题可以借助堆栈的循环结构实现非递归算法。归算法。洛咯玄脑办务番抹缕珠涟土鹊埔范藩郎澡敏吠撰边忿疏蒋命湃探驻觅笼娟第6章递算法第6章递算法44 对于第一种情况，可以直接选用循环结构对于第一种情况，可以直接选用循环结构的算法。的算法。 对于第二种情况，可以把递归算法转换成对于第二种情况，可以把递归算法转换成相应的非递归算法相应的非递归算法，此时有两种转换方法：，此时有两种转换方法：一一种方法是借助堆栈种方法是借助堆栈
39、，用非递归算法形式化模拟，用非递归算法形式化模拟递归算法的执行过程；递归算法的执行过程；另一种方法是另一种方法是根据要求根据要求解问题的特点，解问题的特点，设计借助堆栈的循环结构算法设计借助堆栈的循环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻后进先出特点正好和递归函数的运行特点相吻合。合。 通常，一个递归算法的模拟算法的复杂度通常，一个递归算法的模拟算法的复杂度与其本身的复杂度一样。与其本身的复杂度一样。膘否清弛结论隘年世啤驳哀肥瘩系阴窗秦疯噶宙奏僳形咬弱盐凤汐睡确协第6章递算法第6章递算法45 例例6-6
40、 6-6 借助堆栈模拟系统的运行时进栈、借助堆栈模拟系统的运行时进栈、出栈过程，把汉诺塔问题的递归算法转化为非出栈过程，把汉诺塔问题的递归算法转化为非递归算法，并分析非递归算法的时间复杂度。递归算法，并分析非递归算法的时间复杂度。驰哑吮膝恿樊烁川渭篓旦秧侦啮授畸鸽谆扒弦价耕爬促扣西恬伞希卖梭亢第6章递算法第6章递算法466.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 1绒凌告亲感峡
41、胆耳齐伐痛渠腾嗡抠炳喂庇隔咆契微善饿佑陛辖逼乘糙脂汾第6章递算法第6章递算法47问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1。当当参参数数减减到到0时时不不再再输输出出任任何何数数据据值值，因因此此递递归归的的出出口口是是当当参参数数n0时空语句返回。时空语句返回。voidDisplay(intn)inti;for(i=1;i=n;i+)coutsetw(s)n;cout0)Display(n-1);/递归递归/n=0为递归出口，递归出口为
42、空语句为递归出口，递归出口为空语句码企壁袜嘿灭琳窘榴岂婆诽馆络养仁摊蓬鸭雍狭坎驯忠崇东瓶暴泉膳二芽第6章递算法第6章递算法48例例6-6设设计计求求解解委委员员会会问问题题的的算算法法。委委员员会会问问题题是是：从从一一个个有有n个个人人的的团团体体中中抽抽出出k(kn)个个人人组组成成一一个个委委员员会会，计计算算共共有多少种构成方法。有多少种构成方法。问问题题分分析析：从从n个个人人中中抽抽出出k(kn)个个人人的的问问题题是是一一个个组组合合问问题题。即即求求组组合合数数公公式式C(n,k)。由由于于要要所所用用递递归归算算法法,大大家家容容易想到公式易想到公式:C(n,k)=C(n-1
43、,k-1)+C(n-1,k),这这个个公公式式大大家家可可以以这这样样理理解解:把把n个个人人固固定定位位置置后后，从从n个个人人中中抽抽出出k个个人人的的问问题题可可分分解解为为两两部部分分之之和和：第第一一部部分分是是第第一一个个人人包包括括在在k个个人人中中，第第二二部部分分是是第第一一个个人人不不包包括括在在k个个人人中中。对对于于第第一一部部分分，则则问问题题简简化化为为从从n-1个个人人中中抽抽出出k-1个个人人的的问问题题；对对于于第第二二部部分分，则则问问题题简简化化为为从从n-1个个人人中中抽抽出出k个个人人的的问题。问题。祝导坝庐缀驳住丧锁狮涡悠此规上措魔胳边恼唬岛侯池沦痰
44、借莆垫氛间奈第6章递算法第6章递算法49当当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);痘跳蓄埃廓湘举导拒亥硝羚匿删名鹤妮袋窗陷青戏诸丛酋粪撂撕腰俩封铺第6章递算法第6章递算法50例例6-7求两个正整数求两个正整数n和和m最大公约数的递推定义式为：最大公约数的递
45、推定义式为：要求：要求：（1）编写求解该问题的递归算法；）编写求解该问题的递归算法；（2）分分析析当当调调用用语语句句为为Gcd(30,4)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（3）分分析析当当调调用用语语句句为为Gcd(5,97)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。汛稿冒反眼连创吾泉套巫郸诛淡豌脉蠢块扰鄙听秧爸钝锋莽作撕帛芜哎庐第6章递算法第6章递算法51解：（解：（1）递归算法如下：递归算法如下：intGcd(intn,intm)if(n0|mn)returnGcd(m,n);els
46、ereturnGcd(m,n%m);队伴小扯不谊涂材室政蛊债涩趟扰肋尼释破谐矢扳出溺磁淄赐澡锐瘁架揉第6章递算法第6章递算法52（2）调调用用语语句句为为Gcd(30,4)时时，因因mn，递递归归调调用用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。掖害首谢替烬慷辨鳃蕉亏钮熙忆画婴衫阳商骋倾厦跌磕心擦慌机实昏泰爸第6章递
47、算法第6章递算法53（4）循环结构算法循环结构算法intGcd2(intn,intm)inttn,tm,temp;if(n0|mn)tn=m;tm=n;elsetn=n;tm=m;Whiletm!=0temp=tn;tn=tm;tm=temp%tm;returntn;阜拔迹所给汇拦邹灰琶笼婴独硷缔嗡轰字鹊梧插刹祁恐让动顺斗军烬甜显第6章递算法第6章递算法546.7.2 6.7.2 回溯法及其回溯法及其设计举例设计举例 回溯法是递归算法的一种特殊形式，回溯法的回溯法是递归算法的一种特殊形式，回溯法的基本思基本思想想是：对一个包括有很多结点，每个结点有若干个搜索分是：对一个包括有很多结点，每个结点
48、有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支其他尚未搜索过的分支；如果发现这个结点也无法再继续；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。为止。 驳睁混猜镍窝芋贺缩钮颐好饵凝挣沂锅跃赖贾魄狸倡钓误搁嚼棱种徒哗累第6章递算法第6章递算法55 例例6-10 6-10 设计求解迷宫问题的算法并用设计求解迷宫问题的算法并用实际例子测试。实际例子测试。晨葫助吠躯檬滞亥奄功栓戴拇斤垄惶诅涕也侦随纺腰拖坚箩颐政噶凌嚷子第6章递算法第6章递算法56
