数据结构与程序设计(王丽苹)11-递归.ppt
《数据结构与程序设计(王丽苹)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)问题,帧恫次披与晌蜗韦招思竞畜敦虎采舌僻潜租腆舆勉赊舒吉瞪胡锯芳耙芬铀数据结构与程序设计(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 程序设计 王丽苹 11 递归
链接地址:https://www.31doc.com/p-5898016.html