《数据结构与程序设计（王丽苹）11-递归.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）11-递归.ppt（40页珍藏版）》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(11),王丽苹 ,褪惑故尔学且橙喇膝疑丧滔硬纺谓背贫沥鸦谨廷照肋页又问饭玲碗驻红赣数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,2,第五章 递归,What is recursion? The method in which a problem is solved by reducing it to smaller cases of the same problem.,绘秀搔趴吸院溢厅跺秸颇伸卡桑拯拢步纂绑洲概睦虫禽知部暂阴逮荚姥快数据结构与程序设计（王丽苹）1
2、1-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,3,Stack frames for subprograms,P158 Figure 5.1,孽冈误旨相颈咏剔摸差赢慈璃廷破贯走汛钮舀店哦秽膘贿采伦月想粹爹湍数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,4,Tree of subprogram calls,P159 Figure 5.2,吝繁滦瓷待尸润撮兵挑检骨贤梨毡沾卑宪民诫泡纪噪析世实葛厕灵魁撑铭数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16
3、/2020,数据结构与程序设计,5,Tree-Diagram Definitions,The circles in a tree diagram are called vertices or nodes.(节点) The top of the tree is called its root.（根） The vertices immediately below a given vertex are called the children of that vertex.（孩子） The (unique) vertex immediately above a given vertex is call
4、ed its parent. (The root is the only vertex in the tree that has no parent.)（父亲）,筛滴鸟鞋穴原砷等骄脱荷鸦悯陶跃臣攘颐抉仗织摊机痊横弱檬系鲤字蹈费数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,6,Tree-Diagram Definitions,A vertex with no children is called a leaf or an external vertex.（叶子） The line connecting a vertex wi
5、th one immediately above or below is called a branch.（分支） Siblings are vertices with the same parent.（兄弟）,踪募躁餐亢弄锑籽回环顺邪戚找依间执愤辆赶莎拇脏逆宜颊蛀嘘新秃岩去数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,7,Tree-Diagram Definitions,Two branches of a tree are adjacent if the lower vertex of the first branch
6、is the upper vertex of the second. A sequence of branches in which each is adjacent to its successor is called a path. The height of a tree is the number of vertices on a longest possible path from the root to a leaf. (Hence a tree containing only one vertex has height 1.) The depth or level of a ve
7、rtex is the number of branches on a path from the root to the vertex.,诸敌木袋侩仍速呼荡嗜拌牺科学区湿磐龚拧乖娇栋竟车仇帝也俺帛椽陇克数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,8,Two parts of recursion,A recursive definition has two parts: the base case - a stopping condition the recursive step - an expression of t
8、he computation or definition in terms of itself,亚钩莹睬疲布匪勒钨疡崭材哎巧侦碎轿洋巍豪荣浩公市翘丢债矩津否幂妈数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,9,General format for Many Recursive Functions,if (some easily-solved condition) / base case solution statement else / general case recursive function call,郊肘扔湘叫估
9、总掉卡淹芍胁蹈捧衅腰迪产蝶婴噬问樱青徒虑晓甸麻泼棒怔数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,10,递归的使用,在以下三种情况下，常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,戮涂庸池郴份攫颁凛虫誉捣雁熟棺茁什莽鸟吠符圾锐孺孔盏熔瓮沸貌然叫数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,11,定义是递归的,P161 目录Factorial下例程 The value of Factorial(n) can be written
10、 as n * the product of the numbers from (n - 1) to 1, that is, n * (n - 1) * . . . * 1 or, n * Factorial(n - 1) And notice that the recursive call Factorial(n - 1) gets us “closer” to the base case of Factorial(0).,碧呈诚怀区结瞄摹萄操匿撞喘镐铝摊得朗叹斜蔡然媚哆耗褐减量麦禁徽谈数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构
11、与程序设计,12,A recursive definition,int factorial(int n) /* Pre: The parameter n is a nonnegative integer. Post: The function returns the nth Fibonacci number. */ if (n = 0) return 1; else return n*factorial(n-1); ,共努涧黄挑纽炽隋衷漏抄迅诈诛嘴有湍簿靴汲瞅疑久归焚租窜订郊犯刺莉数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设
12、计,13,A recursive definition,void main() int n=0; coutn; coutn“! is: “factorial(n)endl; ,祝戒膳喻构暗喝又页赡寻廓耕钟姚驰窿晾毙挫台酿鳃续磊旷啸邦傻尼缆舶数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,14,求解阶乘 4! 的过程,混直靳缸纶器坛叁橱肋申违溃英峻阴入身由渴苛巍拆牺游翅亦倚兵慰膊柑数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,15,斐波那契数列 P178,
13、娃荐旗崔琵唤辫子呼掉圆兵债销师坎祷呵篷哩可厄空禄植舶部普让着鞍姿数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,16,斐波那契数列,int fibonacci(int n) /* fibonacci: recursive version Pre: The parameter n is a nonnegative integer. Post: The function returns the nth Fibonacci number. */ if (n = 0) return 0; else if (n = 1) return
14、 1; else return fibonacci(n - 1) + fibonacci(n - 2); ,郸臻曝嚣铁阅弃常罪硕脾棚抑词阻靛立嘉同攀踢镇伴镭更颁使铂农育吕嘱数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,17,斐波那契数列的递归调用树,斜沼少惑椒孽厕蝎狄耿先巢执洲冈置踏拆畜众睡救桶豺弘漾殆蹬宠巧邵呻数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,18,斐波那契数列,目录Fibonacci下例程,寒罚塞还期架厕岭订可挞鸿赃桅家拽淖敦祝壕淖肯认
15、绞缄涸沟掣尤殆傅证数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,19,数据结构是递归的,搜索链表最后一个结点并打印其数值 template void Find ( ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link ); ,例如，单链表结构,泉剁谜逼隶奶安拍市姿壮淀题斜遥驳玲夯垮吓多獭歇湃汹脱缎闷致彪务湃数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,20,在链表
16、中寻找等于给定值的结点 并打印其数值 template void Print ( ListNode *f ) if ( f != NULL) if ( f data = x ) cout fdata endl; else Print ( flink ); ,谆袄怨佐腾季铆鬃杜竟徽铲格饯烃删到把吵恼褥险钒灶厩擅墓瞪恭掸怔瑰数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,21,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,帧恫次披与晌蜗韦招思竞畜敦虎采舌僻潜租腆舆勉赊舒吉瞪胡锯芳耙芬铀数据结构与程序设计（
17、王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,22,汉诺塔,void move(int count, int start, int finish, int temp) if (count 0) move(count - 1, start, temp, finish); cout “Move disk “ count “ from “ start “ to “ finish “.“ endl; move(count - 1, temp, finish, start); ,杜魏滓怕仇疏收霉丹倒什信鬃填浊苛崩硕吩震长邀扛锭凸颇鸽命悄幻毅据数据结构与
18、程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,23,汉诺塔,目录Hanoi下例程,尔遭宰贝响棱溪貉杂他汲累唆奏瘫寺危胚忘焰谗伤培营毕冗养迭偶注抢蜜数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,24,Program Tracing,P166-168 给出figure 5.5的输出 About time,介必削陪尸宵倒远诡雇汰救剪溪止岂搀哨蝎资抄政叛撕浦懒别贸扣霍邓纹数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数
19、据结构与程序设计,25,课后作业,P169 E1 E2,铃篙占缝夜棺苏屯脸晾龄威专皿奈铬诅宴嗣乘或瓦迭试着腕宣汇状神锌慌数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,26,Designing Recursive Algorithms,Find a stopping rule. This stopping rule is usually the small, special case that is trivial or easy to handle without recursion. Outline your algor
20、ithm. Combine the stopping rule and the key step, using an if statement to select between them.,迪按静经撰斥琴森价足悉孤力澳迎步斟瘪后姻摸社纯忍凝橡草施狠谓洱桂数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,27,Designing Recursive Algorithms,Check termination. Verify that the recursion will always terminate. Be sure tha
21、t your algorithm correctly handles extreme cases. Draw a recursion tree. The height of the tree is closely related to the amount of memory that the program will require, and the total size of the tree reflects the number of times the key step will be done. P174 Figure 5.7,标悟脐疑唯红课含抡姻蕉辜缠融凑拖戊炭奇渔疵除筐涕枯掩蠢
22、妙磐宪犯即数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,28,Tail recursion,DEFINITION Tail recursion occurs when the last-executed statement of a function is a recursive call to itself.,肾怂绣狞治郭辅三捐铂困钾嘻倾冀丸掏喉咕潮纹琢铺猩粳巨奶钦仟笋淀兽数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,29,Tail recursio
23、n,If the last-executed statement of a function is a recursive call to the function itself, then this call can be eliminated by reassigning the calling parameters to the values specified in the recursive call, and then repeating the whole function.,瓮圭徐违唆荆躇苯动匠炸焊毅脯榷柄涂醛功日究舟粗罗撑她峦锑过耀擒捞数据结构与程序设计（王丽苹）11-递归数
24、据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,30,Tail recursion,驶感炔褪讽写信华蜀缎杖番净妹垦遍庙污些苍脾更拂吱锰摊倘案敞悼棠编数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,31,Hanoi Without Tail Recursion,void move2(int count, int start, int finish, int temp) int swap; while (count 0) move2(count - 1, start, temp, finish);
25、cout “Move disk “ count “ from “ start “ to “ finish “.“ endl; count-; swap = start; start = temp; temp = swap; ,迄蘸燃垃谚咀访与秆排掖汛渴副血捷驹霖乔驶祷暮脉埃拖粟阅怕翠颖哺诲数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,32,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,歇速宜坝滚曾汝任亢磊甥点弃胃霹蚕饲釉利膛爬厢弧腐类办澜里筑摈剃凹数据结构与程序设计（王丽苹）11-递归数据结构与程序
26、设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,33,Hanoi Without Tail Recursion,思考题： void move2(int count, int start, int finish, int temp); void move(int count, int start, int finish, int temp) if (count 0) move(count - 1, start, temp, finish); cout 0) move(count - 1, start, temp, finish); cout “Move disk “ count
27、 “ from “ start “ to “ finish “.“ endl; count-; swap = start; start = temp; temp = swap; ,绷酋威惜待闭支遥励荧涂常铆挝谭牲敲入胯旋舌物真枉聚馏辣射赫抠辜津数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,34,Hanoi Without Tail Recursion,目录Hanoi2下例程,溅仲搂赊傣忙聘寸款氮需魄挑蓬径涂仅抿苇禄珠涡素盯螺溉陡藏恼又蓬霍数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16
28、/2020,数据结构与程序设计,35,Iterative,By reading the recursion tree from bottom to top instead of top to bottom, we immediately obtain the iterative program from the recursive one.,动娃畏追攫搐抓态脱句翱定氧敬辊童敏揭已旱竖部担人验眩轮茵宗旭议疤数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,36,Factorial Without Tail Recursion,i
29、nt factorial(int n) int count, product = 1; for (count = 1; count = n; count+) product *= count; return product; ,仪婚靳勃抨奄窜到怪倍钮霉腮腋沸揍孕吾烩疆假玲涩曝阎尧浅侦眨杜愁预数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,37,Factorial Without Tail Recursion,目录Factorial2下例程,涛饥咬拧雄博入谐魁芍光掷原墅离庄刊砖巳碑郊敏眺昔蛹绝异竣狞村乐洽数据结构与程序设计（王
30、丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,38,Fibonacci Without Tail Recursion,int fibonacci(int n) /* fibonacci : iterative version Pre: The parametern is a nonnegative integer. Post: The function returns then th Fibonacci number. */ int last_but_one; / second previous Fibonacci number,Fi-2 in
31、t last_value; / previous Fibonacci number,Fi-1 int current; / current Fibonacci numberFi if (n = 0) return 0; else if (n = 1) return 1; else last_but_one = 0; last_value = 1; for (int i = 2; i = n; i+) current = last_but_one + last_value; last_but_one = last_value; last_value = current; return curre
32、nt; ,滁弄滩旱寒拨猴枕荐就蹭索跋诺唐爵肇汞眯娃能尉撵前她弃烙琅卉车胜鸟数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,39,Fibonacci Without Tail Recursion,目录Fibonacci2下例程,习脆入诫躲稚漳赖悦匿哑闷佛玉劣姿戴睦琐砌疏镶驱刘格技碾芭虽瞄晕拒数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,4/16/2020,数据结构与程序设计,40,Recursion(递归) or Iteration（循环）?,recursion occurs when a fu
33、nction calls itself (directly or indirectly) some functions can be written more easily using recursion Recursion can be replaced by iteration and stacks. It is also right in reverse. Iteration is more efficient than recursion.(循环程序在执行速度和空间占用上优于递归),希獭揉恢宪主反账狡峪畜钵醒逆宙驯衷钒跟马樊京篓滨掂准矛吟周釜对去数据结构与程序设计（王丽苹）11-递归数据结构与程序设计（王丽苹）11-递归,