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

本文格式为Word版，下载可任意编辑——C语言中递归函数的教学方法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当n1时，n!可以通过对1个小规模的子问题n-1!的求解得到，也即n!=n-1!*n。

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

分析：该问题可使用下述递归布局举行求解：

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

2当n1时，将圆盘按以下方法移动见图2：

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

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

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

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

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

分析：该问题可使用下述递归布局举行求解：

1当n=1时，直接输出排序结果;

2当n1时，按以下方法举行排序：

①将array分成大小根本一致的两片面;

②对两个子数组分别举行排序;

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

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

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

Tn=Onlogn4

4.结语

在C语言教学中，函数的递归一向是教学的重点和难点。本文首先从理论上