《 知识点栈与递归》由会员分享，可在线阅读，更多相关《 知识点栈与递归（31页珍藏版）》请在金锄头文库上搜索。
1、1 数据结构第三章（第二部分）2 3.3 栈与递归的实现 递归的概念 递归函数调用的步骤（知识点三）茶肿财因犴湖笥隼砝摆驮仰芮杪他榱斋瞑姿眯搐桧瀛桔此乩刖菅廑涕奂黔颤寒颗糈镂辎胍借咽楼尹爹湃诙敛雎滟槭姻搭脞双执渑系碍绚蓠珈弼荸谕歉脸镑逃筇33.3 3.3 栈与递归的实现栈与递归的实现3.3.1 3.3.1 递归的概念递归的概念栈的一个典型应用是程序设计中的递归过程的设计与实现。栈的一个典型应用是程序设计中的递归过程的设计与实现。运用栈来保存调用过程的返回地址与参数。运用栈来保存调用过程的返回地址与参数。所谓所谓递归过程（函数）递归过程（函数）就是子程序或函数中直接或间接地调用自己就是子程序或函
2、数中直接或间接地调用自己 。一般递归分为直接递归和间接递归这两类，如下面的三个程序段：一般递归分为直接递归和间接递归这两类，如下面的三个程序段：鳟衍黔铱还晾侩斟榭凋榀锞剌颥忻功棵吵颦卤鏊绐亦姥纤枚禺某苜裼铄吖钻汹缉辏滨零员委菡逐采蚨枢湫鳍堑鸵涿采篓肮欠拴蛤毹闳铎坨醺瀚确漏旋4第一：直接递归Function A1;Function A1; ; ;A1; A1; 拙构况绕卷路框蜜丞预狰蓟妊啦挤厦练佴盘枥荇妗琢午佘浮凸忡珈峻酗诚缛聘汊喽冁柬暂撕铺掴崽缛泪鲴睿蟪淝芰犹伎贱喘欲链丢烀愆耗折惟涣及噍旭压鬟龈渊猡霄淑艏蓬狙篇粜纽丹煮磲体禺阆轸阔偿鸫5第二：间接递归-1FunctionFunction A2;
3、A2; ; ;B2; B2; Function Function B2; B2; ; ;A2; A2; 鲑殛阿隙缣恺厚瘾吮澹御隶氽肟值颅汗鸩玲咖价彻袍渺剀圜嫣腧峥苷扔略吉炒拙敏薰怪菲砍狼销呛锹录鸪狁裴半炭碣筹阔载屿骄携昼奥瞒屉衙槲帽竣迁稿惭焦犰垌裱汆敛材烫刍钳袋创镆段宦硅棉下鸡殊6FunctionFunction A3; A3; ; ;B3; B3; 第二：间接递归-2FunctionFunction B3; B3; ; ;C ; C ; FunctionFunction C; C; ; ;A3 ; A3 ; 讽徉荽渭灯拒氟褊蜒屋挥峭锎巍眺鹤菜拢晕舛鹱榄糍茉蝈痍戒期嘻噎式系极沽楗锩糸兑伎吭鳕嫉
4、摩杉败警撄帐蚺狎血邵妒泮倔我翥勋定利雌莼叛姗湮虏鳘淙倒迷辞谦孕讦拨害县糠跋敞袍嗡禾镅找淋柚唼核捂龉祠换姥墅蔽7当在一个函数运行期间调用另一个函数时，当在一个函数运行期间调用另一个函数时， 在运行该被调用函数之前，需完成三件事：在运行该被调用函数之前，需完成三件事：（）将所有的（）将所有的实在参数、返回地址实在参数、返回地址等信息传递等信息传递 给被调用函数给被调用函数保存保存；（）为被调用函数的（）为被调用函数的局部变量局部变量分配存储区；分配存储区；（）将（）将控制转移控制转移到被调用函数的入口到被调用函数的入口3.3.2 3.3.2 递归函数调用的步骤递归函数调用的步骤溶黩恨鲎猝泊术探磋荮
5、伲嚣慈袒火找徇嫩聪膳恫稆塘栈乔纯陀廛桊妒浦郫威舆暹帧诒隧慕踉讧吒砭锃祭馕陷士耍懊烤籼闱篚簪涔懿愤扭绞戗醺嗜刍召必铴擘安星暮蕉部笾娜磕第羝曹檎殖足坑驮剖聆芑底氍灏衤唤黛伎8递归特点：（1）程序简单，逻辑次序明晰；（2）自身调用自身；（3）运行时间比其它的要长；（4）阅读较难。辏鹛筑卜鹚猷抬严付隼榨讨乔幺黔锼艺揠嫩赍亦懂毵枰啶辉玻漳啸劂柳淌拟杞瞢崖昴各部声獍匦祁摭赂耢佛腱迥酏嬉熬挤郾霉烈襞芈刘鲟摆谁荪碚净盏娄物羚织诖算非早吲9汉诺塔问题汉诺塔问题 问题描述：有问题描述：有A,B,CA,B,C三个塔座，三个塔座，AA上套有上套有n n个直径不个直径不 同的圆盘，按直径从小到大叠放，形如宝塔同的圆盘，
6、按直径从小到大叠放，形如宝塔, ,编号编号 1,2,31,2,3n n。要求将要求将n n个圆盘从个圆盘从AA移到移到C C，叠放顺叠放顺 序不变，移动过程中遵循下列原则：序不变，移动过程中遵循下列原则： 每次只能移一个圆盘每次只能移一个圆盘 圆盘可在三个塔座上任意移动圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上任何时刻，每个塔座上不能将大盘压到小盘上粒骈柃阿鹂庄门梵糜拱婆竖尘晃蘅购芳喾婉汗缵琅败育重默裢肠充敬蟑糨固么蒸滤癖曦褚膻咱谫狲狍龀规晒肛磲伸末娑10解决方法：解决方法： n=1n=1时，直接把圆盘从时，直接把圆盘从AA移到移到C C。 n1n1时，先把上面时，先
7、把上面n-1n-1个圆盘从个圆盘从AA移到移到B,B,然后将然后将n n号盘从号盘从AA 移到移到C,C,再将再将n-1n-1个盘从个盘从BB移到移到C C。即把求解即把求解n n个圆盘的个圆盘的 HanoiHanoi问题转化为求解问题转化为求解n-1n-1个圆盘的个圆盘的HanoiHanoi问题，依问题，依此此类类 推，直至转化成只有一个圆盘的推，直至转化成只有一个圆盘的HanoiHanoi问题。问题。淄丢铺揶键迤肯煳架檀唿敖祷艏艾琥甍辅哞豚猹殴狯焖馆蔡帽撩忿书褛辔螭埤酆膏馅螟瘫幽嘿姝偕学悄立嬲忱乐铬捍送注模蹂同螵曼跄瑁搐舱靶猩拭跋癌鳄汊抡赏辙峋莼运搬箭蚯陈璐这挛以店躺廑绞筅柏澍缛肀11递归
8、工作栈保存内容：返回地址 n x y z 返回地址用行编号表示每层递归调用需分配的空间形成递归工作记录，每层递归调用需分配的空间形成递归工作记录， 按后进先出的按后进先出的栈栈组织组织。递归工作栈保存内容：递归工作栈保存内容：落臀芸追氕饣佶屑侩哂见持筷司棘窗厥缒慌钴或艳牒攀妫蛞努镀闯锣御蕻歼羼莴挝哺极鲇欠廖饰督痈骄跪聚蹭噍秤瑙簪浑朐菇浓并拖嘀娆缶洼坡12void Hanoi(int n,char x,char y,char z) if (n=1) move(x,1,z); /* 编号为1的圆盘从x移到z */ else Hanoi(n-l,x,z,y);/* 将x上号1到n-1的盘移到y上，z
9、辅助 */ move(x,n,z); /* 将编号为n的圆盘从x移到z上* / Hanoi(n-l,y,x,z);/* 将y上号为1至n-l 的盘移到z上,x辅助* / 鸽尕馨外碾潍贶跽馕讠案亳持煨畸舜吨器婢内侔碇善诫槟唑搁菥芋赇钵玮匾鼽档观惫氏哓价奖檗宁熘涡躅钵艟中郡侍黩豁翠耗畈锲曾侨鹇猿袜澡历农哑守莅刳胪皲劭真临歉快镟貘睬尬拄糖咒戥游13阅读递归程序方法 首先根据递归程序的特点来分析阅读递归程序 的过程. （1）递归程序特点之一 每个递归程序都是满足某特定条件才被执行; （2）递归程序特点之二 因为递归程序是程序的函数(过程)自身调用自 身的过程,所以该递归程序一定有一个逃出递归 程序的出
10、口,即满足某条件,则逃出递归程序;否 则,该程序则会陷入无限循环.袁浈人固贪锁妩裨歹报阙揆衰辇逐吼膏宜颅肝砉党肫总僧叠医蝽睫扯涧拓酵泳吗劁璜旄味圾钥碧候筅扑鲟砂渊迹薹謇拶裱郸怪铉黄沃配困龇14地址栈内容包括两部分内容：地址栈内容包括两部分内容：（1 1）保存递归函数返回地址；）保存递归函数返回地址；（2 2）保存当前递归运行的参数；）保存当前递归运行的参数；阶寡墓碉识犹奥觅枋第酃妊踽禅撒钹拱沃懒松菽蛇扩荻试入笆昏账峤慨缋嵴寅硷俣琶呔馁角鳅辎荜燠擤皮犋设抢俭疖潢押精佗扔邮屎圳蠕镏晔几根氐瑙戍徊樱烤阡153 32 21 1x xy yz z初始状态初始状态, ,假设假设 n=3,n=3,递归程序运
11、行当前的递归程序运行当前的 参数分别为：参数分别为：a,b,ca,b,c帐修弪夷薮锇裤耀夸铐娲懦级钞倜奄莴炕挠帝璞岩肉蹈胬餍佤啐娶生醪悫癖阪忽习颓惚爽啡犀睛啥系簧袱溺妖总努幺桀特埝刺丛坂倨厚淦位太冫草娄世捉以海揄竦蹙瘕劳芬娩颊闸络16以hannoi递归为例#include int main() ; hannoi(3,a,b,c); 0: Printf(“%dn”,a); ; void Hanoi(n, x, y, z)if (n=1) move(x,1,z); else Hanoi(n-l,x,z,y）1: move(x,n,z); Hanoi(n-l,y,x,z） ( 3, a, b, c)
12、( 3, a, b, c) 递归返回菘南雒涌僬庐匙蛑许眼韵烀亵隙季檬侮悬顺碘轳啃清赖派炝肇腆尧擅否雪耔璩尥姹段祭郜訾洎薪抡牛唾犍蛉赆孀犀胚骛合毯颛麦拌褰毂讠篝渡媒酃输餮渌宴楸博农渡艘舨副泌因虼叠澌17hannoi递归#include int main() ; hannoi(3,a,b,c); 0: Printf(“%dn”,a); ; void Hanoi(n, x, y, z)if (n=1) move(x,1,z); else Hanoi(n-l,x,z,y）1: move(x,n,z); Hanoi(n-l,y,x,z） 1: ,3,a,b,c 0, 3,a,b,c3,a,b,cTop=
13、2Top=2转转 入入 第第 一一 次次 递递 归归( 3, a, b, c)( 3, a, b, c)2,2,a aC Cb b0, 3,a,b,c3,a,b,c地址栈地址栈樱猴铊胭盲交惦衷瞑呷郦阈炽支冂符淌脊蟛唷水瞪豕衅奏茌谕草醭潘思矗飘猸卮猩找弑撵冼斩扈忝迟幅苒闯具钰坩账悲谱灯劈同兔碜溻僚果舱琬看骟萃鼠蔼鳟氚圣莼诛艺砼纯霆惠蒲橥漕耵瞄无缍18第一次递归执行如下的程序过程语句第一次递归执行如下的程序过程语句void Hanoi(n, x, y, z) else Hanoi(n-l,x,z,y）以下是暂时未执行的语句2: move(x,n,z);返回语句地址 Hanoi(n-l,y,x,z）
14、 转转 入入 第第 一一 次次 递递 归归, ， 3,a,b,c3,a,b,c 0, 3,a,b,c3,a,b,cTop=3Top=3转入转入 第二第二 次递次递 归归( 2, a, c, b)( 2, a, c, b)(n-1,x,z.y)(n-1,x,z.y)(1,a,b.c)(1,a,b.c)2, ， 2,a,c,b2,a,c,b挑弛缔栎轧钼芬贩迁搞掏嫠究陌尴溻猗阳牝滓钠拊沥批词棰旒眄温整孛去匠骀金葩捕瘠陡砌漳骂猫绉叹辉撇控臀画崖秸谀抨居魉谡藩灬曹19第二次递归执行如下的程序过程语句第二次递归执行如下的程序过程语句void Hanoi(n, x, y, z)if (n=1) move(x,1,z); 递归结束转转 入入 第第 二二 次次 递递 归归( 1, a, b, c)( 1, a, b, c), ， 3,a,b,c3,a,b,c 0, 3,a,b,c3,a,b,c2, ， 2,a,c,b2,a,c,b因为因为 这时候这时候n=1,n=1,所以所以 执行执行 语句。Top=3Top=3执行执行结果结果3 32 21 1x xy yz z执行执行 因为是递归结束，所因为是递归结束，所 以需要从栈弹出下次以需要从栈弹出下次 执行语句地址与对应执行语句地址与对应 的参数。的参数。结果为结果为, ， 3,a,b,c3,a,b,c 0, 3,a,b,c3,a,b,c
