高中《算法与程序设计》中的递归算法

《算法与程序设计》是高中信息技术中重要的选修课之一。课程中涉及多种算法，比如：解析法、穷举法、递归法等，其中递归法教师最难讲解，学生也最不容易理解，很多师生对递归法望而却步。在此，笔者结合自己的上课实践与大家共同探讨递归算法的教学。

一、明确教学目标

新课标指出：“算法部分旨在使学生进一步体验算法思想，了解算法在解决问题过程中的地位和作用，并能从简单问题出发，设计解决问题的算法。”递归算法的教学目标是学会用递归算法的思想分析问题。为了实现该目标，很多教师从递归函数代码的理解出发带领学生学习递归算法，而代码的反复调用很容易给学生理解造成困难。笔者认为指导学生利用递归思想来分析问题是最重要的，理解了递归思想以后，代码的编写就变得相对容易了。

二、学生知识准备

所有的知识都不是空中楼阁，必须有一定的前期知识准备。学生开始学习递归算法前应该已经熟练掌握了顺序结构、分支结构、循环结构，对程序设计语言有了一定的了解，能解决一些有一定难度的程序，有一定的分析问题的能力。而且，学生应该已经掌握了自定义函数，包括函数名、函数参数、函数参数之间的传递等知识。

三、理解递归过程

兴趣是最好的老师，越难理解的知识点越需要抓住学生的兴趣点。对于递归算法的学习，我们可以先让学生玩“汉诺塔”游戏。让他们把塔盘从少到多慢慢增加，一边玩一边总结游戏攻略。通过老师的引导及动画课件，学生应该可以总结出“N个塔盘从A移动到C”的问题可以转换成三个小问题：1.把N-1个塔盘从A移动到B；2.把第N个塔盘从A移动到C；3.把N-1个塔盘从B移动到C。教师只要适时地加以总结：“要想解决复杂问题，可以先把复杂问题转化成简单问题，把问题化解到最小，简单问题解决了，那复杂问题也随之解决。”并给出递归算法的概念：“直接或间接调用本身的算法”，以及递归算法的核心思想：递归分为两个部分，一是递推：大事化小；二是回归：由小及大。当然，教师也可以用“从前有座山”这个大家耳熟能详的故事加以补充说明。

四、把握分析思路

在学生初步了解递归思想后，教师不应急着进入代码的讲解，可以引导学生用递归思想来分析问题，从简单到复杂，从具体到一般。可以从分析求5！开始，分析并总结出求N！的方法。在讲解的过程中，教师可以借助黑板来板书分析思路。（如图）

当分析完5！的求解过程以后，教师可以让学生分析讨论出数学模型，其中包括：递归公式和边界条件

这是一个典型的双分支选择结构语句，可以用IF语句来实现。

五、结合分析完成代码

在学生分析透彻以后，可以让学生试着根据以往的函数知识完成代码的编写。这时可以利用“半成品”的形式，主要是让学生填写递归函数的主体（判断语句）。然后，教师结合代码再次说出递归的过程，学生的印象就很深刻了。这里学生可能会在两个地方出错：1.写成fac（n）=fac（n-1）*n，解释：函数的调用只能在表达式中，而等号是赋值语句，左边只能是变量而不能是表达式。2.函数数据类型和接受返回值的变量数据类型不符，解释：赋值语句等号左右两边数据类型必须相同。

六、适时巩固知识

N！数学模型讨论出以后，学生和教师一起经历了问题分析的过程。这时教师可以适当小结递归概念、递归核心思想、递归边界条件，来帮助学生巩固所学知识。

然后，学生可以用斐波那契数列来进行练习。之所以用斐波那契数列来练习，是因为这个数列学生能很快找到规律，但又因为有两处调用，有一定的难度提高。

当然还是采用从具体到一般的方法，先在学案上分析第5项的数的求法，同时请两位学生到黑板上来分析。再根据分析讨论出递归公式和边界条件（右图为笔者上课时学生书写的学案）。对这道题目的板书分析，以后在总结递归的缺点（重复调用）时也是可以利用的。

七、适当提高应用

在信息技术学科中，学生的能力存在较大差异。而递归算法又在理解上有一定的难度，自然学生达到学习目标的情况也会有所差异。英国现代教育学家沛·西能在《教育原理》中说：“一切教育努力的根本目的应该是帮助学生尽可能达到最高的个人发展。”所以，分层教学在信息技术中会经常运用到。本课内容可以采用难度稍高一点的递归题目作为提高题。笔者在教学的时候采用的是小球自由落体作为分层教学中的提高部分，同时采用小组讨论的形式完成该题的分析。有些教师会让学生编写“汉诺塔”程序，笔者觉得难度太大，会把学生难住，造成学生产生排斥心理。

总之，递归法的教学重点必须落在“算法”上而不是“代码”上。只要学生会用递归算法分析问题，那递归算法的代码就很容易写出来。而只有当学生会用算法的思想分析问题，他们才能真正地体验到算法的魅力，进而爱上《算法与程序设计》这门课。

参考文献：

[1]算法与程序设计.教育科学出版社.

[2]数据结构与算法.天津大学出版社.