对递归算法进行“分类探讨”的教学方法研究

范昊　束德勤

摘要：递归算法或者递归程序是计算机及相关专业高校学生，在大学学习阶段必须掌握的一种程序设计方法。文章首先分析了高校学生在学习递归算法时遇到的难点，然后将递归算法进行不同角度的分类，由易到难详细剖析递归算法的设计思路，最后对递归程序的设计过程进行讲解和总结。文中还结合了实际教学案例，给出了递归算法的讲解和设计过程。

关键词：递归算法;典型案例;递归程序框架;算法分类

中图分类号：G642.0     文献标志码：A     文章编号：1674-9324（2020）16-0195-02

一、引言

计算机及相关专业在大学本专科的学习过程中，不可避免地要接触到递归程序的设计[1]。递归算法的概念和设计技巧，贯穿于计算机及相关专业本科学习的各个阶段。递归思想也在程序设计、算法分析甚至数学课程中有所应用。递归不是一门专门的课程，更不是专门的一个学科，而是一种思想、一种思路，在大学中的各门课程中都有它的身影，甚至在我们的生活中也处处可见。但很多学生一直感觉递归程序是一个难点问题，甚至对递归程序的执行过程掌握得都不是很清楚[2，3]。针对这些问题，本文详细分析和讲解递归的执行过程和递归程序的设计技巧。对递归程序设计过程中的各种情况进行详细的分类探讨，使得教师在讲解时有的放矢，学生们在理解时层层深入，对递归的本质有更深入的了解。

二、递归问题的本质

1.递归算法的基本概念。递归程序（recursion algorithm）在计算机科学中指的是一种通过重复求解子问题，将问题分解为同类的更小问题而解决原始问题的设计方法[4]。递归算法可以被应用以解决很多计算机科学中的实际问题甚至是生活中息息相关的问题，因此它不仅仅是计算机学科中的一个基本概念，更多的是一种计算思维和解决问题的思路。很多程序设计语言支持函数的直接调用自身或者间接调用自身，在一些语言中，如C、C++、Java等程序设计语言，函数或者子程序可以通过调用自身来进行递归。

2.递归程序的特点。其实，简单来说，递归算法的本质是把原始问题归结为规模更小的同类问题的子问题，子问题再分解为更小子问题，直到最小子问题直接得到答案，或者非常容易解决，然后层层返回，得到原问题的解。递归的基本特点为：（1）每一级的函数调用自己有的参数或者变量，当然变量有局部变量和全局变量。（2）每一次函数自身调用都会有返回，不一定立即返回，有时是多层调用后返回，有时是循环中返回。（3）递归函数中，递归调用前程序语句和各级被调用子程序或者循环中调用的子程序具有同样的执行方式。（4）递归程序中，位于递归子程序调用后的语句，其执行顺序和各个被调用子程序的执行顺序相反。

3.递归程序设计的要点。第一要点：明确这个程序想要解决什么问题。姑且不管子程序里面的代码是什么，首先要明确正在设计的程序的功能是什么，要完成什么工作。第二要点：合理设计递归结束条件。需要设计者找出条件为什么时，可能是变量值，也可能是函数的参数是多少时，递归结束，然后递归程序直接返回结果。第三要点：找出程序的递推关系算式。设计者不断缩小参数的范围，把原问题不断缩小，使程序中的递推关系保持不变。

三、递归算法的分类

在教学的课堂讲授阶段，教师可以根据递归的不同特点，将递归程序分类。按照递归调用时，递归语句在程序中出现的位置可以将递归程序分类为：顺序调用递归、分支调用递归和循环调用递归。下面本文分别给出实例。

1.顺序调用递归。此类递归程序结构往往比较简单，指递归调用语句出现在程序的顺序执行语句中，递归程序在调用处执行，執行完毕返回到调用处的后续语句。如求阶乘、斐波那契数列、树的前中后序遍历等。

2.分支调用递归。此类递归程序往往包含分支语句，也就是说程序在进行运算时，要根据需要解决的问题的实际需求，分不同情况进行递归调用，递归调用时不同分支调用的参数往往不同。这类程序包含整数划分问题、二分查找问题、快速排序等，以整数划分问题为例最为典型。

3.循环调用递归。此类递归程序最为复杂，也是学生最不好理解的一类递归。递归调用语句出现在循环语句中，如for、while循环中，在循环中进行递归调用。有时很多程序还得结合判断条件，在循环中符合条件的情况递归调用，不符合条件的不调用，调用结束后返回本层循环语句继续下一个循环变量的调用。这类程序如图的深度优先遍历、求一个集合的全排列、八皇后问题等。以深度优先遍历为例，见图1。

四、课堂讲授案例

1.以趣味问题引入递归。八皇后问题，是一个古老并且非常著名的算法问，它是递归算法的经典例题。这个问题由国际象棋棋手马克斯·贝瑟尔于1848年提出。在8×8格的棋盘上摆放8个皇后棋子，给定任意两个皇后使得它们不能处于同一行、同一列或同一斜线上，请问有多少种布局的方法。数学家高斯起初认为有76种方案，后来有人用图论的方法知道正确答案是92种解法。

2.问题的解法思路。由于棋盘一行或者一列只可以放置一个皇后，就可以用一维数组X（x1，x2，…，xn），表示第i列皇后所在的行x[i]，所以用一维数组来表示各个皇后的位置就可以。对于每一行的皇后可以放置在1，2，…，n各个列同时还不能和已经放置的皇后有冲突，所以很显然，该递归程序的设计是循环递归调用的方法。

3.递归程序设计。根据上述分析，循环递归调用的程序设计如图2所示。

五、结束语

为了使学生们很好地掌握递归这一贯穿于大学计算机相关专业各个阶段的算法，本文首先给出了递归问题的本质和递归程序本身的特点，分析了学生们在掌握这类算法或者程序时容易出现的问题。然后结合实际教学情况对递归程序进行了分类，从简单到复杂把各种递归程序出现的情况做了详细的总结，便于教师课堂讲授和学生分类学习。最后给出了一个实际的教学实例，详细讲述了递归程序的设计思路和步骤。通过本文分析，使得递归问题可以实现趣味性教学，并使学生对课程感兴趣且更易学会。

参考文献：

[1]项响琴.递归问题的教学探讨[J].合肥学院学报，2016，6.

[2]朱浩.基于自组织理论的研究生创新思维生成与培养机制研究[J].研究生教育，2015，4（4）：22-26.

[3]范昊，束德勤.《数据结构》教学方法研究[J].教育教学论坛，2019，47：195-196.

[4]刘羿，虎晓红，孙昌霞.高度信息化形式下高校计算机基础课程教学探析[J].教育教学论坛，2019，47：197-199.

Research on the Teaching Method of "Classification Discussion" on Recursive Algorithm

FAN Hao，SHU De-qin

（College of Information Science and Engineering，Shandong Agricultural University，Tai'an，Shandong 271018，China）

Abstract：Recursion algorithm or recursion program is a kind of program design method that must be mastered by college students majoring in computer and related majors in the university learning stage.This paper first analyzes the difficulties college students encounter in learning recursive algorithm，analyzes the nature and characteristics of recursive program，then classifies the recursive algorithm from different angles，and finally explains and summarizes the design process of recursive program.The paper also gives the explanation and design process of recursive algorithm.This method has a good practical application effect on the teaching and research of recursive algorithm.

Key words：recursion algorithm;typical cases;recursion programming framework;algorithmic classification

收稿日期：2019-10-20

基金項目：2019教育部产学合作协同育人项目（面向企业需求的学生创新能力培养模式研究）项目编号：201901117012

作者简介：范昊（1977-），男，山东泰安人，副教授，主要研究方向为算法设计与分析、Petri网理论与应用、深度学习等。

通讯作者：束德勤（1978-），女，山东淄博人，副教授，主要研究方向为计算机网络、Petri网理论与应用等。