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)当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座;