任务驱动法在递归算法教学设计中的应用

杨平

（韶关学院数学与统计学院，广东韶关512005）

任务驱动法在递归算法教学设计中的应用

杨平

（韶关学院数学与统计学院，广东韶关512005）

摘要：递归作为一种编程算法在程序设计中广泛应用，是编程思维的重点内容之一.以任务驱动法在递归算法课堂教学中的应用为例，设计趣味性任务,由浅入深,激发学生的兴趣，利用道具分解任务规模，促进对问题本质的理解，旨在提高学生的学习兴趣，培养学生的编程能力，提高教学质量.

关键词：递归算法；编程算法；课堂教学；编程能力

递归作为一种编程算法在程序设计中广泛应用，是指函数在运行的过程中又直接或间接地调用该函数本身［1-2］.程序调用自身的编程技巧称为递归，在函数中直接调用函数本身，称为直接递归调用.在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用，称为间接递归调用.

虽然用递归算法编写的程序结构清晰存在着自调用过程，程序控制反复进入其自身，使程序的分析设计有一定困难，致使很多初学者往往对递归迷惑不解，也在这上面花了不少的时间，却收效甚微.本文以“任务驱动法”来设计教学过程的内容，首先从引人入胜的故事入手展开教学，自然简单地引入递归概念，让学生对知识点的认识从感性到理性［3］.再从学生的角度出发合理地设计出学生能接受的教学内容与环节，通过让学生主动分析递归算法经典案例，结合教学道具促进学生容易完成“教学任务”，从而达到培养学生主动分析问题、解决问题的综合能力.

1设计趣味性任务,由浅入深,激发学生的兴趣

课堂教学可以由一个古老的故事引入：从前有座山，山上有个庙，庙里有个老和尚和小和尚，老和尚给小和尚讲故事，讲的是:从前有座山，山上有个庙，庙里有个老和尚和小和尚，老和尚给小和尚讲故事，讲的是：从前有……

这是一个典型的“递归”故事，可以无限次递归下去.可以把这个故事比喻成递归调用，但在程序设计中，程序不可无限地递归下去，必须有递归结束条件，而且每次递归都应该向结束条件迈进，直到满足结束条件而停止递归调用，同时适时宜地给出递归调用的定义.

递归调用的编程应用有一个最著名的问题：相传在很久以前，在中东地区的一个寺庙里，几个和尚整天不停地移动着盘子，日复一日，年复一年，移盘不止，移动盘子的规则是这样的：事先固定三根针，假设分别为A针、B针、C针，A针上套有64个中间带孔的盘子，盘子大小不等，大的在下，小的在上，要求把这64个盘子从A针移到C针，在移动过程中可以借助于B针，每次只允许移动一个盘子，且移动过程中的每一步都必须保证在三根针上都是大盘在下、小盘在上.据说当所有64个盘子全部移完的那一天就是世界的末日，故汉诺塔问题又被称为“世界末日问题”.

从给出这个著名的案例着手一步一步引导学生积极思考，从而自主找出解决问题的方法，这样的课堂的教学才能让学生印象深刻，掌握递归本质.

2利用道具分解任务规模，促进对问题本质的理解

课前简单制作出3个纸柱子与4个不同大小在空心纸盘.首先给出一个最简单的情况，A针上只有一个盘，让一个同学动手操作如何去完成案例任务.当然任何一个学生就能完成：直接把一个盘从A针移到C针.

其次给出A针上只有2个盘，让2个同学起来操作如何去完成任务.可以适当引导学生把任务分解成3步：（1）学生甲让学生乙把A针上的一个盘从A针移到B针上.（2）学生甲直接把A针上剩下的一个盘子移到C针.（3）学生乙把B针上的一个盘从B针移到C针上.可以发现一共移动了3=22-1次.

再给出A针只有3个盘，让3个同学起来操作如何去完成任务.可以适当引导学生把任务分解成3步：（1）学生甲让学生乙、丙把A针上的2个盘从A针移到B针上（用上的方法移动了3次）.（2）学生甲直接把A针上剩下的一个盘子移到C针.（3）学生乙、丙把B针上的2个盘从B针移到C针上（用上的方法移动了3次）.可以发现一共移动了3+1+3=7=23-1次.

图1　初始状态　

图2　分解完成子问题

图3　分解完成单步移动

图4　分解完成整个问题

依次给出A针上只有4个盘的情况，如图1～4所示.

利用前面每次的操作结果，同学们很快可以完成给定的任务，可以顺其自然推理出：对于n个盘子需要移动2n-1次，把64个盘子都移动完毕约需1.8x1019次，假设每秒移动一次，约需一万亿年，不愧是世界末日问题，地球寿命才100亿年.目前，由于计算机运算速度的限制，仅能找出问题的解决方法并解决较小n值的汉诺塔问题.

讨论：汉诺塔问题属于非数值问题，难以用数学公式表达其算法，可以从分析问题本身的规律入手.第一步，问题化简，设A针上只有一个盘子，即n=1，则只需将1号盘从A针移到C针.第二步，问题分解，对于A针上有n（n＞1）个盘子的汉诺塔，可分为三个步骤求解：①将A针上n-1个盘子借助于C针移到B针；②把A针上剩下的一个盘子移到C针；③将B针上n-1个盘子借助于A针移到C针.

显然，①、③两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现.

整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出完整的递归算法描述.

定义一个函数movedisk（int n，char fromneedle，char tempneedle，char toneedle），该函数的功能是将fromneedle针上的n个盘子借助于tempneedle针移动到toneedlee针，这样移动n个盘子的递归算法描述如下.

按照上述算法可编写出如下C语言程序：

3任务驱动法教学内容的展开

适当对递归调用教学内容的展开，在逐步求解的过程中培养学生的探索精神和分析、综合归纳问题的能力.引导学生探索递归调用编程在其他方面应用，总结递归调用编程的通用方法与思维.

3.1数值问题

可以表达为数学公式的问题，如求斐波那契数列的第n项、求非负整数N的阶乘、求两个整数的最大公约数等.

首先来看一个数值问题的递归算法的典型例子，斐波那契数列Fib（n）的递推定义是：

按照上式，求第n项斐波那契数列的递归函数如下：

对于数值问题，由于可以表达为数学公式，所以可以从数学公式入手推导出问题的递归公式，然后确定问题的边界条件，从而确定递归的算法和递归结束条件.

3.2非数值问题

对于本身难以用数学公式表达的问题，如著名的汉诺塔问题、八皇后、九连环问题等非数值问题，求解的一般方法是要设计一种算法，找到解决问题的一系列操作步骤.如果能够找到解决问题的一系列递归操作过程，同样可以用递归的方法解决这些非数值问题，寻找非数值问题的递归算法可以从分析问题本质的规律入手，可以按照下列步骤进行分析：（1）将问题进行化简与最大限度缩小问题规模，分析问题在最简单情况下的求解方法与过程，这时的算法应当是最简单的非递归算法.（2）将问题分解为若干个小问题，其中至少有一个小问题具有与原问题相同的性质，只是在规模上比原问题有所缩小，将分解后的每个小问题作为一个整体，描述用这些较小的问题解决原来较大问题的算法.由第（2）步得到的算法就是一个解决原问题的递归算法，第（1）步将问题的规模缩到最小时的条件就是该递归算法的结束条件.

最后引导学生总结递归程序设计的思维与原理，适宜于用递归算法求解的问题的充分必要条件是：一是问题具有某种可借用的类同自身的子问题描述的性质；二是某一有限步的子问题有直接的解存在.

编写递归程序有两个要点：一是要找到正确的递归算法公式，这是编写递归程序的基础；二是要确定递归算法的结束条件，这是决定递归程序是否能正常终止的关键.

任务驱动法课堂教学的最后，可以设计一些比较典型容易实现的任务，让学生趁热打铁，通过完成任务，加深对教学内容的掌握与理解.

4结语

递归算法在程序设计中十分有用.递归算法的实质是把问题转化为规模缩小了的同类问题的子问题.然后递归调用函数来表示问题的解.当一个问题蕴含了递归关系且结构比较复杂时，采用递归算法能使程序变得简洁和清晰，增加了程序的可读性，并能够很容易地解决一些用非递归算法很难解决的问题.

以任务驱动法来设计递归算法课堂教学内容与过程，在任务驱动教学过程中培养学生的探索精神和分析问题的能力，激发学生的求知欲［3-4］，切实提高了课堂教学效果.

参考文献：

［1］谭浩强.C程序设计［M］.4版.北京：清华大学出版社，2010.

［2］严蔚敏，吴伟民.数据结构（C语言版）［M］.北京：清华大学出版社，2004.

［3］唐大仕.“递归算法”微课教学设计——以“文科计算机基础（下）”为例［J］.计算机教育，2013（17）：5-7.

［4］王婧.任务驱动法在计算机课程教学中的应用 ［J］.计算机教育，2011（8）：51-55.

（责任编辑：邵晓军）

中图分类号：TP399；G642

文献标识码：A

文章编号：1007-5348（2016）04-0075-05

［收稿日期］2016-03-01 ［基金项目］韶关学院教育教学改革研究项目（SYJY20131431）；韶关学院2013年度科研项目（韶学院〔2013〕205号）.

［作者简介］杨平(1977-),男,湖南临湘人,韶关学院数学与统计学院讲师,硕士；研究方向：计算机应用技术.

Application of Task Driven Method in the Recursive Algorithm in Teaching Design

YANG Ping
（CollegeofMathematicsandStatistics，ShaoguanUniversity，Shaoguan512005，Guangdong，China）

Abstract:Recursionas aprogrammingalgorithmis widely usedinprogramdesign，whichis oneof thekey content of programming thinking.As an example，the application of task driven method in the recursive algorithm for classroomteaching，and designing interesting tasks，is easy to understand，to stimulate students’interest，to use props to decompose the scale of the task，to promote the understanding of the nature of the problem,in order to improve the students’interest in learning，to train students programming ability，and to improve the quality of teaching.

Key words:recursivealgorithm；programmingalgorithm；classroomteaching；programmingability