文档介绍：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的最大公约数的过程。因此,有如下递归算法: r=m%n 2. 若 r=0 ,则 n为所求,输出 n,结束 r!=0 ,则令 m=n,n=r 4. 转向步骤 1按照上述算法可编写出如下 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 (