递归作图开拓性的新思维①—认识“递归模式图”
原创作者:林正山老师
“中间递归”是LOGO语言中功能最为强大的“武器”,它能够以极其简炼的程序语句画出非常复杂的图形,例如最基础、最常见的“二叉树”。
下面列出来的就是画“二叉树”的LOGO程序。
TO TREE01 :B :N
IF :N=0 THEN STOP
FD :B RT
45
TREE01 :B/2 :N-1
LT
90
TREE01 :B/2 :N-1
RT 45 BK
:B
END
画“二叉树”的程序并不复杂,但是在过去从来没有一篇教科书把“为什么二叉树的程序必须这样编写”的道理以简单明了的形式说明清楚过。有许多说法甚至反而让人看了越来越糊涂。
这其中的原因就在于:缺少一种科学的,但有是十分简单的方式来描述LOGO递归作图的原理。
其他种类的计算机程序设计语言,对于抽象的编程逻辑问题,一般都有一些简单明了的“工具”来帮助编程者看懂程序。而这些好用的工具不仅能够帮助人们借助这些图解看懂复杂的程序,更是能够在编写程序之前,作为编程者考虑“程序应该如何编写”的规划工具。
上述这些工具中比较著明的有“常规流程图”、“N-S流程图”、“LS文法图”。
遗憾的是,LOGO语言中从来就缺少这样的“工具”。这对LOGO语言的继续发展形成了障碍。
林老师从事LOGO语言教育已有二十余年,编写过五个版本的少年儿童计算机学习用书,编写过几千个绘图及计算的LOGO程序。积以往编程之体会,于2006年创立了“递归模式图”,用以解释所有复杂递归作图问题的构成规律。
“递归模式图”经过数年在教师、学生中推广使用,效果良好。实践证明这是一种简单易懂、直观明了,并且能够使“模式图”与“程序”严格对应的一种专属于LOGO语言的编程工具。
在引进了中间递归的“递归标识点”概念以后,只要看着某个中间递归程序的“模式图”,再复杂的图形,程序的构造规律都将一目了然。如果给出一个“递归模式图”,对应着“模式图”编写程序,LOGO编程也将变得易如反掌。
“递归模式图”包括以下3种“递归标识点”:“递归起点”、“递归点”、“插花点”。
“递归起点”——递归运算的开始点。许多递归程序需要“归零”,程序最终要回到这个“起点”。但是递归的“起点”并不一定都是整个程序的开始,像“无干二叉树”整个程序的开始处,就不是递归的“起点”。
“递归点”——“递归点”规定了海龟运动到这个位置、这个方向,就执行递归。“递归”是调用了程序自身,在递归点上复制了整个程序的信息模式,所以画出来的下一级图形总是和上一级相似。这种自我相似的现象就是“分形”。
“插花点”——“插花”是在递归层次的{zh1}一级画出规定的图形的运算。“插花”是LOGO递归算法中最为巧妙的运算,
“插花”运算将在后续文章中详细介绍。
“起点”、“递归点”中的箭头标记,标示出的是海龟的位置和海龟的指向,并不包含海龟的移动信息,也不包括图形递归过程中画图尺寸逐级增加或减少的信息。
一个递归程序画出的图形不论多么复杂,但是递归的“{dy}级”总是十分简单的。把递归图形的初始状态标上“起点”,以及需要在哪里设立“递归点”,就成为“模式图”了。
“模式图”不仅能应用于“中间递归”图形,也能应用于许多“尾递归”图形。“模式图”里包含了编写递归程序的全部的思路和编程技巧。“模式图”总是和递归程序严格地对应的。有了这样的“模式图”,就能轻松地编写出各种LOGO递归程序。
画递归图形的模式图需要借助TOOLS程序。把下面几个过程用TOOLS文件名存起来,需要时调用。
TO TOOLS ;画递归模式图的工具
DRAW HT QIDIAN
PU SETX 50 PD DIGUI
PU SETX 100 PD CHAHUA
END
TO QIDIAN ;画起点符号的命令
PU FD 4 RT 90 PD
REPEAT 360 [FD 4 * PI / 180 RT 1] ;画起点小圆圈
PU LT 90 FD 4 RT 90 PD
REPEAT 360 [FD 8 * PI / 180 RT 1] ;画起点大圆圈
SETW 3 LT 90 FD 17 YM BK 8 SETW 1
PU BK 8 PD
END
TO YM ;画起点上端羽毛状符号
SETW 1
REPEAT 3 [RT 120 FD 9 BK 9 RT 120 FD 9 BK 9 RT
120 BK 3]
END
TO DIGUI ;画递归点符号的命令
SETW 8 DOT SE XCOR YCOR
;画底部的点
SETW 3 FD 38 RT 150 FD 9 BK 9 ;画杆和箭头
LT 300 FD 9 BK 9 RT 150 BK 38 SETW 1
END
TO CHAHUA ;画插花点符号的命令
SETW 8 DOT SE XCOR YCOR
;画底部的点
SETW 3 FD 28 LT
60
;画杆
REPEAT 5 [PU FD 5 PD FD 7 PU BK 12 RT 30]
;画顶部分叉
LT 90 BK 28 PD SETW 1
END
运行TOOLS命令,画出来的是前面介绍给大家的3种“递归标识点”图形。
在林老师编写的《LOGO语言竞赛习题集》和《LOGO语言竞赛教程》中,几百个递归图形全部都标示上了“递归模式图”,这给LOGO语言学习者带来了极大的方便。
待续
为方便大家查询资料,特此建立以下链接:
林老师{zx1}发表博客的链接:
林正山老师邮箱:
声明:
林正山老师发表的文章,媒体、网站或出版物未经本人许可不得转载。个人博客可以转载,转载时请注明作者姓名、文章原始出处,或以链接形式标明来源。
《LOGO语言竞赛教程》国际标准书号书号ISBN978-7-5335-3424-0,34.1万字、414页,定价22.00元,《LOGO语言竞赛习题集》国际标准书号ISBN978-7-5335-3425-7,39.6万字、481页,定价26.00元。两本书均大32开本,封面采用250克铜版纸,四色全彩印刷,内文采用60克胶版纸,黑白印刷,福建省科技出版社出版。