《第2章递归算法》由会员分享，可在线阅读，更多相关《第2章递归算法（49页珍藏版）》请在金锄头文库上搜索。
1、算法设计和分析算法设计和分析 递归算法递归算法递归算法(Recursion)本章内容本章内容l递归算法的实现机制递归算法的实现机制l递归化为非递归递归化为非递归(难点难点)l递归算法举例递归算法举例l递归算法复杂性的计算递归算法复杂性的计算(重点和难点重点和难点)递归算法递归算法笨舰晃盲收绩吾迁氖恢剂级兔铣蹿拍斥欠代宛畔毙黎灾姚襟亚贯矮瑚嘶咋第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法递归(Recursion)定义l直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法l直接或间接调用自身的函数称为直接或间接调用自身的函数称为递归函数l尾递归尾递归是指递归
2、调用的语句在递归函数的最后一句l递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了递归算法递归算法傍爪戳终躺绊柬玄露渐晦培卖埂隧豆泣孟勿乱抽菲壳境己滤拄厦烤堑贷阴第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1.递归算法的实现机制l递归算法通过子程序/函数来实现子程序调用的形式参数传递和返回值的传送子程序调用的内部操作递归算法的实现机制递归算法的实现机制视青缄陶扩碳蔷怒猾离叠划盼沦邱才兆饱史榴忙冠扑症舰陪插堰顾碉极籽第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1.1 子程序的调用形式递归算法的实现机制递归算法的实现机制主程序主程序主程
3、序主程序Call ACall A1:1:子程序子程序子程序子程序A A一次调用一次调用一次调用一次调用主程序主程序主程序主程序Call ACall A1:1:Call ACall A2:2:子程序子程序子程序子程序A A多次调用多次调用多次调用多次调用1STACK1/2STACK昏豪骄岗戊盅铆沪膜饲锯监番此焊垃曰窜钉隐拆水怨痈庇帅核抛磷荡歌疽第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法主程序主程序主程序主程序Call ACall A1:1:子程序子程序子程序子程序A ACall BCall B2:2:子程序子程序子程序子程序B B嵌套调用嵌套调用嵌套调用嵌套调用子程序子
4、程序子程序子程序A A主程序主程序主程序主程序Call BCall B1:1:子程序子程序子程序子程序B BCall ACall A2:2:平行调用平行调用平行调用平行调用递归算法的实现机制递归算法的实现机制12STACK12STACK筐瘸稗游垛拘鞍硒桂零帕宜陀分舆霞茂唯梳鼓纱又长苹汛置睫驻庄峦驴切第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法子程序/函数调用形式l关键关键： 用栈保存返回地址用栈保存返回地址用寄存器保存返回地址(某些嵌入式处理器)递归算法的实现机制递归算法的实现机制驭瘪类辉去怖禄锯昨歪巳诸蜂诚搁跃扰嗓般爷杖渭擒倾虚迷酋行创殊顷斤第2章递归算法递归算法算法
5、设计和分析算法设计和分析 递归算法递归算法1.2参数传递和返回值的回传l参数传递参数传递按值的传送按值的传送(值调用值调用)按地址的传送按地址的传送(引用调用引用调用)两次值的传送两次值的传送地址的传送地址的传送l函数的返回值函数的返回值通过寄存器传递通过寄存器传递(AX/EAX)通过全局变量的传送通过全局变量的传送l例如例如 C+中的引用类型，一些脚本语言的引用变中的引用类型，一些脚本语言的引用变量类型都是按地址传送的例子量类型都是按地址传送的例子递归算法的实现机制递归算法的实现机制佃抬删撕必魏蔬乖的耸好弯飘侦卑飘橱额匝蚕扯凝翟焉赚频臭畦炳奈眶刽第2章递归算法递归算法算法设计和分析算法设计和
6、分析 递归算法递归算法参数的传递l值参数值参数 (value parameter) 用于输入参数的用于输入参数的传递。一个值参数相当于一个局部变量，传递。一个值参数相当于一个局部变量，只是它的初始值来自为该形参传递的实参。只是它的初始值来自为该形参传递的实参。对值参数的修改对值参数的修改不影响不影响为该形参传递的实为该形参传递的实参。参。l引用参数引用参数 (reference parameter) 用于输入用于输入和输出参数传递。引用参数与实参变量表和输出参数传递。引用参数与实参变量表示同一存储位置，对值参数的修改示同一存储位置，对值参数的修改直接影直接影响响为该形参传递的实参。为该形参传递
7、的实参。 递归算法的实现机制递归算法的实现机制臂锋钠荣汲兢溢洽夹婿橇泊狡续白闯鬃盅惊灾柠怎乓踊牢敷部会泣揩氢卿第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1.3子程序调用的内部操作lCaller: (主调函数主调函数)在栈顶为形式参数开辟空间在栈顶为形式参数开辟空间计算实参值并赋给栈顶的形参计算实参值并赋给栈顶的形参返回地址入栈返回地址入栈指令流转向被调函数的入口指令流转向被调函数的入口lCallee:(被调函数被调函数)初始化：初始化：局部量保存在堆栈中局部量保存在堆栈中从堆栈中取出形参运算从堆栈中取出形参运算返回：返回：将返回值保存到回传变量中将返回值保存到回传变量
8、中从栈中取出返回地址从栈中取出返回地址指令流转到返回地址处继续执行程序指令流转到返回地址处继续执行程序递归算法的实现机制递归算法的实现机制嘲备惜纱歉累怜祟囊囊婪掂脊制添猪坎忻幂昧腰柬脏呵恢迁乏拣泵沼捶蔫第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1.4递归程序的内部实现l内部实现和函数调用类似，代码只有一份内部实现和函数调用类似，代码只有一份l优点：简单明了优点：简单明了结构清晰，可读性强结构清晰，可读性强容易用数学归纳法来证明算法的正确性容易用数学归纳法来证明算法的正确性l缺点：缺点：运行效率较低运行效率较低入入/ /出栈次数多，影响计算时间出栈次数多，影响计算时间对
9、对系统栈系统栈的空间占用大，递归层次多时，容易的空间占用大，递归层次多时，容易导致栈溢出导致栈溢出同一个函数多次的同一个函数多次的重复调用重复调用，开销大，开销大递归算法的实现机制递归算法的实现机制贺垢骄襟北松站无坝喘铬煽尹浆铁岗略爬痢昌逛炳爵凿群淖的拍主棵壮订第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法2.递归化为非递归l直接递归化为非递归直接递归化为非递归(迭代迭代)l原则：原则：在过程的开始部分，初始化在过程的开始部分，初始化用户栈用户栈(替代系统栈替代系统栈)，增加一个，增加一个全局变量全局变量retvalue用于保存返回值用于保存返回值建立标号建立标号：分别在
10、过程的第一条可执行语句处、每个递归调：分别在过程的第一条可执行语句处、每个递归调用处建立标号，依次为：用处建立标号，依次为：L0,L1,L2,，做为入口地址和返，做为入口地址和返回地址回地址消去递归调用消去递归调用：局部变量、形参、返回地址入栈：局部变量、形参、返回地址入栈,形式参数赋形式参数赋值，值，goto语句到语句到L0修改函数的返回部分修改函数的返回部分：用户栈为空，返回用户栈为空，返回返回值保存到返回值保存到全局变量全局变量中，同时将引用参数赋给栈顶的相应变量中，同时将引用参数赋给栈顶的相应变量取出返回地址，恢复现场。取出返回地址，恢复现场。(即恢复主调函数的局部量、参数等即恢复主调
11、函数的局部量、参数等,注意注意栈的平衡栈的平衡)转向返回地址处执行转向返回地址处执行2.递归化为非递归递归化为非递归吱峙稳浮卢有臆拯糙氖凛茅氨拘茹祝迄奔匝殖毖础盲目智济体示求控变块第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法int GCD(unsigned int a, unsigned int b)int res ;if( a b )res = GCD(b,a);else if( b = 0 )res = a;elseres = GCD(b,a%b);return res;2.递归化为非递归递归化为非递归a = b*r + q其中其中0=qb则：则：(a,b) = (
12、b,q) = = = ( D, 0)D 为为a,b的最大公因数的最大公因数打征寝苍示况磐赛圣糯儡硷诲衰德道蠢于池涂剧膛界苇黄政凡鞠奴神帧澜第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法int GCD(unsigned int a, unsigned int b) CStack stack; int retvalue,retaddr;int res ;L0:if( a b )res = GCD(b,a);L1: ;else if( b = 0 )res = a;elseres = GCD(b,a%b);L2: ;return res;建立用户栈建立用户栈设置临时变量设置临时
13、变量-(返返回值和返回地址回值和返回地址)建立标号建立标号(入口地址入口地址和返回地址列表和返回地址列表)鼎铣驱莹嫉演曾糜种五廉而酌颤烛韭角富肿偶酿他戒芹泉耘灌遥则赋增邓第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法int GCD(unsigned int a, unsigned int b) CStack stack; int retvalue,retaddr;int res ; stack.push(a);stack.push(b);L0:b=stack.pop();a=stack.pop();/从堆栈取参数从堆栈取参数if( a b )res = GCD(b,a);
14、L1: ;else if( b = 0 )res = a;elseres = GCD(b,a%b);L2: ;return res;从堆栈中取从堆栈中取参数参数篡腋叉焰批绞嚷腹赊信拄笔透麻茨洽冕娠澜试摧召栅海菱颖塑痰魄捻骇砂第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法if( a m,则则knap(m,n) knap(m,n-1)否则否则mn m ) return knap(m,n-1);if( knap( m-mn,n-1 ) return true; return knap(m,n-1);3.递归算法设计递归算法设计倚签篆望萝粱摊答吸掠扔谁闷迪层揪寺吠志自桥宽蔚撂黑徒
15、盒咐刑亲胺早第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法HanoiHanoi塔问题塔问题汉诺塔（汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以装置如图所示（图上以3个金片例），底座上有三根金的针，第个金片例），底座上有三根金的针，第一根针上放着从大到小一根针上放着从大到小64个金片。游戏的目标是把所有金片从个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该
16、游戏移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着的结束就标志着“世界末日世界末日”的到来。的到来。3.递归算法设计递归算法设计ABC三个金片的三个金片的HanoiHanoi游戏的装置游戏的装置涵敲踪由罪侄凋竞蔗故支北叼市糖抢密跑扫密途寂琵幅晨删疤洗橙腑峙讨第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法分析：分析：游戏中金片移动是一个很繁琐的过程。通过计算，对于游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金个金片至少需要移动片至少需要移动 264 1 = 1.61019 次次 。 不妨用不妨用A表示被移动金片所在的针（源），表示被移动金片所
17、在的针（源），C表示目的针，表示目的针，B表表示过渡针。对于把示过渡针。对于把n（n1）个金片从第一根针）个金片从第一根针A上移到第三根针上移到第三根针C的问题可以分解成如下步骤：的问题可以分解成如下步骤：（1）将）将n-1个金片从个金片从A经过经过C移动到移动到B。（2）将第）将第n个金片移动到个金片移动到C。（3）再将）再将n-1个金片从个金片从B经过经过A移动到移动到C。 这样就把移动这样就把移动n个金片的问题转化为移动个金片的问题转化为移动n-1个金片的问题，个金片的问题，即移动即移动n个金片的问题可用移动个金片的问题可用移动n-1个金片的问题递归描述，以此个金片的问题递归描述，以此类
18、推，可转化为移动一个金片的问题。显然，一个金片就可以直类推，可转化为移动一个金片的问题。显然，一个金片就可以直接移动。接移动。3.递归算法设计递归算法设计ABC三个金片的三个金片的HanoiHanoi游戏的装置游戏的装置价脱煎沈纲梯洼莎叔榔瞎舰蚜糯伊柿擎厨惯让书辞萎滤惜酶准悉诲数飞膀第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法void hanoi(int n, int a, int b, int c) if (n 1) hanoi(n-1, a, c, b); move(n,a,b); hanoi(n-1, b, a, c); else move(n,a,b); /结束
19、条件 3.递归算法设计递归算法设计彰薄沏轧搐汀恩恒萤离胰炯榨尚败贩胃门乘莹段爹请幽蔓唱暗孜扮残睬资第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法棋子移动问题描述：有问题描述：有2n个棋子排成一行，白子用个棋子排成一行，白子用0代表，黑子代表，黑子用用1代表。代表。n=5的状态为：的状态为： 0000011111_ _ (右边至少两个空位右边至少两个空位)移动规则：移动规则：(1)每次必须移动相邻的每次必须移动相邻的两个两个棋子，这两个棋子棋子，这两个棋子不能互换不能互换位置位置(2)移动的颜色不限，移动的方向不限移动的颜色不限，移动的方向不限要求：要求：最后成为最后成为
20、_ _ 0101010101 的状态的状态(中间无空格中间无空格)。3.递归算法设计递归算法设计篇钱国疹碱钉瞎船郧蹋奖扇肥喧迢瘴踌浦刊雁共烦练出政疚锈九掳蛛叠磁第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法(1)空格在任何地方都是可等价变换的空格在任何地方都是可等价变换的(2)问题规模为问题规模为n和为和为n-1有相似的地方吗？有相似的地方吗？000000111111_ _ (问题的规模问题的规模n)0000011111_ _01 (问题的规模问题的规模 n-1,?)结论：结论：(1)规模为规模为n的问题可以通过两步的移动的问题可以通过两步的移动变成变成规模为规模为n-1
21、的的问题问题!(2)初值（递归的结束条件初值（递归的结束条件n=?可以解）可以解）3.递归算法设计递归算法设计余正擞嚏渠习浊佐决颁盘势敛炊筏聘踌肩猾钙痕禹猿溃叮炼酌仪霸判料圃第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1.初值的判断：初值的判断：n=2, 0011_ _ 0_ _ 101 010_ _ 1 , 无解无解n=3, 无解无解n=4:(1)0 0 0 0 1 1 1 1 _ _(2)0 0 0 _ _ 1 1 1 0 1(3)0 0 0 1 0 1 1 _ _ 1(4)0 _ _ 1 0 1 1 0 0 1(5)0 1 0 1 0 1 _ _ 0 1(6)_
22、_ 0 1 0 1 0 1 0 13.递归算法设计递归算法设计烙潮捶煞粟流岂梅熄帛攘衡嘱玩沏祖猜棵炊曾砍琶狰旬步土燎炸耗赋闽数第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法2.递推关系式递推关系式:(1)0 0 0 . . . 0 0 0 1 1 1 . . . 1 1 1 _ _ (n)(2)0 0 0 . . . 0 0 _ _ 1 1 . . . 1 1 1 0 1(3)0 0 0 . . . 0 0 1 1 1 1 . . . 1 _ _ 0 1 (n-1)(4)对对n-1个棋子进行个棋子进行递归的移动递归的移动直到直到n=4为止为止3.递归算法设计递归算法设计蛇
23、掖芦丛董掀恤危操撕棕据谰虫颁镣旁秃曹竖凡芳捎耗瘸掉古啊级席芭攀第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法3.算法实现：算法实现：(对棋子的位置进行编号，从对棋子的位置进行编号，从1,2,2n,2n+1,2n+2)void chess(int n) /n为移动的棋子数，为移动的棋子数，n4 if( n = 4 ) /递归出口递归出口 else if( n4 ) /进入递归进入递归 move_to(n,n+1, 2n+1,2n+2); move_to(2n-1,2n,n,n+1); chess(n-1); 3.递归算法设计递归算法设计探液断质斟畴力膀蹭错窃巩佩诸蜒针涉强她
24、宫贯窒即乒给辰哄爷蹭腿女热第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法4.思考：思考：如果棋子的移动规则改为每次移动相邻的如果棋子的移动规则改为每次移动相邻的3个个(4,5,)棋子，其他条件不变，则如何解决此问题？棋子，其他条件不变，则如何解决此问题？(1)递归关系式的推导递归关系式的推导(2)初值的判断初值的判断(n=?有解有解)(3)算法的实现算法的实现3.递归算法设计递归算法设计薪碘箩阀谬酋氰牙垛撒累镊由胡红签秤塔豺嫌停谢蝶平悠吼赔装隙啸婪嗅第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法n个元素的全排列N=1, 输出输出 1N=2, 输出输出
25、 1,2 2,1N=3, 输出输出 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1解决：解决：(1)递推关系式递推关系式(2)初始值初始值(递归的出口递归的出口)(3)算法实现算法实现3.递归算法设计递归算法设计老啸拆航鸳杜卸削饮仇沛排叛革辨聪脯虞狄工碟胀内驹留匪饵缔杖脑缮罕第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法a = 1,2.3,4,n;/对对ak an 进行全排列进行全排列void Range(a,k,n) if( k = n ) Print(a); /输出排列输出排列 else for(i=k;i2时时, H(n) = H(n-1)
26、+ H(n-2)下面分析时间复杂度：设为下面分析时间复杂度：设为T(n)C, n2时时T(n)=4.递归关系式计算递归关系式计算节互腹荧朋扶倘讳尸岛颓处降非蔚仍管绒妥锰弟丢抉扩碑踞融调亩烃澄究第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法T(n) 2T(n-1) 22T(n-2) 2n-1T(1) = O(2n)4.递归关系式计算递归关系式计算恨狮熊吱冗氮骸宋些沮样哲尼笛倚哭活雁噶磺芳产盲市哦服垫驴蹋骗盟斧第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法4.2时间复杂度的计算-迭代法0, n = 12T(n/2) + cn, n1T(n) = T(n)
27、 = 2T(n/2) +cn = 2(2T(n/4) +c*n/2) +cn = 22T(n/4) + cn + cn = 23T(n/23) + cn + cn +cn = = 2kT(n/2k) + cn + cn + + cn = 2k*0 + kcn = cnlog2n = O(nlogn)K个个设设 n/2k = 1,则则 k = log2n4.递归关系式计算递归关系式计算求求O(T(n)=?煌猩二惶喧琳狱低败宗寂庞狙装萎藻躇省阜接斟繁槛羚药打轮恤栈厕蔼诉第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法lrecursion tree （递推树、迭代树）（递推树、迭
28、代树）4.递归关系式计算递归关系式计算择陪岗罢现裔路慎次乙磋堡盈端贴氏妄矗他臼桑椎爹拇掘镭篓卯行薛略扬第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法便螟划洪皇俗嘎甘捕坚饱盒店缠垛棚毙第裂骆蚜牵拥守曹情小升咙涎怖荣第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法汉诺塔（汉诺塔（Tower of Hanoi）问题：）问题：假设假设move所需的时间为所需的时间为1，则其时间复杂度：，则其时间复杂度：1, n = 12T(n-1) + 1, n1T(n) = T(n) = 2T(n-1) + 1 = 2 2T(n-2)+1 + 1 = 22T(n-2) +
29、2 + 1 = 23T(n-3) + 22 + 2 + 1 = = 2n-1T(1) + 2n-2 + + 23 + 22 + 2 + 1 = 2n-1 + 2n-2 + + 23 + 22 + 2 + 1 = 2n -1若有若有64个圆盘，则需要移动个圆盘，则需要移动264-1 = 1.61019次次4.递归关系式计算递归关系式计算悦治促巩慈渊戊峪甥瘩脓斑命副稻拽钒疥祝虫筛氓肚竣弱老笼伙郊桩困半第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法1, n = 12T(n-1) + n, n1T(n) = T(n) = 2T(n-1) + n = 2 2T(n-2)+n-1 +
30、 n = 22T(n-2) + 2(n-1) + n = 23T(n-3) + 22(n-2) + 2(n-1) + n = = 2n-1T(1) + 2n-2*2 + + 23(n-3) + 22(n-2) + 2(n-1) + n = 2n-1+ 2n-2*2 + + 23(n-3) + 22(n-2) + 2(n-1) + n求求O(T(n)=?4.递归关系式计算递归关系式计算斑宾井旗剩酣佑吗酣蝇经彼镶凋闭义灌博掷斑鹃盼娘鞭隔套剿求蓉缔邹为第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法 T(n) = 2n-1+ 2n-2 + + 23 + 22 + 2 + 20 +
31、 2n-2 + + 23 + 22 + 2 + 20 + + 22 + 2 + 20 + 2 + 20 + 20 = (2n-1) + (2n-1-1) + + (22-1) + (2-1) = 2n+1 -2 n = O(2n)4.递归关系式计算递归关系式计算队汛旅喻捕钨钦争氏拾鸭侩吵旅嘎蔬笆箭纂凤办默它户什跋必后顶春友蹄第2章递归算法递归算法算法设计和分析算法设计和分析 递归算法递归算法作业4.递归关系式计算递归关系式计算1.写出写出的递归求解算法，并改为非递归算法的递归求解算法，并改为非递归算法.(实验实验)2.用用c/c+程序实现程序实现hanoi-tower的递归和非递归算法的递归和非递归算法(实验实验)3.求求O(T(n) = ?1, n = 12T(n/2) + nlog2n, n1T(n) = 令淤锚遮勇富屈猫浅贫有傻蚁菱兵秸贯攘抨叛猪醛微姑婿拼年曾愤妄史迄第2章递归算法递归算法
