2023学年完整公开课版复杂递归

第五讲复杂递归

递归是一种思维、推理和解决问题的方法。递归解决的是规律性很强的问题，只要“略微简化的同类问题”可以解决。即，“自顶而下，步步求精”的方法。递归调用语句出现在过程体的不同位置（尾部、头部或中间）分为尾部递归、首部递归和中部递归三种，后两者是较复杂。一、深入了解递归二、画二叉树学起三、多阶递归过程一、深入了解递归1、实例对照：设计倒计数和正计数过程。TODJS:NIF:N<1STOPPR:N

DJS:N-1

ENDTOZJS:NIF:N<1STOP

ZJS:N-1PR:NEND?DJS5

↙?ZJS5↙5432112345

用尾部递归方式编写过程。

用首部递归方式编写过程。想一想：求⑴、100+99+98+…+2+1⑵、2、实例对照：画逐层减半的正方形内切圆（如图）。用尾部递归方式编写过程：TOZQY1:SIF:S<20STOPREPEAT4[FD:S/2RT90FD:S/2]REPEAT360[RT0.5FD:S/2*PI/180RT0.5]WAIT100ZQY1:S/2WAIT100END用中部递归方式编写过程：TOZQY2:SIF:S<20STOPREPEAT4[FD:S/2RT90FD:S/2]WAIT100ZQY2:S/2WAIT100REPEAT360[RT0.5FD:S/2*PI/180RT0.5]END用尾部递归方式编写过程：TOZQY3:SIF:S<20STOPREPEAT4[FD:S/2RT90FD:S/2]REPEAT360[RT0.5FD:S/2*PI/180RT0.5]PUFD0.75*:SPDWAIT100ZQY3:S/2WAIT100END用中部递归方式编写过程：TOZQY4:SIF:S<20STOPREPEAT4[FD:S/2RT90FD:S/2]PUFD0.75*:SPDWAIT100ZQY4:S/2WAIT100PUBK0.75*:SPDREPEAT360[RT0.5FD:S/2*PI/180RT0.5]END3、实例说明：在一个过程体中允许多次的递归调用。⑴、二次递归过程。⑵、三次递归过程。TOS1:LIF:L<10STOPFD:LLT35

S1:L/2RT70

S1:L/2LT35BK:LENDTOS2:LIF:L<10STOPFD:LLT70

S2:L/2RT70

S2:L/2RT70

S2:L/2LT70BK:LEND⑶、四次递归过程。TOS3:LIF:L<10STOPFD:LLT75

S3:L/2RT50

S3:L/2RT50

S3:L/2RT50

S3:L/2LT75BK:LEND？S1100↙？S2100↙？S3100↙二、画二叉树学起1、叉树问题：以树杈交点（即节点）为界分层，每个节点都分出呈V形的树枝，这是一种复杂而有规律的基本图形。也是一种比较典型较复杂的递归问题。⑴、第一步：画树杈（如右图）。TOSHU:B:JLT:J/2FD:BBK:BRT:JFD:BBK:BLT:J/2END？SHU10060↙【指导说明】：

画完树杈后，海龟要回到原来起始的位置和方向。

⑵、第二步：画二叉树。(编程步骤)【编程关键】：

寻找生叉点并逐一在此处添加递归调用命令。

TOSHU:B:J

LT:J/2FD:B

BK:BRT:JFD:B

BK:BLT:J/2ENDSHU:B/2:JIF:B<10STOPSHU:B/2:J“递归”插入点

?SHU80604↙?SHU80604↙2、深入探究：从创造思维入手，运用“图形想象”的方法去思维、推理和解决问题。在搞清楚“二叉树问题”的基础上，经过变形的各种树的问题就易解。从而总结出用递归进行程序设计的规律和方法。

【指导说明】：⑴、分析每个图形的最基本图形。⑵、确定海龟起始的位置与方向。⑶、找出上下层“递归”插入点。⑷、先编写出最底层的图形过程。⑸、执行过程确定图形正确无误。⑹、逐一插入“递归”步步为营。第二步：编写基本三角形SJ过程。画出如图所示图形⑴、在操作中学：画出左图所示图形。第一步：分析图形的基本结构。基本图形从三角形到树叉TOSJ:BLT90FD:B/2RT120FD:BBK:BRT60FD:BLT120FD:BBK:BLT60FD:B/2RT90ENDTOSJ:B

LT90FD:B/2

RT120FD:B

BK:BRT60FD:B

LT120FD:BBK:BLT60FD:B/2RT90END？SJ100↙逐一添加“递归”与“调整”LT30SJ:B/2RT30RT30SJ:B/2LT30LT30RT30SJ:B/2IF:B<10STOP30°第三步：在上面的过程基础上，逐一插入“递归”命令行。

？SJ100↙？SJ100↙？SJ100↙⑵、在操作中学：再以“递归”插入点直接画出上图形。TOSJA:BIF:B<10STOP

PULT60BK:B/4LT60PDSJA:B/2\PURT60FD:B/4RT60PDFD:BRT120

PULT60BK:B/4LT60PDSJA:B/2\PURT60FD:B/4RT60PDFD:BRT120

PULT60BK:B/4LT60PDSJA:B/2\PURT60FD:B/4RT60PDFD:BRT120ENDTOSJB:BIF:B<10STOPLT90FD:B/2

LT30SJB:B/2RT30RT120FD:B

LT30SJB:B/2RT30RT120FD:B

LT30SJB:B/2RT30RT120FD:B/2RT90END？DRAWRT30SJA100↙？DRAWSJB100↙动脑筋，画一画⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾⑿三、多阶递归过程在一个递归过程体中进行了若干种不同级的递归调用。1、在操作中学：画出右图所示图形。TOD:BFD:BLT45RT45RT45LT45BK:BENDTODD:N:B:JIF:N<0STOPFD:BLT45

DD:N-2:B*:J*:J:JRT45

DD:N-1:B*:J:JRT45

DD:N-2:B*:J*:J:JLT45BK:BEND？FSDD81000.65↙

？D100↙

【说明】：:N是级数参数，:B是尺寸参数，:J是相邻两级树的尺寸比例参数。2、在操作中学：:S由0变大时树会不同程度地往一边倾斜。TODSB:L:NIF:N<1FD:LSTOPREPEAT2[LT90FD:N/2RT90\FD:LRT90FD:N/2RT90]DSB:L:N-2ENDTODSC:B:A:SIF:B<5STOPDSB:B:B/10LT:A-:S

DSC:B*0.6:A:SRT:A

DSC:B*0.8:A:SRT:A

DSC:B*0.6:A:SLT:A+:SBK:BEND?DSC50300↙?DSC50305↙?DSC503010↙【说明】：:B是树干尺寸参数，:A是相邻两树叉夹角参数，:S是风力大小参数。?DSB1005↙3、在操作中学：画出右图所示图形。TOSJG:B:JIF:B<10LT90YUAN5RT90STOPLT:J/2FD:BSJG:B/2:JBK:BRT:JFD:B/2RT90FD:B/2

LT90YUAN5RT90BK:B/2LT90FD:B/2SJG:B/2:JBK:BLT:J/2ENDTOYUAN:RREPEAT360[RT0.5FD:R*PI/180RT0.5]END？SJG10060↙4、想一想：在下面过程中插入“递归”，画出的图形怎样？TOJ2:BIF:B<10STOPREPEAT3[FD:BRT120J2:B/2]ENDTOZ1:BIF:B<10STOPREPEAT4[FD:BZ1:B/2RT90]ENDTOZ2:BIF:B<10STOPREPEAT4[FD:BRT90Z