- 相关推荐
C语言中递归函数的教学方法
导语：函数递归基于分治法思想，将复杂的大规模问题转化为小规模问题进行求解，在算法设计中具有重要的理论意义和实用价值，是C语言教学的难点。下面就由小编为大家介绍一下C语言中递归函数的教学方法，欢迎大家阅读!
C语言中递归函数的教学方法 1
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语言中递归函数的教学方法 2
【示例】用递归计算 n!。阶乘 n! 的计算公式如下：
根据公式编程：
long factorial(int n){
long result;
if(n==0 || n==1){
result = 1;
}else{
result = factorial(n-1) * n; // 递归调用
}
return result;
}
这是一个典型的递归函数。调用factorial后即进入函数体，只有当 n==0 或 n==1 时函数才会执行结束，否则就一直调用它自身。
由于每次调用的实参为 n-1，即把 n-1 的值赋给形参 n，所以每次递归实参的值都减 1，直到最后 n-1 的值为 1 时再作递归调用，形参 n 的值也为1，递归就终止了，会逐层退出。
例如求 5!，即调用factorial(5)。当进入factorial函数体后，由于 n=5，不等于0或1，所以执行result = factorial(n-1) * n;，即result = factorial(5-1) * 5;，接下来也就是调用factorial(4)。这是第一次递归。
进行四次递归调用后，实参的值为 1，也就是调用factorial(1)。这时递归就结束了，开始逐层返回。factorial(1) 的值为 1，factorial(2) 的值为 1*2=2，factorial(3) 的'值为 2*3=6，factorial(4) 的值为 6*4=24，最后返回值 factorial(5) 为 24*5=120。
注意：为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。
递归调用不但难于理解，而且开销很大，如非必要，不推荐使用递归。很多递归调用可以用迭代（循环）来代替。
【示例】用迭代法求 n!。
复制纯文本新窗口
long factorial(int n){
int i;
long result=1;
if(n==0 || n==1){
return 1;
}
for(i=1; i<=n; i++){
result *= i;
}
return result;
}
C语言中递归函数的教学方法 3
一、要点：
1、C语言函数可以递归调用。
2、可以通过直接或间接两种方式调用。目前只讨论直接递归调用。
二、递归条件
采用递归方法来解决问题，必须符合以下三个条件：
1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。
说明：解决问题的方法相同，调用函数的参数每次不同(有规律的递增或递减)，如果没有规律也就不能适用递归调用。
2、可以应用这个转化过程使问题得到解决。
说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题。
3、必定要有一个明确的结束递归的条件。
说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。
三、递归实例
例：使用递归的方法求n!
当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。
比如n=5：
第一部分：5*4*3*2*1 n*(n-1)!
第二部分：4*3*2*1 (n-1)*(n-2)!
第三部分：3*2*1 (n-2)(n-3)!
第四部分：2*1 (n-3)(n-4)!
第五部分：1 (n-5)! 5-5=0，得到值1，结束递归。
源程序：
fac(int n)
{int t;
if(n==1)||(n==0) return 1;
else
{ t=n*fac(n-1);
return t;
}
}
main( )
{int m,y;
printf(“Enter m:”);
scanf(“%d”,&m);
if(m<0) printf(“Input data Error!n”);
else
{y=fac(m);
printf(“n%d! =%d n”,m,y);
}
}
四、递归说明
1、当函数自己调用自己时，系统将自动把函数中当前的变量和形参暂时保留起来，在新一轮的调用过程中，系统为新调用的函数所用到的`变量和形参开辟另外的存 储单元(内存空间)。每次调用函数所使用的变量在不同的内存空间。
2、递归调用的层次越多，同名变量的占用的存储单元也就越多。一定要记住，每次函数的调用，系统都会为该函数的变量开辟新的内存空间。
3、当本次调用的函数运行结束时，系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点，同时取得当初进入该层时，函数中的变量和形参 所占用的内存空间的数据。
4、所有递归问题都可以用非递归的方法来解决，但对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂，而函数的递归调用在解决这类 问题时能使程序简洁明了有较好的可读性;但由于递归调用过程中，系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的 开销，因此函数的递归调用通常会降低程序的运行效率。
五、程序流程
fac(int n) /*每次调用使用不同的参数*/
{ int t; /*每次调用都会为变量t开辟不同的内存空间*/
if(n==1)||(n==0) /*当满足这些条件返回1 */
return 1;
else
{ t=n*fac(n-1); /*每次程序运行到此处就会用n-1作为参数再调用一次本函数,此处是调用点*/
return t; /*只有在上一句调用的所有过程全部结束时才运行到此处。*/
}
}
【C语言中递归函数的教学方法】相关文章：
C语言函数递归教程09-25
C语言函数的递归调用08-26
C语言中递归算法的剖析08-15
C语言函数的递归和调用08-22
C语言递归函数的执行与求解08-11
对C语言中递归算法的深入解析09-26
深入解释c语言中的递归算法07-17
C语言中函数的区分08-30
关于C语言函数的递归和调用09-12