递归程序教学.docx
- 文档编号:7214094
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:26
- 大小:345.61KB
递归程序教学.docx
《递归程序教学.docx》由会员分享,可在线阅读,更多相关《递归程序教学.docx(26页珍藏版)》请在冰点文库上搜索。
递归程序教学
LOGO递归程序教学
一、什么是递归?
递归就是把求未知结果回归成对已知内容进行求解。
数学中经常用自身的简单情况来定义自己。
如,阶乘n!
=1*2*3*…*n,可定义为:
在LOGO语言中,递归是指一个过程直接或间接地调用该过程本身,这种调用方法叫做“递归调用”,相应的过程叫做“递归过程”。
二、递归图形
有些图形,它本身又包含一个或多个与整个图形相似的图形(只是大小上的差别),这样的图形我们把它称为递归图形。
可以用递归过程来绘出图形。
三、递归过程的基本结构
TO过程名参数表
IF<递归结束条件>STOP
…
过程名参数表
…
END
四、尾递归
尾递归是递归中最简单的一种特殊情况,其基本形式是在过程的最后(END语句之前)调用过程自身,构成循环。
人们很熟悉的“老和尚讲故事”的故事,由于故事的情节里边又讲述了故事的本身,所以这个故事可以无限地反复,永远讲下去。
这就是尾递归一个很形象的例子。
什么样的图形,用尾递归来解
例1 画“正大”图形
画出上图最左边的图形,其中最小正方形的边长为5,最大正方形边长不大于100。
[算法分析]该图形由若干个“正大”形图形组成,且相邻两个半径相差一倍。
我们可从最小的“正大”形图形开始一个一个画出。
因此画“正大”图形过程的结束前可递归调用(尾部)自己,画出下一个“正大”图形,一直到边长大于100。
TOZHENGDA:
R
FD:
R/2REPEAT360[FD:
R/2*PI/180RT1]
BK:
R/2REPEAT7[FD:
RRT90]
END
TODO:
X
IF:
X>100STOP
ZHENGDA:
XRT90
DO:
X*2
END
TOMAIN
DRAWDO5
END
例2画多个等边长多边形
画出上图最右边的图形。
[算法分析]我们可以先画正三边形,然后画正四边形、…最后画正九边形。
由于画正多边形有统一的公式,因此,可以编写一个画n边形的过程,在过程结束前递归调用自己,画n+1边形。
TODBX:
N:
ATOMAIN
IF:
N>10THENSTOPDRAWDBX350
REPEAT:
N[FD:
ART360/:
N]END
DBX:
N+1:
A
END
尾递归过程的执行步骤
尾递归总结
尾递归的作用类似于重复命令,直到一个条件成立。
因此,尾递归可看成是一种特殊的重复命令。
五、中间递归
在过程的中部递归调用本过程,称为中间递归(过程)。
什么样的图形,用中间递归来解。
例3画嵌套三角形
画出如图所示若干个正三角形嵌套在一起的图形,最外三角形的边长为N。
[算法分析]如下图所示我们先画边长为N的三角形的两边和第三边的一半后,画最外三角形边长为N/2的嵌套三角形(原问题类似的问题),最后画边长为N的三角形的第三边的另一半,并让海龟回到初始位置,方向为原方向。
TOSJX:
N
IF:
N<5STOP
REPEAT2[FD:
NRT120]
FD:
N/2RT60
SJX:
N/2
LT60
FD:
N/2
RT120
END
DRAWLT30SJX150
中间递归过程的执行步骤
例3
例2
六、用递归程序画“树形图案”
1、二叉树程序
[说明]图中,树干长为100,每次分叉后,边长都减半,最短不小于5。
[算法分析]这棵二叉树由树干和左子树、右子树组成。
左右子树又是与整棵类似的二叉树。
画整棵二叉树时,从根开始,先画树干,然后左转45度画左子树,接着右转90度画右子树,最后再左转45度后退回到根。
(最后回到根是很重要的)
二叉树基本图形程序:
TOTREE:
N
FD:
N
LT45
RT90
LT45BK:
N
END
TOTREE:
N
IF:
N<5THENSTOP
FD:
N
LT45 TREE:
N/2
RT90 TREE:
N/2
LT45 BK:
N
END
TOMAIN
DRAW TREE80
END
递归树程序的各种变形
①基本型(角度变小):
TOSHU1:
A:
N
IF:
N=0STOP
FD:
ALT30
SHU1:
A*.6:
N-1
RT60
SHU1:
A*.6:
N-1
LT30BK:
A
END
②节点处加入小圆,两分支长度不同:
TOSHU2:
A:
N
IF:
N=0STOP
FD:
ALT60REPEAT36[FD:
A*PI/180RT10]RT30
SHU2:
A*.6:
N-1
RT60
SHU2:
A*.5:
N-1
LT30BK:
A
END
③改变树干宽度,增加分支,各分支长度不同:
TOSHU3:
A:
N
IF:
N=0STOP
SETW:
N/2+.5FD:
ALT30
SHU3:
A*.7:
N-1
RT20
SHU3:
A*.6:
N-1
RT20
SHU3:
A*.8:
N-1
RT20
SHU3:
A*.5:
N-1
LT30BK:
A
END
2、圣诞树程序(2002省赛复试题二)
编写程序FPOI2(主过程FPOI2:
R)能画出如图所示的三叉树,其中每层三叉树的左右枝为90度半径为R的等弧,中间是长度与半径为R的90度的弧弧长相等的直线段,上层弧半径是下层弧半径的一半。
最小弧半径不小于5.例如FPOI240画出如下的图形。
参考答案:
TOFPOI2:
R
DRAWHT
A2:
R
END
TOA2:
R
IF:
R<5STOP
FD:
R*PI/2
A2:
R/2
BK:
R*PI/2
REPEAT9[RT5FD:
R*PI/18RT5]
A2:
R/2
REPEAT9[LT5BK:
R*PI/18LT5]
REPEAT9[LT5FD:
R*PI/18LT5]
A2:
R/2
REPEAT9[RT5BK:
R*PI/18RT5]
END
圣诞树基本图形程序:
TOA2:
R
FD:
R*PI/2
BK:
R*PI/2
REPEAT9[RT5FD:
R*PI/18RT5]
REPEAT9[LT5BK:
R*PI/18LT5]
REPEAT9[LT5FD:
R*PI/18LT5]
REPEAT9[RT5BK:
R*PI/18RT5]
END
3、仙人掌程序
[问题说明]图中叶子均为100度弧,且仙人掌左右分叉的中轴的夹角为90度。
[算法分析]
这个图形显然是一个递归图形,因此我们可以按如下步骤画图:
(1)左转100/2度,先画图中最下面的叶子中的左弧,然后再左转100/2,使得海龟方向朝正上方;
(2)左转45度,准备画左子图;
(3)画左子图(递归调用);
(4)右转90度,准备画右子图;
(5)画右子图;
(6)左转45度;
(7)右转180-100/2度;
(8)画出图中最下面的叶子中的右弧;
(9)右转180-100/2度,使海龟方向与画图前一致。
TOHU:
R:
J
REPEAT:
J[RT0.5FD:
R*PI/180RT0.5]
END
仙人掌基本图形程序
TOXRZ:
R:
J
LT:
J/2 HU:
R:
J
LT:
J/2 LT45
RT90
LT45
RT180-:
J/2 HU:
R:
J
RT180-:
J/2
END
TOXRZ:
R:
J
IF:
R<5STOP
LT:
J/2 HU:
R:
J
LT:
J/2 LT45
XRZ:
R/2:
J RT90
XRZ:
R/2:
J LT45
RT180-:
J/2 HU:
R:
J
RT180-:
J/2
END
执行:
XRZ80100
七、用递归程序画“分形图形”
[要求]画出右图所示的分形图形
[算法分析]该图形的基本轮廓图形如图1,由四个部分组成,每个部分的图形与整个图形类似(大小为原来的1/3),显然可用递归过程画出该图。
TOFX:
N
IF:
N<5FD:
NSTOP
FX:
N/3 LT60
FX:
N/3 RT120
FX:
N/3 LT60
FX:
N/3
END
TOMAIN
DRAW RT90FX100
END
仔细分析上面的程序,可以发现,如果删除IF语句,并用IF语句中的FD:
N取代递归语句FX:
N/3,就变成了下面这个画出基本图形的程序了。
TOFX:
N
FD:
N LT60
FD:
N RT120
FD:
N LT60
FD:
N
END
由此,我们也可以找到编写分形递归程序的简单方法:
先编写画出基本图形的程序,然后在需要出现分形图形的位置加入递归命令,最后加入控制程序结束和画出线段的条件语句就可以了。
[练习]编写画出下面分形图形的程序:
TOFX2:
M:
N
IF:
N=0FD:
MSTOP
FD:
M/3LT90
FX2:
M/3:
N-1RT90
FX2:
M/3:
N-1RT90
FX2:
M/3:
N-1LT90
FD:
M/3
END
TOFX3:
M:
N
IF:
N=0FD:
MSTOP
FD:
M/3LT108
FX3:
M/3:
N-1RT72
FX3:
M/3:
N-1RT72
FX3:
M/3:
N-1RT72
FX3:
M/3:
N-1LT108
FD:
M/3
END
八、用递归程序画“平面图案”
1、十字地毯
tomain
drawbb35
end
tobb:
n:
s
repeat2[aa:
n:
slt90fd:
slt90]
end
toaa:
n:
s
if:
n=0[fd:
srt90fd:
slt90fd:
slt90fd:
srt90fd:
sstop]
aa:
n-1:
s
rt90fd:
slt90fd:
srt90
aa:
n-1:
s
lt90fd:
slt90
aa:
n-1:
s
rt90fd:
slt90fd:
srt90
十字地毯基本图形程序:
toaa:
n:
s
fd:
srt90fd:
slt90fd:
slt90fd:
srt90fd:
s
rt90fd:
slt90fd:
srt90
fd:
srt90fd:
slt90fd:
slt90fd:
srt90fd:
s
lt90fd:
slt90
fd:
srt90fd:
slt90fd:
slt90fd:
srt90fd:
s
rt90fd:
slt90fd:
srt90
fd:
srt90fd:
slt90fd:
slt90fd:
srt90fd:
s
end
aa:
n-1:
s
end
2、迷宫图案
“迷宫”曲线,又称为“希尔伯特曲线”。
这是一个包含4层中间递归的过程。
其中参数:
B控制图形最小线段的长度,:
N控制递归的深度,:
J控制线段转弯的角度。
在使用MG10490命令时,画出的是一个一笔画正方形的迷宫,十分漂亮。
TOMIGONG:
A
DRAWHT
PUSETXY[150-100]PD
MG5:
A90
END
TOMG:
B:
N:
J
IF:
N=0STOP
LT:
J
MG:
B:
N-10-:
J
FD:
BRT:
J
MG:
B:
N-1:
J
FD:
B
MG:
B:
N-1:
J
RT:
JFD:
B
MG:
B:
N-10-:
J
LT:
J
END
九、递归编程参考实例
图形一:
TODGT:
B:
N
IF:
N=0STOP
REPEAT9[LT5FD:
B*PI/18LT5]
DGT:
B/2:
N-1RT180]
REPEAT9[LT5FD:
B*PI/18LT5]
DGT:
B/2:
N-1RT180]
REPEAT9[LT5FD:
B*PI/18LT5]
DGT:
B/2:
N-1RT180]
REPEAT9[LT5FD:
B*PI/18LT5]
END
将相同部分用重复命令改写后:
TODGT:
B:
N
IF:
N=0STOP
REPEAT3[REPEAT9[LT5FD:
B*PI/18LT5]DGT:
B/2:
N-1RT180]
REPEAT9[LT5FD:
B*PI/18LT5]
END
图形二:
TOZZF:
A:
C
IF:
C=0STOP
FD:
A
ZZF:
A/2:
C-1
REPEAT2[RT90FD:
A]RT180
ZZF:
A/2:
C-1
LT90FD:
ART90
END
图形三:
TOO1:
A
IF:
A<20STOP
REPEAT2[REPEAT18[RT5FD:
A*PI/18RT5]O1:
A/2]
END
图形四:
TOO2:
A
IF:
A<30STOP
REPEAT4[REPEAT9[RT5FD:
A*PI/18RT5]O2:
A/2]
END
图形五:
TOSJX:
A:
N
IF:
N=0STOP
REPEAT3[FD:
A/2LT120SJX:
A/2:
N-1RT120FD:
A/2RT120]
END
图形六:
TOSJ:
A:
B
IF:
A<:
BSTOP
REPEAT3[FD:
ART120SJ:
A/2:
B]
END
图形七:
TOZF:
A:
B
IF:
A<:
BSTOP
REPEAT4[FD:
ART90ZF:
A/2:
B]
END
图形八:
TOSJT:
A:
N
IF:
N=0STOP
SJ:
A:
N
RT60BK:
ALT60BK:
A*(:
N-1)
SJT:
A:
N-1
END
TOSJ:
A:
N
IF:
N=0STOP
REPEAT4[FD:
ALT120]RT120
SJ:
A:
N-1
END
图形九:
尾递归画法:
TOYUAN2:
A:
N
IF:
N=0STOP
REPEAT54[LT5FD:
A*PI/18LT5]
YUAN2:
A*.7:
N-1
END
中部递归画法:
TOYUAN2:
A:
N
IF:
N=0STOP
REPEAT18[LT5FD:
A*PI/18LT5]
YUAN2:
A*.7:
N-1
REPEAT18[LT5FD:
A*PI/18LT5]
END
图形十:
TOFYH:
A:
N
IF:
N=0STOP
REPEAT4[FD:
ART90]
REPEAT9[RT5FD:
A*PI/18RT5]
FYH:
A*.618:
N-1
END
图形十一:
尾递归:
TOSHU:
A
IF:
A<5STOP
FD20BK10LT50FD:
ABK:
A
RT100FD:
ABK:
ALT50
SHU:
A-4
END
中部递归:
TOSHU:
A
IF:
A<5STOP
FD20BK10LT50FD:
ABK:
ART50
SHU:
A-4
RT50FD:
ABK:
ALT50BK10
END
图形十二:
TOMEN:
X
IF:
X<10RT90STOP
REPEAT6[FD:
XRT90]LT180
MEN:
X/2
REPEAT6[FD:
XRT90]LT180
END
图形十三:
TOJZT:
A:
N
IF:
N=0STOP
REPEAT:
N[REPEAT7[FD:
ART90]RT90]
FD:
ALT90FD:
A*:
N-:
A/2RT90
JZT:
A:
N-1
END
图形十四:
TODCT:
A:
N
IF:
N=0TAD:
ASTOP
REPEAT3[FD:
ART90]LT90
BK:
A*1.2LT45FD:
A*.4RT45FD:
A*.8RT180
DCT:
A*.8:
N-1
BK:
A*.8RT45BK:
A*.4LT45FD:
A*1.2
REPEAT3[BK:
ART90]RT90
END
TOTAD:
A
REPEAT3[FD:
ART90]LT90
REPEAT3[FD:
A+3LT120FD:
A+3]
REPEAT3[FD:
ART90]LT90
END
图形十五:
TOAA:
R:
N
IF:
N=0STOP
STAMPOVAL:
R:
RPUFD1.8*:
RPD
AA:
R*0.8:
N-1
END
TOTHL:
P:
N
REPEAT:
P[FD20PUFD10PDAA10:
NPUSETXY[00]PDRT360/:
P]
ENDd
图形十六:
TOHJ1:
A:
C
IF:
C=0STOP
LT30BK:
ALT60FD:
A/4RT90
HJ1:
A/4:
C-1
LT90FD:
A/4RT90
HJ1:
A/4:
C-1
LT90FD:
A/4RT90
HJ1:
A/4:
C-1
LT90FD:
A/4RT120FD:
ALT30
END
TOHJ2:
A:
C
IF:
C=0STOP
LT25BK:
A*1.18LT65FD:
A/4RT90
HJ2:
A/4:
C-1
LT90FD:
A/4RT90
HJ2:
A/4:
C-1
LT90FD:
A/4RT90
HJ2:
A/4:
C-1
LT90FD:
A/4RT115FD:
A*1.18LT25
END
TOHJ3:
A:
C
IF:
C=0STOP
RT150-20HU40:
A*PI/2*.95RT100FD:
A/4RT90
HJ3:
A/4:
C-1
LT90FD:
A/4RT90
HJ3:
A/4:
C-1
LT90FD:
A/4RT90
HJ3:
A/4:
C-1
LT90FD:
A/4RT100HU40:
A*PI/2*.95LT50
END
TOHU:
J:
R
REPEAT:
J[RT.5FD:
R*PI/180RT.5]
END
图形十七:
TOHU:
R:
J
REPEAT:
J[FD:
R*PI/180RT1]
END
TOXRZ2:
R:
J
IF:
R<5STOP
LT:
J/2HU:
R:
J*2/3LT70
XRZ2:
R/3:
J
RT70HU:
R:
J*1/3
LT:
J/2LT45
XRZ2:
R/2:
JRT90
XRZ2:
R/2:
JLT45
RT180-:
J/2HU:
R:
J*1/3LT110
XRZ2:
R/3:
J
RT110HU:
R:
J*2/3
RT180-:
J/2
END
其它图形:
十、递归调用的基本规则
1、过程递归调用时,将会有一些同名的过程暂时共存的现象发生。
2、暂时共存的每一个过程都有自己独立的参数专用库。
3、在过程递归调用时,被调用的过程停止后,将返回调用它的上一级过程,并从调用命令的下一条命令继续执行下去。
十一、用递归程序画图的基本步骤
无论多么复杂的递归图形都是由一个简单的基本图形派生出来的。
所以,在编写一个画递归图形的程序时,一般可以按以下步骤进行:
1、认真分析其中的基本图形是什么,其递归插入点在哪里。
2、象编写普通绘图程序一样,编写能画出基本图形的LOGO程序。
编写基本图形程序时,应注意留下程序的递归插入点,插入点前后为进行递归所作的海龟转向命令也应写上。
3、在基本图形程序各个递归插入点插入递归语句,并在适当位置插入控制程序结束的IF语句。
结束语
递归程序设计是一个很抽象的智力活动,对小学生来讲是比较困难的,但递归程序设计也有一定的规律可循。
正确理解、掌握递归程序设计的基本方法,对学生智力的培养将有很大的帮助。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 程序 教学
![提示](https://static.bingdoc.com/images/bang_tan.gif)