C语言中递归函数的设计课件.ppt

C语言中递归函数的设计课件.ppt

ID:57292297

大小:75.50 KB

页数:16页

时间:2020-08-10

C语言中递归函数的设计课件.ppt_第1页
C语言中递归函数的设计课件.ppt_第2页
C语言中递归函数的设计课件.ppt_第3页
C语言中递归函数的设计课件.ppt_第4页
C语言中递归函数的设计课件.ppt_第5页
资源描述:

《C语言中递归函数的设计课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、C语言中递归函数的设计主讲人熊立伟(武汉大学遥感信息工程学院)1、教学目标使学生学会使用和设计递归函数去解决较复杂的问题2、教学重点递归函数的定义、递归问题的分类、递归函数设计的一般步骤3、教学难点理解递归函数的内涵、确定递归结束条件4、教学方法讲故事激发学生兴趣,巧解概念,典型例题分析新课导入:C程序结构是函数模块结构,C程序是由一个或多个函数构成的,是函数的集合。函数具有相对独立的特定功能,是程序的基本单位,因此,在C语言教学中,函数这一章(大部分教材把函数作为一章)是重点内容,而函数的递归调用则是这一章的重点之一。下面我们首先来看递归函数的定义一、

2、递归的定义在调用一个函数的过程中调用该函数本身,称为函数的递归调用。递归调用简称递归。有这么一个古老的故事:从前有座山,山上有个庙,庙里有个老和尚和小和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有个庙,庙里有个老和尚和小和尚,老和尚给小和尚讲故事,讲的是……这是一个典型的“递归”故事,可以无限次递归下去。当大人们肚中无故事而又要哄小孩时,常常讲这个故事。我们可把这个故事比喻成递归调用,但在C语言程序设计中,程序不可无限地递归下去,必须有递归结束条件,而且每次递归都应该向结束条件迈进,直到满足结束条件而停止递归调用。为此,可将上述“递归”故事修改如

3、下:从前有座山,山上有个庙,庙里有个老和尚和3岁的小和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有个庙,庙里有个老和尚和2岁的小和尚,老和尚给小和尚讲故事,讲得是:从前有座山,山上有个庙,庙里有个老和尚和1岁的小和尚。这里的递归结束条件即小和尚的年龄,因为没有0岁的小和尚,所以讲到“庙里有个老和尚和l岁的小和尚”时,故事结束。每次递归都使小和尚的年龄减少一岁,所以总有终止递归的时候,不会产生无限递归。二、递归的分类1、数值问题可以表达为数学公式的问题,如求非负整数N的阶乘、求斐波那契数列的第n项、求两个整数的最大公约数等。2、非数值问题其本身难以

4、用数学公式表达的问题,如著名的汉诺塔问题、八皇后问题。三、递归函数设计的一般步骤编写递归程序有两个要点:一是要找到正确的递归算法,这是编写递归程序的基础;二是要确定递归算法的结束条件,这是决定递归程序能否正常结束的关键。前面我们把递归问题分为两大类:数值问题和非数值问题。这两类问题具有不同的性质,所以解决问题的方法也不同。对于数值问题,由于可以表达为数学公式,所以可以从数学公式入手推导出问题的递归定义,然后确定问题的边界条件,从而确定递归的算法和递归结束条件。对于非数值问题,其本身难以用数学公式表达。求解非数值问题的一般方法是要设计一种算法,找到解决问题

5、的一系列操作步骤。如果能够找到解决问题的一系列递归操作步骤,同样可以用递归的方法解决这些非数值问题,寻找非数值问题的递归算法可以从分析问题本身的规律入手,可以按照下列步骤进行分析:第一步,将问题进行化简,将问题的规模缩到最小,分析问题在最简单情况下的求解方法,这时的算法应当是最简单的非递归算法。第二步,将问题分解为若干个小问题,其中至少有一个小问题具有与原问题相同的性质,只是在规模上比原问题有所缩小,将分解后的每个小问题作为一个整体,描述用这些较小的问题解决原来较大问题的算法。由第二步得到的算法就是一个解决原问题的递归算法,第一步将问题的规模缩到最小时的

6、条件就是该递归算法的结束条件。三、典型例题分析首先来看一个数值问题的递归算法例1用辗转相除法求整数m与n的最大公约数。讨论:此问题属于数值问题,求m与n的最大公约数等价于求n与(m%n)的最大公约数,这时可以把n当作新的m,(m%n)当作新的n,问题变成了求新的m与新的n的最大公约数,它又等价于求新的n与(m%n)的最大公约数……如此继续,直到新的n=0时,所求最大公约数就是新的m,这就是用辗转相除法求m与n的最大公约数的过程。因此,有如下递归算法:1.求r=m%n2.若r=0,则n为所求,输出n,结束3.若r!=0,则令m=n,n=r4.转向步骤1按照

7、上述算法可编写出如下C语言程序:#includevoidmain(){intgcd(intm,intn);intm,n,g;printf(“请输入整数m,n:”);scanf(“%d%d”,&m,&n);printf(“”);g=gcd(m,n);printf(“%d和%d的最大公约数是:%d”,m,n,g);}intgcd(intm,intn){intg;if(n==0)g=m;elseg=gcd(n,m%n);returng;}下面我们再来看一个非数值问题的递归算法例2汉诺塔(Hanoit)问题这是一个著名的问题,相传在很久

8、很久以前,在中东地区的一个寺庙里,几个和尚整天不停地移动着盘子,日复一日,年复一

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。