C语言中递归函数的设计

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的最大公约数的过程。因此，有如下递归算法：1.求r=m%n2.若r=0，则n为所求，输出n，结束3.若r!=0，则令m=n,n=r4.转向步骤1按照上述算法可编写出如下C语言程序：#includestdio.hvoidmain(){intgcd(intm,intn);intm,n,g;printf(“请输入整数m,n:”);scanf(“%d%d”,&m,&n);printf(“\n”);g=gcd(m,n);printf(“%d和%d的最大公约数是：%d\n”,m,n,g);}intgcd(intm,intn){intg;if(n==0)g=m;elseg=gcd(n,m%n);returng;}下面我们再来看一个非数值问题的递归算法例2汉诺塔(Hanoit)问题这是一个著名的问题，相传在很久很久以前，在中东地区的一个寺庙里，几个和尚整天不停地移动着盘子，日复一日，年复一年，移盘不止，移动盘子的规则是这样的：事先固定三根针，假设分别为A针、B针、C针，A针上套有64个中间带孔的盘子，盘子大小不等，大的在下，小的在上，要求把这64个盘子从A针移到C针，在移动过程中可以借助于B针，每次只允许移动一个盘子，且移动过程中的每一步都必须保证在三根针上都是大盘在下、小盘在上。据说当所有64个盘子全部移完的那一天就是世界的末日，故汉诺塔问题又被称为“世界末日问题”。不难计算，对于n个盘子需要移动2n-1次，把64个盘子都移动完毕约需1.8X1019次，假设每秒移动一次，约需一万亿年，若用现代电子计算机计算，设一微秒可计算(并不输出)一次移动，也几乎需要一百万年。目前，由于计算机运算速度的限制，我们仅能找出问题的解决方法并解决较小n值的汉诺塔问题。讨论：汉诺塔问题属于非数值问题，难以用数学公式表达其算法，可以从分析问题本身的规律入手。第一步，问题化简，设A针上只有一个盘子，即n=1，则只需将1号盘从A针移到C针。第二步，问题分解，对于有n（n1）个盘子的汉诺塔，可分为三个步骤求解：1.将A针上n-1个盘子借助于C针移到B针2.把A针上剩下的一个盘子移到C针3.将B针上n-1个盘子借助于A针移到C针显然，上述1,3两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现。整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述：定义一个函数movedisk(intn,charfromneedle,chartempneedle,chartoneedle)，该函数的功能是将fromneedle针上的n个盘子借助于tempneedle针移动到toneedlee针，这样移动n个盘子的递归算法描述如下：movedisk(intn,charfromneedle,chartempneedle,chartoneedle){if(n==1)将n号盘子从one针移到three针;esle1.movedisk(n-1,fromneedle,toneedle,tempneedle)2.将n号盘子从fromneedle针移到toneedle针;3.movedisk(n-1,tempneedle,fromneedle,toneedle)}按照上述算法可编写出如下C语言程序：#includestdio.hvoidmain(){voidmovedisk(intn,charfromneedle,chartempneedle,chartoneedle);intn;printf(“Pleasesinputthenumberofdiskes:”);scanf(“%d”,&n);printf(“Thestepmovingdiskesis:\n”);movedisk(n,’A’,’B’,’C’);}voidmovedisk(intn,charfromneedle,chartempneedle,chartoneedle){if(n==1)printf(“%c%c\n”,fromneedle,toneedle);else{movedisk(n-1,fromneedle,toneedle,tempneedle);printf(“%c%c\n”,fromneedle,toneedle);movedisk(n-1,tempneedle,fromneedle,toneedle);}}五、总结递归是一个十分有用的方法。当一个问题蕴含了递归关系且结构比较复杂时，采用递归调用的程序设计技巧可以使程序变得简洁，增加了程序的可读性，递归调用能使代码紧凑，并能够很容易地解决一些用非递归法很难解决的问题。当然，递归算法也有它的缺点，递归程序通常要花费较多的机器时间和占用较多的存储空间，另外也不是每个问题都适合用递归方法求解。