基于与递推算法对比的递归教学方法思考

马晓丹 王忠 范青刚 陈菁

摘 要 为了培养学生思考能力，计算思维能力，在算法的学习中运用知识的正迁移。在课堂教学中进行了同一问题不同算法解法的对比尝试，有效提高了课堂教学效率。本文从两种算法的程序结构、终止条件、算法效率等方面系统进行了比较，以结合课程内容和学生的知识积累为基础，循序渐进积极引导学生思考，从而培养学生的学习兴趣，发挥学生学习的主动性，提高学生自主地发现问题、研究问题和解决问题的能力。

关键词 递推 递归 算法对比 正迁徙

Abstract In order to improve students' thinking ability， computing thinking ability， the positive transfer of knowledge is used in the learning of algorithms. In the classroom teaching， we tried to compare different algorithms and solutions of the same problem， which effectively improved the efficiency of classroom teaching. This paper systematically compares the algorithm structure， termination conditions， and algorithm efficiency of the two algorithms. Based on the combination of the curriculum content and the student's knowledge accumulation， actively guides students think step by step， cultivating students' learning interest and giving full play to their learning .Initiative to improve students' ability to discover， research and solve problems autonomously.

Keywords inductive; recursion; algorithm comparison; positive migration

1 问题提出

在程序基础编程实现中，递归与递推是两种最为基础和常见的算法。而在程序基础的教学中，常常听到学生说计算机编程语言理解吃力，无法有效的对常用的这两种算法进行掌握、区分和应用。而学生们感到程序基礎这门课难也主要是因为涉及的基本算法思想比较抽象，对于刚接触计算机的人来说不易形象化的内化理解。概念不清晰，知识点理解分离孤立，不好理解。

在教育心理学中的重要概念正迁移，是指一种学习对另一种学习起到积极的促进作用。知识迁移的能力是指将所学知识应用到其它新的情景下，并解决新问题时所体现出的一种素质和能力，包含对新情境的感知和处理能力、旧知识与新情境的链按能力、对新问题的认知和解决能力等层次。形成知识的有效的迁移能力可以避免对知识的死记硬背，实现知识点之间的贯通理解和转换，有利于认识事件的本质和规律，构建知识结构网络，提高解决问题的灵活性和有效性。正迁移， 通常表现为：（1）一种学习使另一种学习具有了良好的心理准备状态、活动所需的时间或练习次数减少。（2）使另一种学习的深度增加、单位时间内的学习量增加。（3）已经具有的知识经验使学习者顺利地解决了面临的问题等情况。[1]

在递归函数的教学中可以采用从数学归纳法到函数递归的思路，并对同一问题进行函数封装递推算法到递归解法，在执行中对比两种算法的异同优缺点的方法，有效进行递归知识点的掌握和学习。

2 基于与递推算法对比的递归教学设计

2.1 基于递推算法的函数定义

在循环和函数概念的基础上，让学生编写一个函数，求第n项斐波那契数列。目的一是巩固和加强对循环递推算法的理解，二是巩固加强对函数定义的巩固和应用，采用循环递推的方法解决的C语言代码如下：

设置课堂讨论环节，讨论循环体内的三个语句顺序是否可以调换f3=f1+f2;f1=f2;f2=f3;得到的讨论结果为递推算法的本质是根据已知数列的前面，使用递推公式以此类推得到后面数值项。与数学中的递推公式思想一致。抛出新的问题：题目同样可以使是否可以用数学归纳法的方式解决？数学归纳法：用于证明断言对所有自然数成立。

证明过程：

证明对于N=1成立

证明N>1时：假设对于N-1成立，那么对于N成立。

2.2 递归概念的引出

不同于数学归纳法的是，递归是计算机领域关于函数的特有概念，指的是函数对于自身的直接或者间接调用，就像Photoshop中的罗斯福效果：镜子与镜子对照出来的无限空间，也似盗梦空间中表示的多层梦境一样。如此循环往复，但根据算法的有限性的特点，递归算法需要一个边界条件，使得循环在某个条件满足的时候，返回一个终值。这种方法通常能把一个大规模的复杂的问题转化为一个与原问题相似的小规模问题来解决，以此来极大的提高代码的可读性并减少程序代码量。可以给出斐波那契数列的递归形式表达式：

进而写出斐波那契数列的递归函数：

2.3 递推与递归算法的对比

类似的对比例子还可以求n！、前n项和等，完成之后对比两个代码，让学生讨论和比较两种算法的异同，同时执行两种算法的代码，感受和对比执行的效率。总结如下：

递推主要指递推公式、递推数列或递推函数。一个数列的下一项由它前面几项的一种运算（或函数）构成，如a[n]=a[n-1]+2、a[n]=a[n-1]+a[n-2]等。

递归主要指计算机上的递归函数，即会调用自己的一段函数代码。

递归与迭代都是以控制结构为基础的：迭代直接在代码形式上使用了循环结构实现以此类推”，而递归直接使用了选择结构，进行边界条件的判断和本函数的调用。

递归与迭代的本质都是重复：迭代显式使用重复结构，而递归通过函数调用实现重复。

递归与迭代也都有终止条件的判断：迭代在循环条件失败时停止循环操作，递归在遇到边界条件返回终值。[2]

总的来说进行程序设计时，递归算法的最大优点是程序结构清晰，可读性强，当我们把问题写成递归形式的数学的表达式之后，与代码有着极高的相似度。因此在实际使用中是一种常用的算法设计，尤其是在许多现实复杂的问题中，想要找到从初始条件开始一一推出所需结果的过程很难的时候，使用递归算法实现问题解决要简单的多。而随之而来的缺点便是，递归算法在不同的调用阶段会重复执行同一个函数的计算，算法复杂度是指数级的，并且每一次的函数调用都要栈来实现不同调用阶段的数据保存，频繁的出栈和入栈使的空间消耗也是极大的。当问题规模稍微大一些的时候，递归深度甚至超出可接受限度，（在Python中递归的嵌套深度不能超过998，当调用栈超过998层就会报错）。

而同样的问题对于设计良好的非递归算法的执行效率就高得多，因此在问题解决之后也应激励学生进一步的鉆研和讨论如何将递归算法进行非递归化以进一步的优化算法设计，提高代码质量。

2.4 递归算法的应用扩展

归纳总结可知递归算法是由递归出口和递归转移函数构成的（类似于动态规划中的状态转移方程）。一般递归算法框架为：

返回值函数名（形参列表）{ if （出口条件） return 返回值else { 根据状态转移方程递归调用自身return 返回值}怎么判断问题可以使用递归来解决的？

问题可用递归来解决需具备的条件：子问题需与原问题为同样的事，且规模更小;程序停止条件。并以经典的汉诺塔问题和其他问题作为练习，巩固对递归算法的理解和应用。

3 结束语

在教学过程中，很多学生不能实现从数学思维到计算思维进行转换，递推到递归的思维转换的困难，因此在计算机程序设计和求解过程中面对类似实际问题描述的时候没有思绪，无从下手，概念混淆，胡编乱造。这提示我们解决程序逻辑思维混乱的方法之一便是在平时的程序设计学习中以熟悉的数学知识概念为基础，理清思绪。促进知识正迁移，弱化或者克服知识负迁移。并且通过两种算法的多方面对比加深学生对不同算法的理解和认识，通过同时运行两个程序感受运行时间的差异，激发学生对算法评价指标的理解和重视，获得良好的教学效果。

参考文献

[1] 皮连生.学与教的心理学（第四版）.上海：华东师范大学出版社，2006.

[2] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1997.12：141.