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