数据结构中递归算法的教学要点及方法探讨
开篇：润墨网以专业的文秘视角，为您筛选了一篇数据结构中递归算法的教学要点及方法探讨范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：学生对递归算法的理解和掌握程度影响着对数据结构及后续课程的学习效果，提出在数据结构课程中应补充递归思想和算法实现的教学，探讨了教学要点和教学方法，并设计合理的实验教学方案。实践证明教改后取得了良好的教学效果。
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）04-0784-04
数据结构课程教学内容中无论是概念的描述还是算法的设计，都广泛使用了递归的思想。以严蔚敏的数据结构教材[1]为例，在概念的描述上，广义表、二叉树、树的定义都使用了递归的形式；在算法设计上，二叉树的先序、中序和后序遍历、二叉树的构造、树的先根和后根遍历、图的深度优先搜索、二叉排序树上的查找以及排序算法中的快速排序和递归排序均使用了递归的方法。
数据结构和递归思想密不可分，学生对递归算法的理解和掌握程度影响着对数据结构及后续课程的学习效果，因此教学工作者们对递归算法的教学方法做了大量探索和研究。文献[2]指出应提前引入简单问题递归算法的讲解，为后续复杂问题的递归算法教学铺平道路，并给出线性表上递归算法的教学示例。文献[3]指出学生由于不清楚递归函数的执行过程影响了对递归算法的理解，举例使用图示法解析了函数调用过程中栈的变化和递归函数的执行过程。文[4]强调在教学过程中应先讲解学生容易理解的数值型递归问题，再讨论非数值型递归问题。文献[5，6]给出了包括递归模型、递归原理、递归程序的阅读和递归程序的设计四个环节的教学过程。该文以武汉科技大学信息与计算科学系为例，分析在数据结构递归相关内容的教学环节中常遇到的问题，提出在数据结构教学中应补充对递归思想和算法实现的讲授与实验安排，教学过程应由浅入深、由表及里、提前引入、贯穿始终，探讨了递归算法编写思路、运行机制和使用场合的教学方法，并设计相应的实验教学方案。
1 数据结构递归算法教学中存在的问题
1）从课堂教学的学生反应来看，学生对使用递归方式描述的概念进行正确理解通常问题不大；但数据结构中使用递归算法解决的问题大多比较复杂，学生对这些递归算法的阅读依然感到吃力，这些算法中的递归策略影响了学生对算法问题本身的理解；
2）在用到递归算法的实验中常有学生表示对递归算法能够实现预期功能感到不可思议；
3）在需要自行编写递归算法求解问题时常有学生不知如何下手。
2 递归算法及实现的教学要点
学生在前导课程高级程序设计语言的学习中曾经接触过几个递归算法，但学生只有粗略印象并没有深入学习。在广泛使用的严蔚敏的数据结构教材[1]中，“栈与递归的实现”为选讲内容，根据多年教学经验来看，如果教学过程越过该内容，后续出现的一系列递归算法往往常成为教学过程中的绊脚石，因此有必要安排专门的课时对递归算法的编写思路、运行机制展开讲解，并辅以必要的实验练习用于巩固。
虽然递归算法形式简洁，但对初学者来说由于递归算法在执行过程中会层层调用自身且执行过程不直观，使初学者对递归算法的执行过程感到困惑不解。依据教学经验来看，如果直接向学生讲解递归算法执行过程，以及系统在代码背后完成的一系列工作诸如开辟递归工作栈等常使得学生对递归算法感到高深莫测和枯燥乏味。如果先引导学生观摩递归算法的经典实例并传授递归算法编写的思路，使学生对递归算法先有个感性认识且能够对新的问题进行分析并自行编写出递归算法，则可以为学生建立信心并产生对递归算法进一步探索的兴趣；然后再引导学生洞悉递归算法执行的内部机制，从而达到知其然且知其所以然。因此将递归算法的教学过程分为三个步骤：1）传授递归算法的编写思路；2）洞悉递归算法的实现机制；3）分析递归算法的使用场合。
2.1 递归算法的编写思路
递归是一种分析和解决问题的方法和思想，从形式上来看它是函数直接或间接地调用自己。当待解决的问题满足以下两个条件，则可用递归方法求解：1）问题可以分解为规模更小但与原问题性质相同的子问题；2）具备递归终止条件。下面直接通过例子来学习递归算法的编写方法。
例1：计算n阶乘，其中n为非负整数。
算法思路：由于5！=5×4×3×2×1， 4！=4×3×2×1，可以推得n！=n×（n-1）！。其中求解（n-1）！与（n）！是性质相同的问题，但规模变小了；且0！=1，1！=1，它们构成了递归调用的终止条件。故n阶乘问题可以用递归算法求解，如下所示：
int Fac（int n）{
if （n==0||n==1）
return 1；
else
return n*Fac（n-1）；
}
例2：逆序输出单链表。已知单链表不带头结点，结点的存储结构定义为
typedef struct Node{
int data；
struct Node *next；
}Node；
算法思路：逆序输出整个单链表，可以考虑先逆序输出后n-1个元素，再输出第一个元素。其中逆序输出后n-1个元素与原问题是性质相同的问题，且规模更小；若单链表为空，则为空操作，它构成了递归调用的终止条件。故逆序输出单链表可以用递归算法求解，如下所示：
void RevPrint（Node *p）{
if （p）{
RevPrint（pnext）；
printf（"%d "，pdata）；
}
}
2.2 递归算法的实现机制
2.2.1 递归算法的调用流程
递归算法形式简洁但执行过程并不直观，使得初学者对递归调用的流程理解困难，尤其对函数调用和返回的对象与时机容易理解错误。递归调用流程的讲解通常可以采用动态演示法或者是图示法。动态演示法利用程序调试工具通过设置断点和单步执行等手段来展现算法执行的各个步骤，但由于程序执行细节过多，学生如果在某一个环节没有跟上，就很难对整个执行过程理解到位。因此对递归调用流程的讲解更推荐采用图示法。
如图1所示，演示了n阶乘递归算法的调用流程，使用递归算法求解3阶乘。图中实线代表递归调用，实线的起始端对应函数调用语句，箭头端代表进入被调用的函数体；虚线代表被调用函数执行完毕并返回至调用语句处；实线和虚线上的编号代表函数调用和返回的次序。代码左侧序号为语句行号。由图示可知，递归调用遵循先调用后返回的特点，且最后一次调用满足递归的终止条件，使得程序不会无限制的递归下去。
图1 3阶乘的递归调用流程
2.2.2 递归工作栈
当学生弄清楚递归调用的流程、自己也可以动手编写递归程序以后，自然会进一步思索递归程序表面看起来井井有序的调用工作到底是怎样实现的，这便是该引出递归工作栈的时候了。首先介绍普通函数调用期间系统所做工作，再引出递归调用时系统完成的工作，并以阶乘的递归算法为例形象展示递归调用期间系统协助完成的工作。通过该部分的讲解可以排除学生对递归调用的神秘感。
1）普通函数调用
程序运行期间发生函数调用时系统需要为其分配存储空间，用于保存外层函数的实参和返回地址、内层函数的局部变量等；调用函数执行期间，则该存储区保存的局部变量参与运算；调用函数执行完毕时，则根据该存储空间保存的返回地址返回到被调用函数，并释放该存储空间。当多个函数嵌套调用时，需要按照“后调用先返回”的原则保证程序逻辑的完备，为实现这一原则系统通常采用“栈”结构来实现前述存储空间的分配。具体来讲，系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当一个函数退出时，就释放它的存储区，栈顶总是存放当前正运行的函数的相关信息。
2）递归函数调用
递归函数调用和普通函数调用本质上并没有区别，只不过每次调用的是同一个函数体而已。为区分各次调用，调用递归函数的主函数称为第0层，则从主函数调用递归函数称为进入第1层；从第i层递归调用递归函数称为进入第i+1层。通常把递归函数运行期间使用的数据存储区称作递归工作栈，每一次递归调用会产生一条“工作记录”，包含调用时所需要的实参、局部变量和返回地址。每进入一层递归调用，就产生一条新的工作记录压入栈顶，每退出一层递归，就从栈顶弹出一条工作记录[1]，并按所保存的返回地址进行返回，从而实现了递归程序最后调用最先返回的特性。由此可知，在每一层的调用过程中，系统为新调用的函数所用到的局部变量开辟新的的存储空间，每次调用所使用的局部变量在不同的存储空间。
3）递归工作栈示例
如表1所示，以3阶乘的递归求解为例演示了递归工作栈的状态变化。递归工作栈中的工作记录包括被调用函数的返回地址和调用函数的局部变量，其中返回地址使用程序语句所在行号表示，并假设主函数的返回地址为0，程序语句所在行号详见图1。
2.3 递归算法的使用场合
通过前面的学习，学生将感受到使用递归的思想解决问题可以使求解思路简单清晰，而且编写出的代码精简易读，递归层层调用和返回的工作交给系统完成就可以了。那么满足递归两个条件的问题是否都应该使用递归算法来求解呢？要回答这个问题，则需要从函数调用的代价来考虑。
由上节讨论可知发生函数调用时系统需要保存当前的调用现场，为其分配存储空间，调用函数执行完毕时需要返回被调用处并释放该存储空间，因此函数调用的过程既浪费系统存储空间，还消耗系统处理的时间。递归算法通常需要进行多次的函数调用，因此递归算法会浪费很多时间在函数调用的处理上。当递归层次较深时，甚至可能造成栈溢出的问题。
那么对于同一个问题如果既可以使用递归算法求解，又可以使用迭代算法求解 ，例如n阶乘问题，尽管递归可以简化求解思路，但空间和时间上的开销却更大，此时我们更倾向于选择使用迭代方法求解。当然，有些问题使用迭代算法很难甚至解决不了，例如经典的汉诺塔问题，这时我们就必须求助于递归算法了。
3 递归算法实验内容设置
单纯依靠课堂的讲授不足以使学生熟练掌握递归思想的使用方法，仍然需要依靠实验练习来加深学生对递归的理解、巩固递归算法的编写和调试方法。实验教学内容的合理设置和精心安排更有利于学生建立学习的信心，并体会到征服困难与不断进步的成就感。因此，我们采用由易到难、由浅入深的方法将递归算法的训练贯穿于整个数据结构的教学过程中。
以严蔚敏的数据结构教材[1]为例，从第六章“树和二叉树”开始，学生将陆续接触到一系列复杂问题的递归算法，所以有必要在第六章教学之前就安排递归算法的讲解与实验练习，通过比较简单的递归问题使学生掌握使用递归思想分析问题的方法和递归算法的编写模式，从而为后续复杂问题的递归算法教学铺平道路，这部分实验称为预备型实验。在后续教学的过程中，复杂问题递归算法的实验则根据相应章节的教学进度进行安排，这部分实验分为设计型和验证型两种。其中，验证型实验学生可以参考课本提供的算法，而设计型实验则完全靠自己进行分析设计和算法实现。数据结构课程中递归相关内容的实验安排如表2所示。
4 结束语
在以往的教学中，发现数据结构中算法的递归策略影响了学生对算法问题本身的理解，因此在数据结构教学改革中增加了对递归思想和算法实现的讲授与实验安排，讲授部分包括递归算法的编写方法、运行机制与应用场合分析，实验安排则将递归算法的训练贯穿于整个课程的教学过程中由易到难地展开。通过对教学改革后学生上课、实验及考试情况的观察，学生在递归算法上犯错的比例比以往有很大程度的降低，递归算法不再是数据结构学习中的绊脚石，学生对数据结构的学习更加轻松和自信。
参考文献：
[1] 严蔚敏，吴伟民.数据结构（C语言版） [M].北京：清华大学出版社，1997.
[2] 唐自立.数据结构课程中递归算法教学探讨[J]. 中国科技信息，2006（8）：290-291.
[3] 牛小飞， 李盛恩， 张冬梅，等.关于数据结构中递归的教学探讨[J]. 山东建筑大学学报，2010，25（6）：656-661.
[4] 王慧娇.程序设计中递归函数教学问题探究[J]. 计算机教育，2010（16）：59-62.
[5] 郭韶升，张炜.数据结构中递归算法的研究与实现[J].机械管理开发，2007（6）：90-91.
[6] 张永梅，马礼.程序设计中的递归算法教学探讨[J].华北工学院学报，2001（3）：38-39.