文档介绍：C语言中递归函数的设计
主讲人熊立伟
(武汉大学遥感信息工程学院)
1、教学目标
使学生学会使用和设计递归函数去解决较复杂的问题
2、教学重点
递归函数的定义、递归问题的分类、递归函数设计的一般步骤
3、教学难点
理解递归函数的内涵、确定递归结束条件
4、教学方法
讲故事激发学生兴趣,巧解概念,典型例题分析
新课导入:C程序结构是函数模块结构,C程序是由一个或多个函数构成的,是函数的集合。函数具有相对独立的特定功能,是程序的基本单位,因此,在C语言教学中,函数这一章(大部分教材把函数作为一章)是重点内容,而函数的递归调用则是这一章的重点之一。下面我们首先来看递归函数的定义
一、递归的定义
在调用一个函数的过程中调用该函数本身,称为函数的递归调用。递归调用简称递归。
有这么一个古老的故事:从前有座山,山上有个庙,庙里有个老和尚和小和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有个庙,庙里有个老和尚和小和尚,老和尚给小和尚讲故事,讲的是……
这是一个典型的“递归”故事,可以无限次递归下去。当大人们肚中无故事而又要哄小孩时,常常讲这个故事。
我们可把这个故事比喻成递归调用,但在C语言程序设计中,程序不可无限地递归下去,必须有递归结束条件,而且每次递归都应该向结束条件迈进,直到满足结束条件而停止递归调用。为此,可将上述“递归”故事修改如下:
从前有座山,山上有个庙,庙里有个老和尚和3岁的小和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有个庙,庙里有个老和尚和2岁的小和尚,老和尚给小和尚讲故事,讲得是:从前有座山,山上有个庙,庙里有个老和尚和1岁的小和尚。
这里的递归结束条件即小和尚的年龄,因为没有0岁的小和尚,所以讲到“庙里有个老和尚和l岁的小和尚”时,故事结束。每次递归都使小和尚的年龄减少一岁,所以总有终止递归的时候,不会产生无限递归。
二、递归的分类
1、数值问题
可以表达为数学公式的问题,如求非负整数N的阶乘、求斐波那契数列的第n项、求两个整数的最大公约数等。
2、非数值问题
其本身难以用数学公式表达的问题,如著名的汉诺塔问题、八皇后问题。
三、递归函数设计的一般步骤
编写递归程序有两个要点:一是要找到正确的递归算法,这是编写递归程序的基础;二是要确定递归算法的结束条件,这是决定递归程序能否正常结束的关键。
前面我们把递归问题分为两大类:数值问题和非数值问题。这两类问题具有不同的性质,所以解决问题的方法也不同。
对于数值问题,由于可以表达为数学公式,所以可以从数学公式入手推导出问题的递归定义,然后确定问题的边界条件,从而确定递归的算法和递归结束条件。
对于非数值问题,其本身难以用数学公式表达。求解非数值问题的一般方法是要设计一种算法,找到解决问题的一系列操作步骤。如果能够找到解决问题的一系列递归操作步骤,同样可以用递归的方法解决这些非数值问题,寻找非数值问题的递归算法可以从分析问题本身的规律入手,可以按照下列步骤进行分析:
第一步,将问题进行化简,将问题的规模缩到最小,分析问题在最简单情况下的求解方法,这时的算法应当是最简单的非递归算法。
第二步,将问题分解为若干个小问题,其中至少有一个小问题具有与原问题相同的性质,只是在规模上比原问题有所缩小,将分解后的每个小问题作为一个整体,描述用这些较小的问题解决原来较大问题的算法。
由第二步得到的算法就是一个解决原问题的递归算法,第一步将问题的规模缩到最小时的条件就是该递归算法的结束条件。
三、典型例题分析
首先来看一个数值问题的递归算法
例1用辗转相除法求整数m与n的最大公约数。
讨论:此问题属于数值问题,求m与n的最大公约数等价于求n与(m%n)的最大公约数,这时可以把n当作新的m,(m%n)当作新的n,问题变成了求新的m与新的n的最大公约数,它又等价于求新的n与(m %n)的最大公约数……如此继续,直到新的n=0时,所求最大公约数就是新的m,这就是用辗转相除法求m与n的最大公约数的过程。
因此,有如下递归算法:
=m%n
=0,则n为所求,输出n,结束
!=0,则令m=n,n=r
按照上述算法可编写出如下C语言程序:
#include<>
void main()
{
int gcd(int m,int n);
int m,n,g;
printf(“请输入整数m,n:”);
scanf(“%d%d”,&m,&n);
printf(“\n”);
g=gcd(m,n);
printf(“%d和%d的最大公约数是:%d\n”,m,n,g);
}
int gcd(int m,int n)
{
int g;
if(n==0)
g=m