《程序语言教学中的递归程序思维培养.doc》由会员分享，可在线阅读，更多相关《程序语言教学中的递归程序思维培养.doc（15页珍藏版）》请在三一文库上搜索。
1、程序语言教学中的递归程序思维培养 递归程序设计思想在程序语言教学中处于重要地位，也是程序语言教学的难点。这篇论文从明确递归程序思想教学目标入手，从实际例子出发来引导学生正确理解递归思想并初步掌握其设计的基本方法。在此基础上通过构造趣味教学案例，巧妙设局，层层引入，从多方面多角度训练和培养学生的递归程序思维。通过以上教学环节的实施，取得了较好的教学实施效果，学生普遍接受了递归程序设计思想，并自觉运用递归程序设计思想来解决实际问题。 The Training of Recursive Programming Thought in Programming Language Teaching SHAO
2、 Li-ping (School of Computer Science, Shaanxi Normal University, Xian 710062, China) Abstract The recursive programming thought plays an important role in programming language teaching and It is also the key and difficult point in teaching of programming language. This paper instruct students to cor
3、rectly understand the recursive thought and preliminary grasp the basic idea of the recursive programming design method by utlizing the practical examples. Based on this foundation, students recursive programming thought is trained and improved from all angles and aspects by introducing interesting
4、teaching cases, setting trips skillfully and multiple extention. From the above performed teaching means, a good teaching effect is obtained and the students generally accepted the recursive programming thought by consciously using it to solve the practical problems. Key words programming language t
5、eaching; recursive; programming thought; programming design; teaching case 进行计算机基础课程学习特别是程序语言教学已成为我国高校计算机专业和非计算机专业计算机教学中必备的一环。无论是计算机专业还是非计算机专业学生，有效地培养其计算机程序设计思维，将对其后继的专业课程学习和未来有效地运用计算机解决本专业的实际问题产生深远影响。 计算机编程思维主要体现在用特定的程序语言进行思考，将自己的想法转换为程序，按计算机的逻辑教会计算机怎么做；分而治之地解决问题，即将复杂问题细化为简单问题并一一击破，而所有问题的解决等价于复杂问题的
6、最终求解；程序算法的有始有终，既有特定的入口，也有特定的出口。 而作为计算机编程思维分治思想的典型代表递归程序设计思想在程序语言教学中处于重要地位，也是历来进行程序语言教学和考核学生的难点。利用递归可完美地解决许多复杂的数学问题，运用递归程序设计思想编写出来的程序，具有结构清晰，可读性强，但其简练的背后蕴含着高度的复杂性，对于刚接触计算机编程的学生而言，往往感到深不可测、难以理解1-2。 如何使学生真正地接受递归程序设计思想，了解递归程序的特性，掌握递归程序的设计方法并自觉运用递归程序解决本专业的实际问题，成为摆在每位程序语言授课教师面前的首要解决问题。结合笔者近年来从事程序语言教学所获取的教
7、学经验，该文从明确递归程序思想教学目标入手，从贴近人们日常工作生活的例子出发，来引导学生正确理解递归思想并初步掌握递归程序设计的基本方法。在此基础上给出了通过构造趣味教学案例，巧妙设局，层层引入，从多方面多角度训练和培养学生的递归程序思维的教学方法。实践表明以上教学手段的有效实施，可使学生普遍地接受递归程序设计思想并自觉运用递归程序设计方法来解决实际问题，从而取得了较好地教学实施效果。 1 明确教学目标，从实际例子出发引导学生正确理解递归程序思想并初步掌握递归程序设计的基本方法 所谓递归，就是指一个过程和函数通过直接或间接地调用自己3，使问题求解规模不断下降，当问题简单到可以直接求解时，则可逐
8、级返回，最终使复杂问题得以解决。在递归调用时，必须设置一定的条件作为退出递归调用的出口，当条件满足时，则返回对应的计算结果，反之则继续调用自己，将复杂问题进一步简化。 递归程序设计思想主要体现程序编程思维中的分治思想，同时也满足计算机算法的一般特征，即有始有终。因此在向学生讲解递归程序设计思想时，应明确三个教学目标寻找复杂问题和同类简单问题之间的递推关系，从而将复杂问题进行简化4；留好最简单问题的求解出口，当问题降低到最简单规模时，则可顺次求解；明确递归程序的执行线索，了解递归所暗含的压栈出栈过程，从而理解递归程序表达的简练并不代表执行效率的高效性。 其中，目标体现了程序分治思想，即将一个复杂
9、问题不断细化直至简单求解的过程，其求解方向是由整体到局部，由复杂到简单和由高阶到低阶；目标体现了算法的有始有终思想，只有简单问题能够求解，复杂问题才依次得以求解，其问题求解方向为由局部到整体，由简单到复杂，由低阶到高阶；目标即涵盖了目标的执行线索，即先由整体到局部，复杂到简单，高阶到低阶，体现为栈中问题不断堆积的过程4，问题求解规模的不断分解和简化，一旦栈中问题可以求解，则表现为栈中问题的依次弹出，由局部到整体，由简单到复杂，由低阶到高阶，从而复杂问题随着问题的求解规模的不断加大而渐次求解，最终整个问题得以完美解决。 递归尽管理解起来比较抽象，但也没有脱离人类自身实践，它的解决问题思路也和人类
10、的思维活动相接近。因此可通过日常生活中的例子5来帮助学生理解递归程序设计思想。 比如，任何一个组织都是一个层次的结构，考虑一个由处于顶级的组织领导，处于中层的部门经理和处于底层的职员构成的三层组织结构。组织事务的处理步骤一般为处于顶层的组织领导将顶层事务分解，传递给各个部门领导；各个部门领导进一步把任务分摊到在每个职员上；若每个职员所处理的事情外部条件均具备，则职员任务得以解决；若所有职员的事务得以解决，则该部门的事务得以解决；若所有部门的事务得以解决，则该组织的顶级事务得以完成。其中体现的是问题分解的过程；而体现的则是问题由简单到复杂渐次求解问题。 又比如，人们处置复杂事务，从中理清事务线索
11、的过程也蕴含着递归程序思想，设A, C, D, E, H, M, G为复合事件，a, c为原子事件，G为求解目标，其中符号“?酆”表示为事件依赖关系，符号“?刍”表示事件的决定关系。其中复合事件表示为依赖于其他事件的事件，原子事件为不依赖于其他事件且单步可解的事件。若事件的依赖关系满足，为达成G，则人们理清的事务分解线索为。由于a可解，则A,C可解；由于c可解，则E可解；由于a, c可解，则D可解；由于A,C可解，则H可解；由于D, E可解，则M可解；由于H, M可解，则最终问题G最终求解。以下是事务G的求解线索 通过以上例子，可使学生了解递归的基本概念并初步建立起递归程序的设计思想，在此基础
12、上，进而可通过实际的教学案例来帮助学生正确理解递归程序递推公式和递归之间存在何种联系，不预留低阶简单问题出口可能带来的后果；递归的执行线索和递归和循环之间的联系以及递归程序的表示效率和执行效率。 在教学中，可将Fibonacci数列作为教学案例，原因Fibonacci数列有两个初始值，其数列的递推公式是由前两项导出后一项，相对于一般教材所广为采用的教学案例高阶阶乘计算3,6-7和自然数累计5更具代表性和一般性。 Fibonacci数列的初始值为a1=1, a2=2且满足递推公式an=an-1+an-2(n3)，求取Fibonacci数列的第n项可以很好地借助递归思想进行表达，如图1所示。 在图
13、1所给出的程序代码中，第1行第2行伪码用于返回Fibonacci数列的第1项和第2项，即当问题的求解规模降低到最低时弹出栈顶元素的过程，为低阶最简问题预留出口；第3行第4行伪码用于当n3，将Fibonacci数列的第n项的计算结果降为第n-1和第n-2项，即将复杂问题不断地简化，表现为不断地压栈的过程。为使学生有更直观的印象，可通过算例求Fibonacci序列第5项元素得值，给出Fibonacci序列元素具体的执行线索，如图2所示。 图2给出了求解Fibonacci序列第5项元素值的求解线索，其中实线箭头对应为图1中的第3行第4行伪码，为不断堆栈的过程，虚线箭头对应为图1中的第1行第2行伪码，
14、为不断出栈的过程。若在代码1中删去第1行第2行伪码，则表现为实线箭头的不断增加和不断地推栈，从而程序耗尽系统资源，导致系统崩溃和程序推栈异常。 此时，作为对比，可给出非递归的Fibonacci序列伪码，从而让学生形成递归算法的表示效率和计算效率的直观印象。基于非递归的Fibonacci数列的第n项伪码如图3所示。 在图3所给出的程序代码中，第1行第2行伪码用于变量初始化和赋值，第3行第7行通过循环计算Fibonacci数列的第n项，并更新递推公式，具体为按递推公式的前两项计算后1项，每新计算出1项，即顺次后移1项对递推公式进行更新并计算新项，从而使Fibonacci数列的第n项得以解决。以下以
15、Fibonacci_N(5)为算例，给出具体的执行线索，如图4所示。 通过对比递归和非递归Fibonacci数列第n项程序伪码（图1和图3）和递归和非递归Fibonacci数列执行线索（图2和图4），可使学生形成直观的印象并理解递归背后暗含的规律递归程序描述相对于非递归程序描述更为简洁直观；递归程序简单直观的背后蕴含着执行路线的复杂性；递归程序蕴含着复杂到简单，再有简单到复杂的渐次求解过程，其中的简单到复杂的渐次求解过程可等价于一个循环过程；相对于非递归算法，递归算法的执行效率相对较低。 至此可帮助学生掌握递归程序设计的基本方法寻找待求解问题高阶问题同低阶问题之间的关系，从而可将问题简化；给出
16、简化问题的求解方法，当问题化简到最简单时，问题可以求解。 2 巧妙设局，层层引入，从多方面多角度训练和培养学生的递归程序思维 以上课堂引导，虽能使学生正确理解递归程序设计思想并使学生初步掌握递归程序设计的基本方法，但离实际灵活运用还相距一定距离。在实践中，笔者也发现尽管学生貌似理解了递归程序设计思想，也基本掌握了递归程序设计方法，但遇到具体的问题时，依然不知何从分析，难以入手。 为从多方面训练和培养学生的递归程序思维，笔者在实际教学中，营造了多个趣味案例，通过巧妙设局和层层引入的方法来实际锻炼和培养学生的递归程序思维，促其主动思考，在实际中取得了较好的教学实施效果。以下仅举几例，对其进行简要分
17、析并给出具体的问题求解思路。 教学案例1分数序列求和问题有一分数序列2/1, 3/2, 5/3, 8/5, 13/8, 21/13,，用递归算法求出该分数序列的前n项之和。 教学案例1分析将该分数序列的分子和分母构成一个数列 ，发现其规律为a1=1,a2=2且an=an-1+an-2(n3)，由此可按前面Fibonacci数列的方法递归求an；设该分数序列满足的数列为bn，则有bn=an+1/an，此时可通过将该式封装为函数计算bn；设数列bn前n项的和Sn，则有Sn=Sn-1+bn(n2)，此时可建立起Sn和Sn-1之间的递推关系，当Sn简化到最简时，有S1-b1。基于此思路 ，可实现Sn的
18、计算。其中设局是为了检测学生的学习情况，设局是为检验学生实际运用递归程序解决实际问题的能力。以下给出具体的分数序列问题递归程序伪码如图5所示。 在图5中，第1行第7行伪码用于计算数列an；第8行用于计算bn；第9行第13行伪码用于计算Sn。其中，第1行第4行伪码返回 的前两项a1=1,a2=2；第5行第6行伪码用于将an的求解规模降为an-1和an-2；第9行第10行伪码返回S1，第11行第13行将Sn的求解规模转为Sn-1和bn。在实际教学中，笔者还进一步设局促进学生独立思考来实际提升和培养学生的编程思维能力让学生分析图5代码的执行线索和效率；让学生对图5的递归程序伪码进行优化；让学生写出对
19、应的非递归算法；让学生将优化后的递归算法和非递归算法的执行效率进行对比分析来实际探求递归程序的效率和本质。 教学案例2猴子吃桃问题一个猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个；第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下桃子数量的一半零一个。到第n天早上想再吃时，见只剩下一个桃子。求第一天共摘了多少个桃子。请用递归算法编程实现。 教学案例2分析采用逆向思维，将猴子每天吃下的桃子数量逆置作为一个数列Pn，且P1=1；由每天早上都吃了前一天剩下桃子数量的一半零一个，则有Pn-1=pn/2-1(n2)，即Pn=2(pn-1+1)( n2)。由则可
20、给出猴子吃桃问题的递归算法。其中，设局主要锻炼学生的逆向思维和简化问题模型的能力，设局则重点考查学生是否清晰递归的概念，明确递归问题的求解方向。以下给出具体的猴子吃桃问题递归程序伪码，如图6所示。 在图6中，第1行第2行伪码返回 数列第1项作为结果，预留出口，即最后1天只剩1个桃子；第3行第4行伪码将待求解问题的规模由n将为n-1，即将n天前的桃子数推到n-1天前。在实际授课过程中，笔者还对猴子吃桃问题进一步扩展进行设局来对学生的递归程序思维进行训练和培养，例如猴子每天吃掉的桃子比例不再局限于1/2；猴子每天多吃的桃子数也不再局限于1个。 教学案例3企业奖金利润提成问题某企业规定其企业的利润提
21、成方案为，当利润小于等于10万元时，奖金可提10%；利润在10万元到20万元（含20万元）之间时，利润中10万元部分按前一级处理，高于10万元的部分，可提成7.5%；利润在20万到40万元（含40万元）之间时，利润中的20万元部分的按前一级处理，高于20万元的部分，可提成5%；利润在40万元到60万元（含60万元）之间时，利润中的40万元部分按前一级处理，高于40万元的部分，可提成3%；利润在60万元到100万元（含100万元）之间时，利润中的60万元部分按前一级处理，高于60万元的部分，可提成1.5%；高于100万元时，利润中的100万元部分按前一级处理，超过100万元的部分按1%提成。请用
22、递归算法编程实现。 教学案例3分析在企业奖金利润提成问题中，总共有6个利润提成级 money10, 10money20, 20money40, 40money60, 60money100和money100，决定了程序的6条执行线索，其中money为企业收益； money10为最简单，money100为最复杂，由此可确定递归的执行线索；除了money10，其余级和前一级都能构成递推关系，例如money100的提成和money=100的提成存在递推关系，money=100的提成依赖于money=60的提成，然后依赖于money=40的提成，进而依赖于money=20并最终取决于money=10，由
23、此可将提成的高阶问题和提成的低阶问题联系在一起。以下给出具体的企业奖金利润提成问题递归程序伪码，如图7所示。 在图7中，第1行第2行伪码为当利润小于10万时，直接返回提成，留好出口；第3行第4行伪码为当利润在10万与20万之间时，利用递推公式将利润提成转嫁为10万的情况；第5行第6行伪码，为当利润在20万与40万之间时，利用递推公式将利润提成转嫁为20万的情况；第7行第8行伪码，为当利润在40万与60万之间时，利用递推公式将利润提成转嫁为40万的情况；第9行第10行伪码，为当利润在60万与100万之间时，利用递推公式将利润提成转嫁为60万的情况；第11行第12行伪码为当利润大于100万时，利用
24、递推公式将利润提成转嫁为100万的情况。教学案例3相对于教学案例1和教学案例2更贴近学生的实际生活，更为综合和具体。对教学案例3的进一步设局，还可解决贴近人们日常生活的银行多阶段调息计算问题，电费运营调整的计费问题，职务升迁的薪水计算问题等。设局教学案例3的目的，是通过实际的例子来锻炼和培养学生的递归程序设计思维并进一步让学生深深地体会出递归程序设计思想的魅力所在，让学生体会出一个复杂的实际例子可借助递归思想进行简练的表达和描述。 以上教学案例的实施，从多方面检验了学生对递归程序设计思想的掌握情况，并从多角度训练和培养了学生的递归程序思维。通过学生先独立思考再反馈式讲解，取得了较好的教学实施效
25、果，实践表明通过实施以上教学案例并巧妙设局和层层引入，使学生普遍接受了递归程序设计思想并自觉运用递归程序设计思想来解决实际问题。 3 结论 递归程序设计思想是计算机编程思维分治思想的典型代表，在程序语言教学中处于重要地位，也是历来进行程序语言教学和考核学生的难点。递归程序设计思想难于接受在于其抽象性和简练背后蕴含的复杂性。 该文则结合笔者近年来从事程序语言教学所获取的教学经验，给出了笔者的教学实践。从递归程序设计思想的教学目标出发，通过人类日常生活中耳熟能详的例子层次型组织结构处置事务的方式和人们处置复杂事务理清事务线索的过程中引出递归程序设计思想所蕴含的人类思维方式，从而引导学生正确理解递归程序思想并初步掌握递归程序设计的基本方法，在此基础上构造趣味教学案例，巧妙设局，层层引入，从多方面多角度训练和培养学生的递归程序思维，并对所构造的教学案例其进行简要分析并给出具体的问题求解思路。实践表明以上教学手段的有效实施取得了较好的实施效果，可使学生普遍地接受递归程序设计思想并自觉运用递归程序设计方法来解决实际问题。 第 15 页