C语言中递归函数的教学方法探讨

孙冬 高清维 卢一相

摘 要： 函数递归基于分治法思想，将复杂的大规模问题转化为小规模问题进行求解，在算法设计中具有重要的理论意义和实用价值，是C语言教学的难点。通过一组从简单到复杂的程序实例，引导学生由浅入深地掌握递归程序的编写技巧，在教学中取得较好的效果。

关键词： C语言 递归函数 分治法思想 教学方法

1.引言

C语言是一种语法简洁紧凑、运算符丰富、可移植性强、目标程序执行效率高的强数据类型语言，近年来在国内得到迅速的推广应用。作为我校信息类本科教学的入门语言，C语言是汇编语言、计算机原理、单片机程序设计等其他后继课程的基础，对整个教学过程具有重要的作用。

所有的C语言程序都由函数组成。在函数的调用中，直接或间接地调用自身的函数称为递归函数，相应的算法称为递归算法。在计算机算法设计与分析中，递归算法是一类较重要的算法，递归的使用往往使函数的定义和算法的描述简洁且易于理解。

2.递归的基本原理

对于任何可以用计算机求解的问题，其求解难度与计算时间都与问题的规模有关。若一个规模较大的且难以直接解决的问题能够分解为k个规模较小的子问题，并且这些子问题互相独立且与原问题相同，那么可以通过对这些子问题进行分别求解，然后将各个子问题的解合并，得到原问题的解。其中P代表原始问题，P1、P2…Pk是比原始问题的规模|P|更小的子问题，Merge函数将子问题的解y1、y2…yk进行合并。

假设原始问题规模为n，子问题P1、P2…Pk的规模为n/m，分解阈值n0=1，且AdHoc函数求解规模为1的问题耗费1个单位时间。再设合并函数Merge的时间复杂度为f此时递归算法具有多项式的计算复杂度，其阶数由子问题的划分数目k和子问题的规模n/m共同决定。

3.教学实例分析

函数的递归是C语言教学中的一个难点，本节根据上面给出的递归程序结构，通过一组从简单到复杂的实例，逐步引导学生掌握递归程序编写的技巧。

实例1（阶乘问题）：计算整数n的阶乘。

分析：该问题可使用下述递归结构进行求解：

（1）当n=1时，可以直接计算n！=1；

（2）当n>1时，n！可以通过对1个小规模的子问题（n-1）！的求解得到，也即n！=（n-1）！*n。

实例2（Hanoi塔问题）：设a、b、c是三个塔座。开始时，在a座处自上而下、从小到大地叠放n个圆盘，编号分别为1、2、…n，如图1所示。现要求将a座处的所有圆盘按同样的次序堆叠到b座上，并且要求：（1）每次只能移动1个圆盘；（2）任何时候都不允许将大盘压在小盘的上方。

分析：该问题可使用下述递归结构进行求解：

（1）当n=1时，直接将盘从a座移动到b座；

（2）当n>1时，将圆盘按下列方法移动（见图2）：

①将a座上的n-1个盘移动到c座；

②将a座的第n个盘移动到b座；

③将c座上的n-1个盘移动到b座。

根据以上分析，可以写出如下的程序：

实例3（排序问题）：对n个元素的整型数组array进行排序。

分析：该问题可使用下述递归结构进行求解：

（1）当n=1时，直接输出排序结果；

（2）当n>1时，按下列方法进行排序：

①将array分成大小基本相同的两部分；

②对两个子数组分别进行排序；

③将两个排序后的子数组进行合并。

其中参数left和right分别代表当前数组的第1个元素和最后一个元素的下标。

对于该排序算法，子问题的数目k=2，规模n/m = n/2。因为函数Merge的合并操作可以在线性时间内完成，所以由（3）式可以得到相应的时间复杂度为

T（n）=O（nlogn）（4）

4.结语

在C语言教学中，函数的递归一直是教学的重点和难点。本文首先从理论上给出递归的程序结构，然后以该结构为指导，通过一组程序实例，引导学生掌握递归程序的编写技巧，理解应用分治法解决复杂问题的思想。实践证明，本方法在课堂教学中取得较好的效果。

参考文献：

[1]张建军，史银龙，刘胜厚.C语言程序设计[M].北京：海洋出版社，2010：53-63.

[2]谭浩强.C语言程序设计[M].北京：清华大学出版社，1999：35-38.

[3]范劲松，黄友初.案例教学法在C语言教学中的系统应用[J].郧阳医学院学报，2005，24（3）：191-192.

[4]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2010：9-22.