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

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


【C语言中递归函数的教学方法】相关文章:

C语言函数的递归调用10-04

C语言递归函数的执行与求解11-15

c语言中time函数的用法10-08

C语言中strpbr()函数的用法10-04

C语言中isalnum()函数和isalpha()函数的对比11-21

C语言中函数的区分有哪些11-21

C语言函数教学方法11-27

C语言中函数之间地址传递方式11-13

在C语言中函数调用方式的区别11-20

C++调用C函数的方法 轻松学习C语言的技巧