《C语言程序设计》课程递归算法的教学设计

摘 要：递归算法是函数嵌套调用的一种特例，递归思想在程序设计中非常重要，递归思想的实质就是把问题转化为规模小的同类问题的子问题，这样对原问题的研究就可转移到子问题的研究，特别是当解决问题的条件不具备时，用递归算法去实现是非常有效的。通过对递归调用的学习，培养学生"自顶向下"、"逐步求精"的编程思想。

关键词：递归算法；嵌套调用 ；编程思想

基于递归算法的编程思想是理论知识强且比较抽象的教学内容，本次课主要运用任务驱动式教学模式和情境教学法，精心挖掘了一些生动、恰当的例子，让学生更容易理解，利用游戏和视频等图文声像并茂的传播方式，增强了感染力，激发了学生的学习兴趣。

一、新课引入（通过角色扮演，情景再现，提升学生的学习兴趣）

引例：有4个人坐在一起，问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1人，他说是10岁。请问第5人到底多大？（举一个通俗的例子来说明递归的思想）

二、递归的定义及条件

1.递归的定义：在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为递归算法。

2.递归的两个条件：

（1）需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量上、规模上不同。（递归方程）

（2）必须有递归结束条件来终止递归。（递归的結束标志）

三、根据递归的条件判断以下的例子是否属于递归（用小组讨论的方式）

从前有座上，山里有座庙，庙里有老和尚在给小和尚讲故事，讲的什么呢？从前有座上，山里有座庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？从前有座上，山里有座庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？……

四、递归的经典案例

1.情境导入汉诺塔问题

（先了解背景知识，满足学生的好奇心，增强学习的兴趣）

相传在印度的一座大寺庙里有一块黄铜板上插着三根宝石针，印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64个金盘， 不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金盘：一次只移动一个金盘，不管在哪根针上，小盘必须放在大盘上面。当所有的金盘都从梵天穿好的那根针上移动到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。

2.体验游戏

这就是汉诺塔，现在已经演变成家喻户晓的益智游戏。那我们就玩汉诺塔游戏吧，（事先用flash制作好的游戏）教师先演示三层的情况，然后学生自告奋勇的上来玩四层的情况。）

通过玩游戏得出结论：

3个金盘由一根针移动到另一根针上至少需要7次， 即23-1

那64个金盘由一根针移动到另一根针上至少需要？（启发学生进行思考）

264-1次。264-1，这是一个天文数字，如果每秒钟移动一次，需要5800亿年。如果计算机每一微秒实现一次移动，也需要5.8亿年。

3.递归的实现与执行

对汉诺塔问题研究的焦点集中在如何以最少的步骤完成全部金盘由一根针搬动到另一根针上。解决这个问题需要运用递归的思想。

哪怎么分解呢？不着急，先看一个视频，让学生从中会得到启发。

（看如何把大象装进冰箱的视频）

得到的启发是：

大象装进冰箱可以分成三步，把64个金盘从一根针移动到另一根针能不能分成三步？ （与学生形成共鸣）

（用Autoware制作的课件演示汉诺塔的搬动过程，看到了吗？问题已经解决了。）

五、递归算法的特点

递归算法的优点在于把复杂问题简单化，用递归分析有些复杂问题思路非常清晰，而且程序简单明了，同时把许多复杂的工作交给系统去处理，减轻了用户的负担。缺点是在递归过程中有大量数据需要保存，增加了系统空间的开销，同时不断重复调用自己，也增加了系统时间的消耗。

作者简介：

1.陈祥（1973-），男，广西岑溪人，教授，研究方向：课程改革、软件技术.

基金项目：广西工业职业技术学院2017年度教育教学改革立项课题：“高职计算机应用专业学生创新创业能力的探索与实践”（项目批准编号：桂工业院2017[56]）.