问题讨论：LOGO语言中慎用“递归”进行数学计算

    仔细看看前面的“三角形”一定会很惊讶：这样复杂的“三角形”竟然是“一笔画”。当递归的级数为5级时，图形已经相当复杂，一根线条缠绕到底，构成了一个分形三角形。当递归的级数是9级时，具体的线条已经密集到分辨不出来的程度了。这确实是递归图形的奇观。

    而且画这个图形的主递归过程只用了区区6行LOGO程序。如果换用其他计算机语言来编写，恐怕30行、50行程序也编不出来。

    这就是LOGO语言的递归的优势了。我们不得不说：

    LOGO语言的递归真是个好东西!

    LOGO语言在数学计算方面也表现得相当好。例如林老师开发的《计算有周率到小数下10000位》以及即将陆续发表的

    《任意位数高精度加法》、

    《任意位数高精度减法》、

    《任意位数高精度乘法》、

    《任意位数高精度除法》、

    《任意进制数的换算》

等等。许多事实都将证明：LOGO语言的计算功能是大有作为的。

    但是，有个一个问题：数学计算是不是都要使用LOGO递归，那就值得讨论了。

    最近林老师接到若干封电子邮件，看到的是用递归编写的进行数学计算的，怎么都搞不清楚毛病在哪里的程序。

    大家都应该弄清楚：在LOGO语言中使用递归方式进行数学计算，程序确实常常显得非常优雅、简练。

    例如计算“高斯百数求和问题” 1+2+3+…+100=5050 可以有许多种方式，使用FOR循环程序是这样编写的。

    TO JS100_B

      MAKE "S 0   ;累加器的值是0

      FOR "N 1 100[MAKE "S :S + :N] ;循环变量就是加数

      (PR [S=] :S)   ;显示计算的结果

    END

    这个问题不使用递归，可能有不下于十几种编程方式（请参考林老师的《LOGO语言竞赛教程》P296～P299）。

    不过，高斯百数连加问题也能够用递归编程：

    0+1+2+……+N的计算当然可以倒着从高位N向下加上N-1……一直加到0。编成中间递归程序是这样的。

    TO SUM_ :N  ;计算累加和

      (PR[SUM=] F :N) ;输出计算结果

    END

    TO F :N  ;计算累加的和

      IF :N=0 THEN OP 0 ELSE OP :N+(F :N-1)

    END

    在这个问题上，递归算法马上就显示出它的局限性：用这样的算法从0加到10,和等于55是正确的。

    ? SUM_ 10 ;从0加到10 的和是55

    SUM = 55

    累加超过46的数时LOGO系统就无法计算了，提示：“调用过多的递归过程”。

    ? SUM_ 47  ;计算从0加到47时系统提示：调用过多的递归

    Too many recursive procedure calls.

 

    这个例子告诉我们，递归的级数太多时，LOGO系统可能承载不了。相类似的例子还有“八皇后问题”（参见林老师的《LOGO语言竞赛教程》P354～P358）使用递归算法的LOGO程序明明没有错，就是算不下去，最后改用现有的算法，才算解决了这个难题。

    在林老师的《LOGO语言竞赛教程》P315～P318共介绍了其他多个可以使用中间递归编程的例题。

 

    这里需要讨论的关键问题在于：到底应该在那些情况下使用递归？

    ①使用递归画图，优越性是不言而喻的。特别是画图递归题，常常递归到8～10级，图形就已经非常精细了。这样数量级的递归，在LOGO系统可以容忍的范围内。

    ②在使用递归进行数学计算时，如果是“尾递归”，反复进行计算，在多数情况下问题不是很大。

     ③用其他类型的“递归”就要慎重了。在使用“中间递归”、“首递归”、“多重递归”算法的计算问题，程序往往极其抽象难以理解。有许多时候递归的次数很多了，还是出不了结果，那就应当考虑使用FOR循环等更加直观、更加简单的方法进行计算。

 

    所以，我们应该认识到：

    递归与循环是两种不同的解决问题的思路。

    递归算法的优点是：代码简洁、思路巧妙。缺点是：它的运行需要较多次数的函数调用，对计算机内存资源的开销很大(甚至让计算机无法承载)，而且递归算法的程序往往较难懂。

    循环编程的优点：效率高，结构简单，程序易懂。缺点：并不能解决所有的问题。一般的问题如果能使用循环的话，最好还是使用循环来计算。

    这样的问题是不是值得所有编写LOGO的人引起注意呢？

 

 

 

这里是新颖有趣的LOGO、DEV-C++语言之家

欢迎评论 欢迎转载

 

查找林老师博客最便捷的方法：

  在百度、谷歌、搜狗、搜搜、雅虎、有道等搜索引擎中输入

   林老师 LOGO 就能找到林老师博客文章了

 

查阅林老师最新发表文章的链接：

      http://blog.sina.com.cn/lzs2099 
  

快速检索数百篇博客提高阅读效率的链接：

 《LOGO语言简明教程》及初学者题库
  《LOGO语言画图编程题》目录
  《LOGO及DEV-C++计算编程题》目录
  《LOGO竞赛试题及解题分析指导》目录
  《LOGO语言编程新理念及编程技巧》目录
  《奥数及趣味数学问题》目录
  《LOGO语言竞赛教程·习题集内容剖析》目录
  《林老师话说天南地北》目录 

   初学者题库及编程技巧分析

查看林老师拍摄及推荐的照片的链接

 

林正山老师邮箱：  linzhengshan@21cn.com

因网络拥挤“纸条”常不能及时打开查阅。有信息尽量使用“评论”或邮件。 

 

需要LOGO系统文件常用表格工具文件及DEV-C++系统文件的可以发邮件给林老师

 

声明：
    林正山老师发表的文章及照片，媒体、网站或出版物未经本人许可谢绝进行任何形式的删节、改编、重组及转载。

    允许个人博客按原文(含图片及附注)进行完整转载，转载时敬请注明本博作者姓名、文章原始出处，并以链接形式标明来源。