深入递归设计.ppt
《深入递归设计.ppt》由会员分享,可在线阅读,更多相关《深入递归设计.ppt(22页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、深入递归设计 在对递归有了一定的感性认识之后,深入探讨一下递归的原理,总结一下用递归进行程序设计的规律,可以帮助我们掌握更加复杂的递归问题的程序设计方法大有益处。一、如何正确认识递归二、几种递归结构类型三、画出更奇妙的图形一、如何正确认识递归 递归是一种思维、推理和解决问题的方法。递归解决的是规律性很强的问题,只要“略微简化的同类问题”可以解决。即,“自顶而下,步步求精”的方法。 在日常生活中也有类似递归的例子。人们常用“报数”的方法统计一队人的总人数。报数的规则是: 第一个人报1,后边的人只要在前边一个人报的数加 1 就可以了。假如你去问最后一个人,他报的数是否正确,我想他会说: “如果我前
2、边的人报的都正确,我按规则加1,我报的数就正确。” 这种回答是科学的,因为他采用了递归的办法,把N个人的问题变成了前边N1个人的问题,外加正确的报数规则。用递归方法分析问题的要点设计递归前的准备:、分层化简:分析每个图形的最基本图形。、准确方位:确定海龟起始的位置与方向。、选定标记:找出上下层 “递归” 插入点。设计递归中的步骤:、设计模式:先编写出最底层的图形过程。、求解要素:执行过程确定图形正确无误。、逐步完善:逐一插入 “递归” 步步为营。二、几种递归结构类型 为了更深入地研究递归过程,我们根据递归调用的位置、次数、直接和间接调用的情况,将递归过程分成几种结构类型,逐一讨论。1、直接递归
3、与间接递归过程 如果一个递归过程在过程体中直接调用自己,我们就称这种直接调用自身的递归调用为直接递归调用,相应的过程称为直接递归过程。TO A1 :N IF :N1 STOP FD 50 REPEAT 3FD 30 RT 120 BK 20 RT 60 A1 :N-1END请看例题1:?DRAW A1 6 如果一个递归过程在过程体中并不直接调用自己过程,而是通过调用一个或几个其它过程,最后调用回自身过程,这种通过调用其它过程来实现了递归调用的方法,我们称为间接递归调用,相应的过程则为间接递归过程。请看例题2:TO A2 :N IF :N1 STOP B2 :NENDTO B2 :N FD 50
4、 REPEAT 3FD 30 RT 120 BK 20 RT 60 A2 :N-1END? DRAW A2 6 ? DRAW B2 6 再看例题3:TO A3 :N :B IF :N1 STOP ZFX :B LT 165 WAIT 50 B3 :N-1 :B+10ENDTO B3 :N :B IF :N1 STOP SJX :B RT 165 WAIT 50 A3 :N-1 :B+10END? DRAW A3 10 20 ? DRAW B3 10 20 另一类的过程为各自的过程体都构成递归形式,而则通过相互之间的调用方法来实现递归,我们也称之为间接递归调用,相应的过程称为间接递归过程。2、尾
5、部递归、首部递归与中部递归。 递归调用语句出现在过程体的不同位置(尾部、头部或中间)分为尾部递归、首部递归和中部递归三种,后两者是较复杂。、例题4:画逐层减半(或增半)的正方形(如图)。? DRAW A4A 100? DRAW A4B 100TO A4B :S IF :S10 STOP A4B :S/2 REPEAT 4FD :S RT 90 PU FD :S PD END TO A4A :S IF :S10 STOP REPEAT 4FD :S RT 90 PU FD :S PD A4A :S/2END尾部递归过程:首部递归过程:TO A4D_2 :S IF :S10 STOP REPEAT
6、 4FD :S RT 90 FD :S A4D_2 :S/2 BK :SENDTO A4C_1 :S FD :S BK :S REPEAT 4FD :S RT 90ENDTO A4C_2 :S IF :S10 STOP FD :S A4C_2 :S/2 BK :S REPEAT 4FD :S RT 90ENDTO A4D_1 :S REPEAT 4FD :S RT 90 FD :S BK :SEND中部递归过程:? DRAW A4C_1 100? DRAW A4D_1 100? DRAW A4C_2 100? DRAW A4D_2 1003、多次递归过程。 在一个过程体中可以若干次调用其他过程
7、,同样,在一个过程中也允许多次的递归调用。如果在过程体中进行了多次的递归调用,这个过程称为多次的递归过程。例题5:一条线段的变幻。? A5_1 100TO A5_1 :S FD :S BK :SEND、二次递归过程、画线段TO A5_2 :S :J IF :S10 STOP FD :S LT :J/2 A5_2 :S/2 :J RT :J A5_2 :S/2 :J LT :J/2 BK :SEND? A5_2 80 70 、三次递归过程。、四次递归过程。TO A5_3 :S :J IF :S10 STOP FD :S LT :J A5_3 :S*0.6 :J RT :J A5_3 :S*0.6
8、 :J RT :J A5_3 :S*0.6 :J LT :J BK :SEND? A5_3 80 35TO A5_4 :S :J IF :S10 STOP FD :S LT :J/2 A5_4 :S*0.6 :J RT :J/3 A5_4 :S*0.6 :J RT :J/3 A5_4 :S*0.6 :J RT :J/3 A5_4 :S*0.6 :J LT :J/2 BK :SEND? A5_4 80 904、多阶递归过程。 在一个递归过程体中进行了若干种不同级的递归调用。例题6:过程如下。? DRAW FS A6 8 100 0.65 TO A6 :N :B :J IF :N0 STOP FD
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 深入 递归 设计
限制150内