《C语言与程序设计教程》课件第5章.ppt

1、第第5章章 函数函数 5.1 函数的概念及特点 5.2 函数的定义和调用 5.3 变量的作用域 5.4 函数的嵌套调用与递归调用5.5 典型例题精讲*5.6 递归转化为非递归研究 5.1 函数的概念及特点函数的概念及特点 5.1.1 函数的概念函数的概念对于一些规模较大而又比较复杂的问题，解决的方法往往是把它们分解成若干个较为简单和基本的问题进行求解。这在程序设计中表现为：将一个大程序分解为若干个相对独立且较为简单的子程序，大程序通过调用这些子程序来完成预定的任务。子程序的引入不仅可以较容易地解决一些复杂问题，而且更重要的是使程序有了一个层次分明的结构。另外，程序中反复出现的相同程序段也可以采

2、用子程序的形式独立出来，以供程序随时调用。子程序结构不但增强了程序的可读性，同时也使一个复杂程序的编写、调试、维护和扩充都变得更加方便和容易。主程序与子程序间的调用关系如图5-1所示，主程序顺序执行到调用子程序语句时，就转去执行子程序；当子程序执行结束时，再返回到主程序中调用子程序语句的下一条语句继续向下执行。图5-1 主程序与子程序调用关系示意图在C语言中，子程序的作用是由函数来完成的。一个C程序可由一个主函数(即main函数)和若干个其他函数构成。主函数main可以调用其他函数，其他函数之间也可以相互调用，同一个函数可以被一个或多个函数调用任意多次。C程序的执行总是从主函数main开始，其

3、间可以调用其他函数，但最终还是回到main函数并在main函数中结束整个程序的运行。5.1.2 函数的分类函数的分类从函数定义角度看，函数可分为库函数和用户自定义函数两种。1.库函数库函数由C语言系统直接提供且不必在程序中作类型说明，只需在程序前包含该函数原型的头文件即可。前面各章例题中反复用到的printf、scanf、getchar、putchar、gets、puts、strcat等函数均属此类。例如，要使用数学函数，则需用“#include”将数学头文件包含到程序中；要使用字符串处理函数则需用“#include”将字符串处理头文件包含到程序中。注意，C程序中调用库函数时需分两步实现。第一

4、步：在程序开始处使用include命令指出库函数的相关定义和说明。而include命令必须以“#”开头，系统提供的头文件以“.h”作为文件后缀，文件名用一对尖括号“”或一对双引号“”括起来。由于以#include开头的命令行不是C语言语句，故该命令行末尾不加分号“;”。第二步：在程序中需要调用这个库函数的地方调用此库函数，其形式为：库函数名(参数表)常见的库函数如下：(1)输入输出函数(头文件为stdio.h)：用于完成输入输出功能。(2)字符串函数(头文件为string.h)：用于字符串操作和处理。(3)数学函数(头文件为math.h)：用于数学函数计算。(4)内存管理函数(头文件为stdl

5、ib.h)：用于内存管理。(5)日期和时间函数(头文件为time.h)：用于日期、时间的转换操作。(6)接口函数(头文件为dos.h)：用于与DOS、BIOS和硬件的接口。C语言常用的标准库函数及调用方式参见附录3。2.用户自定义函数用户自定义函数是指用户按需要自行定义和编写的函数。虽然C语言的标准库函数为用户提供了丰富的函数，但还远远不能满足用户实际编程的需要。因此，大量的函数还需用户自行定义。如何定义一个函数以及如何正确调用一个函数是本章讨论的重点。5.2 函数的定义和调用函数的定义和调用 5.2.1 函数的定义函数的定义在C语言中，所有自定义的函数都必须遵循“先定义，后使用”的原则，在使

6、用之前先进行定义。并且，所有的函数定义包括主函数main都是相互平行和独立的，不允许出现嵌套定义。函数定义的形式为：类型标识符 函数名(形式参数表)函数体其中第一行称为函数首部，它定义了函数返回值的类型、函数的名字以及调用该函数时需要给出的参数个数及参数的类型。需要注意的是，函数名为有效的标识符，不能与其他变量名、数组名相同。此外，如果所定义的函数不需要参数，则形式参数表可以省略，但括号“()”不能省略。用花括号“”括起来的部分称为函数体，它包括函数的说明部分和执行部分。说明部分用于对函数内部使用的变量进行定义，也即在此定义的变量仅在该函数内部有效；执行部分是函数的主体，它具体描述该函数所应实

7、现的功能。根据完成功能和调用方式的不同，C语言的函数又分为有返回值函数和无返回值函数两种类型。1无返回值函数无返回值函数其典型标志是函数返回值的类型为void，这种函数只是完成某种指定的操作，并且调用该函数通过一个函数调用语句实现。例如：#includevoid f(int x);/*自定义函数f的声明语句*/void main()int a=5;f(a);void f(int x)/*自定义函数f*/printf(%dn,x);在此，自定义函数f只是完成将主函数main传递过来的a值(已保存于形参x中)进行输出这一功能，而主函数main调用函数f也是通过一个函数调用语句“f(a);”实现的。

8、2有返回值函数有返回值函数其典型标志是函数返回值的类型为int、char、float和指针类型(见第6章)等，这种函数实现的操作主要是为了获得一个计算的结果值，而这个结果值最终必须通过return语句返回给调用者，并且这个返回值的类型就是由函数首部这个类型标识符来指定的。对于该类函数调用可以出现在表达式中，即出现在赋值号“=”右边或printf输出语句中。例如：#includeint f(int x);/*自定义函数f的声明语句*/void main()int a=5;printf(%dn,f(a);int f(int x)/*自定义函数f*/return(x*x);在此，自定义函数f完成将主

9、函数main传递过来的a值(已保存于形参x中)平方后再通过return语句传回给main函数，而主函数main调用函数f是以表达式的形式出现在printf语句中。需要注意的是，这类函数在定义时通常要有将函数计算结果返回给调用者的return语句，并且通常是在表达式中调用这类函数。在PASCAL等高级语言中，像C语言中这种无返回值函数被称之为过程，而有返回值函数才称之为函数。5.2.2 函数的调用和返回值函数的调用和返回值1.函数的调用函数虽然不可以嵌套定义，但可以嵌套调用，也允许函数之间相互调用。通常我们把调用者称为主调函数而把被调用者称为被调函数。函数还可以自己调用自己，被称为递归调用。在大

10、多数情况下，函数调用时主调函数与被调函数之间存在着数据传递(也称参数传递)。需要说明的是，在定义函数时函数名后面括号“()”中的变量名称为“形式参数”(简称“形参”)；在主调函数中调用一个函数时，该函数名后面括号“()”中的参数称为“实际参数”(简称“实参”)。形式参数本身只具有形式上的意义，仅当给形式参数赋予了调用的实际参数后才有确切的内容。形式参数与程序中的变量定义类似，也有值的类型。因此在函数定义时必须指定每个形式参数的类型。在函数调用时，参数传递的方式是将主调函数中的实参(可以是常量、变量或表达式)传递给被调函数中的形参，这是一种值的传递。参数传递的原则是：形参与实参的排列顺序必须一致

11、，类型必须相同或赋值相容，参数的个数也必须相同。需要注意的是，在定义函数时指定的形参，在未出现函数调用时，它们并不占用内存单元，只有在发生函数调用时，这些形参才被分配内存单元并接受所对应的实参值。当函数调用结束时，形参占用的内存单元被系统收回而不再存在；函数内定义的变量(称为局部变量)也是如此。当再次出现函数调用时，则重复上述的分配和回收过程。函数调用的过程是：当主调函数调用被调函数时，先为被调函数的形参开辟对应的内存单元，然后计算出实参表达式的值并送入对应的形参内存单元；至此参数传递完成，形参与实参之间就不再发生联系，形参的任何变化也不影响实参。这种参数传递如同接力比赛的交接棒一样，当交完棒

12、后，交棒者和接棒者就再无关系了。当函数执行结束时，形参因其内存单元被系统收回而不存在，故形参仅在函数中有意义。因此，可以把形参看做是函数中的局部变量，而实参传递给形参就相当于给形参赋初值。例如：#includeint sum(int x,int y);void main()int a=1,b=2,c;c=sum(a,b);printf(c=%dn,c);int sum(int x,int y)int z;z=x+y;return z;在此，主调函数main将两个整数a和b的值分别传递给被调函数sum的形参x和y。而函数sum则实现对x和y两数求和的功能，并通过变量z将求和的结果返回给主调函数m

13、ain的变量c，最终通过函数printf输出这个c值。2.函数的返回值函数的返回值是指调用被调函数后，执行函数体中的语句得到所需的计算结果，并将这个结果值通过return语句返回给主调函数，这个值就是函数的返回值。在定义带返回值的函数时，必须先定义函数的类型。函数类型决定了函数返回值的类型，这里要注意以下两点：(1)函数返回值的类型和函数的类型应保持一致。如果两者不一致则以函数定义中的函数类型为准，将函数的返回值自动转换为函数定义的类型。(2)函数返回值通常由return语句返回给主调函数。return语句的功能是计算表达式的值并返回给主调函数，只要执行return语句，则结束被调函数的执行并

14、将返回值(如果有的话)返回给主调函数。在一个函数中可以有多条return语句，但每次函数调用只能有一条return语句被执行(当执行该条return语句后即返回到主调函数，故其余return语句无法执行)，所以一个函数只能返回一个函数值。return语句的格式分为下面三种：(1)return表达式;(2)return(表达式);(3)return;其中，(1)、(2)两种格式的功能是一样的，它们都能实现：将返回值返回给主调函数；终止被调函数的执行；返回到主调函数。第(3)种格式与第(1)、(2)种格式的差别在于无返回值返回给主调函数。注意，VC+6.0有返回值函数使用格式(1)、(2)，而无返

15、回值(void开头)函数通常不使用return语句，如果使用也只能用格式(3)。例如：#includeint max(int x,int y);void main()int a=5,b=6,c;c=max(a,b);printf(%dn,c);int max(int x,int y)if(xy)return x;elsereturn y;此外，要注意的是，定义为void类型的函数中是没有return语句的，这类函数只是完成需要的操作而无返回值。5.2.3 函数执行的分析方法函数执行的分析方法为了能够形式化地描述函数调用执行的全部过程，我们采用称之为动态图的方法来对程序的执行进行描述，即记录主函

16、数和被调函数的调用、运行及撤消各个阶段的状态，以及程序运行期间所有变量和函数形参的变化过程。动态图规则如下：(1)动态图纵向描述主函数和其他函数各层之间的调用关系，横向由左至右按执行的时间顺序记录主函数和其他函数中各变量及形参值的变化情况。(2)函数的形参均看做是带初值的局部变量。其后，形参就作为局部变量参与函数中的操作。(3)主函数、其他函数按运行中的调用关系自上而下分层，各层说明的变量包括形参都依次列于该层首列，各变量值的变化情况按时间顺序记录在与该变量对应的同一行上。例5.1 用动态图分析下面程序的执行过程。#includeint max(int x,int y);void main()

17、int a=5,b=6,c;c=max(a,b);printf(%dn,c);int max(int x,int y)int z;z=xy?x:y;return(z);解 函数max的形参为x、y，在函数调用时y、x分别接受了实参b、a的值6和5。注意，在VC+6.0中参数传递是由右左进行的(参见例5.2)。此外，函数max还定义了一个局部变量z来保存x和y值中较大的那一个值，最终将这个z值返回给主调函数main。图5-2以动态图的方式描述了整个程序的执行情况，其中包括函数max因调用而创建、运行及运行结束后撤消的全过程。由动态图可知该程序的输出结果为6。图5-2 程序运行和函数调用动态图例5

18、.2 用动态图分析下面程序的执行过程。#includeint add(int x,int y);void main()int i=1,sum;sum=add(i,+i);printf(%dn,sum);int add(int x,int y)int z;z=x+y;return(z);运行结果：4 解 主调函数main调用被调函数add的实参依次为i和+i，根据参数传递由右向左的原则，则先执行+i，即i值变为2后传递给形参y，接着再将i值(已为2)传给x。图5-3(a)中的动态图描述了整个程序的执行情况，因此最终的输出结果是4而不是3，程序上机执行也证实了这种结果。如果调用函数的语句改为sum

19、=add(+i,i);，则最终输出结果是3而不是4，这也证实了参数传递是由右向左进行的。此时程序的执行情况见图5-3(b)的动态图描述。图5-3 程序运行和函数调用动态图5.2.4 函数的声明如果被调函数定义在主调函数之前，则满足“先定义，后使用”的原则，主调函数可在函数体内直接调用被调函数；如果被调函数定义在主调函数之后，那么主调函数在函数体内直接调用被调函数则成了“先使用，后定义”，即违背了“先定义，后使用”的原则。在有些情况下不可避免的会出现“先使用，后定义”这种情况：如两个函数相互调用时，则必然有一个函数调用会出现“先使用，后定义”的问题。为了解决这种矛盾，即被调用函数定义在主调函数之

20、后时，则必须在程序中予以声明。声明的方法是将后定义的被调函数其函数首部(即该函数定义的第一行)再加上一个分号“;”放置于主调函数之前或主调函数中的说明部分。这样，当在主调函数中使用被调函数时由于其前面已有了该函数的“声明”，则认为被调函数已经定义过了，即满足了“先定义，后使用”的原则。例5.3 分析下面程序进行两数交换的执行过程。#includevoid main()void swap(int a,int b);int x=8,y=10;printf(x=%dty=%dn,x,y);swap(x,y);printf(Swapped:n);printf(x=%dty=%dn,x,y);void

21、swap(int a,int b)int temp;temp=a;a=b;b=temp;运行结果：x=8 y=10Swapped:x=8 y=10 解 本例中，被调用函数swap定义于主调函数之后，因此在主调函数main调用被调函数swap的调用语句“swap(x,y);”之前必须先对函数swap进行声明。在程序中，这个声明语句位于主函数main之前(也可放在主调函数main中“swap(x,y);”语句之前的任何位置)。此外，由图5-4可以看出，参数传递只是一种单向传递，即由实参传给形参。而执行被调函数所引起形参值的任何变化都不会影响到实参，故执行完函数swap后返回到主函数main时，其x

22、、y值均没有发生改变。图5-4 例5-3的程序动态图从例5.3可以看出，函数的声明与函数定义中的函数首部只差一个分号“;”，因此可以简单地照抄已定义的函数首部，再加上一个分号“;”，就形成了该函数的“声明”语句。此外，也可以省略函数首部中的形参名，仅保留形参的类型。如上例函数swap的声明可写为：void swap(int,int);此外，例5.3也可以按“先定义，后使用”方式书写：#includevoid swap(int a,int b)int temp;temp=a;a=b;b=temp;void main()int x=8,y=10;printf(x=%dty=%dn,x,y);swa

23、p(x,y);printf(Swapped:n);printf(x=%dty=%dn,x,y);5.3 变量的作用域变量的作用域 当程序中存在两个以上的函数时，就会出现变量的作用域问题。变量的作用域是指变量在程序中可以被使用的范围。在C语言中，根据变量的作用域可以将变量分为局部变量和全局变量。变量说明位置不同，其作用域也不同。5.3.1 全局变量与局部变量全局变量与局部变量在函数内部定义的变量或者在复合语句内部定义的变量，称之为局部变量。它只在该函数范围内或该复合语句内有效，离开这个范围变量就无效了。由于函数中的形参只在该函数内有效，离开该函数就不存在。所以也可以将形参看做接受了实参初值的局部

24、变量(局限于该函数内)。全局变量是指在程序中任何函数之外定义的变量，这种变量的使用不局限于某一个函数，而是从定义处开始位于其后的函数都可使用，也就是由定义处开始至程序结束都有效(即满足“先定义后使用”原则)。如果在函数内有与全局变量同名的局部变量存在，那么究竟哪个变量起作用呢？我们将全局变量和局部变量的适用范围归纳如下：(1)如果全局变量与局部变量不同名，则全局变量适用于由定义处开始至程序结束这个范围，而函数说明的变量及形参则仅局限于在该函数内使用。(2)若全局变量与局部变量同名，则在说明该局部变量的函数之外，同名的全局变量起作用(当然应属于由全局变量定义处开始至程序结束这一范围)，而同名的局

25、部变量则不存在；在函数内，则同名的局部变量起作用，而同名的全局变量暂时不起作用。注意，C语言中规定主函数main与其他函数的地位是相同的，它们是相互平行的。主函数中定义的变量只能在主函数中使用而不能在其他函数中使用，主函数中也不能使用其他函数中定义的变量。在程序中定义全局变量的目的是增加函数间数据传递的通道以及实现数据共享：(1)如果在程序的开始处定义了全局变量，则这个程序中所有函数都能引用全局变量的值。也即，如果在一个函数中改变了全局变量的值，则其他函数就可以访问这个改变了值的全局变量，这样相当于多了一个数据传递的通道。(2)由于函数的调用只能带回一个返回值，则在需要带回两个以上的结果值时就

26、可以使用全局变量。例5.4 用函数实现求两数中的最大值。#includeint a=5,b=8;int max(int a,int b);void main()int a=12;printf(max=%dn,max(a,b);int max(int a,int b)if(ab)return a;elsereturn b;运行结果：max=12 解 本例中定义了两个全局变量a、b，其作用范围为整个程序；而函数max定义两个形参变量a、b，其作用范围在函数max中。可以看到，在函数max和主函数main中都定义了一个局部变量a，而这两个a处于不同函数中，相互没有影响。但全局变量a在函数max和主函

27、数main中被其各自定义的同名局部变量a屏蔽了，即在整个程序范围内不起作用。此外，由于在函数max中定义了局部变量b，而主函数main除了局部变量a再没有定义任何其他局部变量，因此全局变量b在主函数main中有效而在函数max中无效。5.3.2 函数的副作用函数的副作用全局变量在程序整个执行过程中都占用内存单元，造成了内存资源的浪费。此外，全局变量还降低了函数的通用性和可靠性，容易产生错误。因此应尽量避免使用全局变量。下面，我们通过一个例子来看在函数中使用全局变量所产生的副作用。例5.5 全局变量对函数的影响。解 本例中，程序(1)、(2)除了if语句中的逻辑表达式“p|f()”和“f()|p

28、”书写的顺序不同外其余均相同。而从数学上讲，这两种书写格式是完全等价的。但是，由于全局变量p的作用，执行程序(1)时输出“True!”，而执行程序(2)时输出“False!”，造成了概念上的混乱，这就是由于使用全局变量不慎而带来的函数副作用。5.4 函数的嵌套调用与递归调用函数的嵌套调用与递归调用 5.4.1 函数的嵌套调用函数的嵌套调用在C语言中，函数的定义不允许嵌套。也就是说定义函数时，在一个函数定义内(即函数体里)不能再出现另一个函数的定义而形成函数的嵌套定义。但是，函数的调用可以嵌套，即主调函数在调用被调函数的过程中，这个被调函数又去调用其他函数，从而形成函数的嵌套调用。例5.6 验证

29、哥德巴赫猜想，即一个大于等于6的偶数可以表示为两个素数之和。例如：6=3+3，8=3+5，10=3+7，解 题目要求将一个大于等于6的偶数n分解为n1和n2两个素数，使得n=n1+n2。在此采用穷举法来考虑n1和n2的所有组合情况，当发现n1和n2均为素数时则验证成功。我们用函数prime来判断一个数(保存在形参中)是否为素数，如果为素数则返回1，否则则返回0。而用函数div来将给定的偶数(保存在形参中)分解为两个素数之和。程序设计如下：#includeint prime(int n);void div(int n);void main()int n;doprintf(input n(=6):

30、);scanf(%d,&n);while(!(n=6&n%2=0);div(n);void div(int n)int n1,n2;for(n1=3;n1n/2;n1+)n2=n-n1;if(prime(n1)&prime(n2)printf(%d=%d+%dn,n,n1,n2);int prime(int n)int i,flag=1;for(i=2;i=6):1010=3+7程序执行过程及函数的嵌套调用示意如图5-5所示。图5-5 程序执行过程及函数的嵌套调用示意5.4.2 函数的递归调用函数的递归调用函数在它的函数体内直接或间接地调用它自身称为函数的递归调用，这种函数称为递归函数。在递归

31、调用中，主调函数和被调函数是同一个函数。下面我们通过一个例子来说明函数递归调用的特点。例5.7 用动态图分析递归函数的执行过程。#includevoid out1();void main()out1();printf(n);void out1()char ch;scanf(%c,&ch);if(ch!=n)out1();printf(%c,ch);输入：abc输出：cba 解 程序的执行过程及函数递归调用示意见图5-6。由图5-6可以看出：(1)、(2)、(3)、(4)为程序中函数out1的4次递归调用。图5-6 程序执行过程及函数递归调用示意同样，我们也可以用动态图来描述程序执行过程及函数的

32、递归调用(见图5-7)。图5-7 程序执行的动态图由图5-6我们可以看出，函数out1的执行代码(即函数体中的语句)只有一组，函数out1的递归过程就是多次调用这组代码。由于第(4)次调用函数out1时，输入的字符是回车符“”，它使函数out1体中if语句的条件“ch!=n”为假，故第(4)次函数out1的调用不执行任何操作而结束并返回到主调函数(上一层调用它的out1)。从图5-7的动态图可知，函数out1每次调用就进入了新一层的out1，并且每一层都重新定义了局部变量ch，且上一层的ch和下一层的ch不是同一个变量。在哪一层执行，则哪一层的变量ch起作用；当返回到上一层时，下一层的变量ch

33、就不再存在(该层存储空间被系统收回)。递归函数的调用可以引起自身的进一步调用。产生进一步的调用时，主调函数并不释放自己的工作空间(即该函数定义的变量仍然存在)，而是为进一步调用的函数(可以是主调函数自身)开辟新的工作空间，这在动态图上表现为又产生了一个新的函数层并在其上建立新的变量如ch等。只有当最后一次调用的函数运行结束时，才撤消这最后一次函数调用时所建立的工作区，然后返回到它的调用者上一层函数的工作环境下继续执行。这样，每当一次函数调用结束时，就回收其对应的工作区，然后返回到它的主调函数(即上一层)处继续执行。这种建立与撤消的关系就如同先进后出的栈一样。反映到本题中的程序，就是函数out1

34、最后一次调用(4)最先结束，而最先调用(1)则最后结束(见图5-6)。因此程序的输出结果正好与读入的字符顺序abc相反：cba。注意，如果将函数out1中的调用语句“out1();”与输出语句“printf(%c,ch);”对调位置，则输出的结果正好与读入的字符顺序相同，读者可用动态图方法自行分析。例5.8 用递归方法计算n!。解 递归类似于递推，在遇到终止条件之前重复执行对对象的操作。但递归与递推不同的是，递归通过操作对象自身来最终形成终止条件。用递推法求解n的阶乘是基于公式：n!=123n实现的程序如下：#includevoid main()int i,n,s=1;scanf(%d,&n)

35、;if(n0)for(i=1;i=n;i+)s=s*i;printf(n!=%dn,s);elseprintf(Error!n);运行结果：5n!=120其中，递推操作是通过for语句的循环实现的。用递归法求解n的阶乘是基于公式：可以看出，这是一个递归的定义，其实现程序如下：#includeint fac(int n);void main()int n;scanf(%d,&n);if(n0)fac=fac(n-1)*n;return fac;解 该函数定义出错的情况如下：(1)不带参数的函数名(如fac)仅起名字的作用，它本身并不是变量，因此不能当作变量来使用，也即它不能独立地出现在函数体中的

36、任何地方。因此，fac出现在赋值号“=”左边以及作为return语句的返回值都是错误的。(2)我们知道，数学中阶乘计算当n等于0时n!等于1，即相当于要求函数fac(0)等于1。但是，条件语句if只考虑了n0的情况，当n等于0时则if语句相当于一个空语句。那么当递归调用到fac(0)时，其值是什么我们将无从知道。此外还要注意的是，在函数体内，函数名带上参数(如fac(n-1)出现在表达式中则意味着一次函数调用，它会返回一个结果值。但是它不允许出现在赋值号“=”的左边，因为赋值号“=”左边只能以变量形式出现而不能以值的形式出现。正确的函数fac定义见例5.8。例5.10 用递归函数求两个正整数m

37、和n的最大公约数，并计算当m和n分别为25和125时程序的运行结果。解 由第3章的最大公约数解法可知，求m和n的最大公约数等价于求n与m%n的最大公约数。这时可以把n当作新的m，而m%n当作新的n，即问题又变成了求新的m和n的最大公约数。按这种方法不断进行下去直到n等于0时的m即为最大公约数。由此可得到递归公式如下：其中，gcd(m,n)代表m和n的最大公约数。按照这个公式得到求解程序如下：#includeint gcd(int m,int n);void main()int m,n;printf(Input m、n:);scanf(%d%d,&m,&n);printf(gcd=%dn,gcd

38、(m,n);int gcd(int m,int n)if(n=0)return m;elsereturn(gcd(n,m%n);当m和n的输入值为25和125时，我们可以用类似数学推导的方法来得到最终的结果：此外，gcd函数的定义还可写为：int gcd(int m,int n)return n=0?m:gcd(n,m%n);例5.11 分析下面程序的输出结果。#includevoid fun(int k);void main()int w=5;fun(w);printf(n);void fun(int k)if(k0)fun(k-1);printf(%d,k);解 我们可以通过程序执行的动态

39、图分析得到程序的运行结果。程序执行的动态图见图5-8。图5-8 程序执行的动态图因此，该程序的输出为：012345。注意，如果函数fun改为如下形式：void fun(int k)if(k0)fun(k-1);printf(%d,k);则输出为：54321。例5.12 分析下面程序的输出结果。#includeint abc(int u,int v);void main()int a=24,b=16,c;c=abc(a,b);printf(%dn,c);int abc(int u,int v)int w;while(v)w=u%v;u=v;v=w;return u;解 程序执行的动态图见图5-9

40、。从图5-9的动态图可以看出，该程序的输出为：8图5-9 程序执行的动态图例5.13 分析下面程序的输出结果。#includeint fun(int x);void main()printf(%dn,fun(7);int fun(int x)int p;if(x=0|x=1)return 3;p=x-fun(x-2);return p;解 本题的函数fun在x等于0或1时返回3，而在其余情况下返回“x-fun(x-2);”的值，也即本题的递归算法如下：程序的输出结果为：fun(7)=7-fun(5)=7-(5-fun(3)=7-(5-(3-fun(1)=7-(5-(3-3)=7-5=2例5.1

41、4 实现用递归函数输出回文字符串，如输入abc，则输出abccba。解 从例5.7中我们已经知道：在函数out1的函数里，输出语句“printf(%c,ch);”在调用语句out1()之后时，输出的字符序列正好与输入的字符序列相反。如果将输出语句“printf(%c,ch);”调至调用语句out1()之前，则输出的字符序列正好与输入的字符序列相同。基于这一点，我们得到输出回文字符串的程序如下：#includevoid out1();void main()out1();printf(n);void out1()char ch;scanf(%c,&ch);if(ch!=n)printf(%c,ch

42、);out1();printf(%c,ch);如果输入abc，要求输出的回文字符串为：abcba，则只需当变量ch读入回车符n时回退一个字符即可。对应的程序如下：#includevoid out1();void main()out1();printf(n);void out1()char ch;scanf(%c,&ch);if(ch!=n)printf(%c,ch);out1();printf(%c,ch);elseprintf(b);/*回退一个字符位置*/例5.15 用递归函数求Fibonacci数列。解 Fibonacci的递归公式如下：因此，Fibonacci数列适合用递归函数求解。我

43、们用函数fib实现对Fi的求值，用主函数实现调用fib求出每一个Fi(i=1，2，n)的值，边计算边输出。编写的程序如下：#includeint fib(int n);void main()int i,n;printf(Input Fibonaccis number:);scanf(%d,&n);for(i=1;i=n;i+)printf(%6d,fib(i);if(i%5=0)printf(n);printf(n);int fib(int n)if(n=1|n=2)return 1;elsereturn fib(n-1)+fib(n-2);运行结果：Input Fibonaccis numb

44、er:20 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765从函数fib的定义可以看出，函数体完全是递归公式的C语言描述。因此，如果知道了递归公式，再设计递归函数则会容易得多。例5.16 利用递归函数输出如下所示的数字金字塔。解 在第3章中我们采用了二层循环实现数字金字塔图形的输出。在此我们通过递归函数来完成数字金字塔图形的输出：(1)由于数字金字塔图形左右对称，所以每一行上的数字输出由递归函数完成。(2)每行第一个数字的输出位置应顺序前移一个字符位置，故设i为循环控制变量来控制输出数字的个数。此外，每行输出的

45、起始位置由10-i来确定。程序设计如下：#includevoid generate(int m,int n);void main()int i,j;for(i=1;i=9;i+)for(j=1;j=10-i;j+)printf();/*输出两个空格*/generate(1,i);printf(n);void generate(int m,int n)if(m=n)printf(%2d,m);elseprintf(%2d,m);generate(m+1,n);printf(%2d,m);由于函数generate的函数体中存在这样的语句：printf(%d,m);generate(m+1,n);p

46、rintf(%d,m);因为它们是对称的，所以输出是对称的(例5.14的回文字符串输出也是如此)。主函数main在每次执行“generate(1,i);”语句则输出一行左右对称的数字序列，其后又执行一条“printf(n);”语句，即换一行。这两条语句合起来是输出一行左右对称的数字序列，然后回车并换到下一行。从for语句中循环控制变量i的变化范围可知一共要输出9行数字序列；而内层for循环则由j来控制在输出每一行在输出第一个数字之前应输出多少个空格，从而使输出的整个数字图形呈现为三角形。例5.17 要求用函数的嵌套调用实现s=13+23+n3。在主函数中由键盘输入n值且在主函数中输出s值，其他

47、功能用函数实现。解 本题要求用函数的嵌套调用来完成，因此定义函数func1完成累加功能，而定义func2完成求立方的功能；这样主函数main调用func1来计算各项的累加结果，而函数func1则调用函数func2求各个累加项。程序设计如下：#includevoid main()long func1(int n);int n;long sum;printf(Input n:);scanf(%d,&n);sum=func1(n);printf(s=%ldn,sum);long func1(int n)int func2(int m);int i;long sum1=0;for(i=1;i=n;i+

48、)sum1=sum1+func2(i);return(sum1);int func2(int m)return(m*m*m);运行结果：Input n:6s=441例5.18 输入年、月、日，求这一天是该年的第几天。要求用一个自定义函数完成闰年的判断，另一个自定义函数求指定月份的天数，而主函数则完成这一天是该年第几天的计算。解 在例4.8中我们用数组求某年某月某日是该年的第几天。在此，我们不用数组只用变量实现；并且用自定义函数leapyear和month_days分别实现对闰年的判断和求指定月份的天数；主函数main则调用函数month_days求出指定月份month之前的每一个月的天数并进行

49、累加，而month这个月的天数day则是在累加之前就赋给days了。程序设计如下：#includeint leapyear(int);int month_days(int,int);void main()int i,days,year,month,day;printf(Input year,month,day:n);scanf(%d,%d,%d,&year,&month,&day);days=day;for(i=1;imonth;i+)days=days+month_days(year,i);printf(Days of%d-%d-%d is:%dn,year,month,day,days);

50、int leapyear(int year)if(year%4=0&year%100!=0)|year%400=0)return 1;elsereturn 0;int month_days(int year,int month)if(month=4|month=6|month=8|month=11)return 30;elseif(month=2)if(leapyear(year)return 29;elsereturn 28;elsereturn 31;*5.6 递归转化为非递归研究递归转化为非递归研究 5.6.1 汉诺塔问题递归解法汉诺塔问题递归解法汉诺塔(Tower of Hanoi)问