第4章函数与程序结构

《第4章函数与程序结构》由会员分享，可在线阅读，更多相关《第4章函数与程序结构（81页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 函数与程序结构函数与程序结构 函数的定义、说明与调用函数的定义、说明与调用 函数之间参数传递规则函数之间参数传递规则 变量的存储类型与特性变量的存储类型与特性 函数递归的概念与执行过程函数递归的概念与执行过程 递归程序的编程方法递归程序的编程方法本本 章章 要要 点点24-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回模块化是结构化程序设计的基础。采用模模块化是结构化程序设计的基础。采用模块化程序设计有很多优越性块化程序设计有很多优越性：控制程序设计的控制程序设计的复杂性复杂性，提高软件的提高软件的可靠性可靠性，提高软件开发的提高软件开发的效率效率，提高软件

2、的提高软件的可维护性可维护性，提高程序的提高程序的重用性重用性。一、程序的模块化一、程序的模块化34-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回 函数函数函数函数是是是是C C程序的程序的程序的程序的最小最小最小最小单元。单元。单元。单元。C C程序是由程序是由程序是由程序是由一个主函数一个主函数一个主函数一个主函数以及若干个以及若干个以及若干个以及若干个函数函数函数函数构成构成构成构成主函数可以调用其它函数，其它函数可以相互调用主函数可以调用其它函数，其它函数可以相互调用主函数可以调用其它函数，其它函数可以相互调用主函数可以调用其它函数，其它函数可以相互调用l l例

3、如：例如：例如：例如：int int int int mainmainmainmain( )( )( )( ) printfprintfprintfprintf( ( ( (” ”ThisThisThisThis is C programn is C programn is C programn is C programn” ”);););); 函数函数函数函数mainmainmainmain调用了函数调用了函数调用了函数调用了函数printfprintfprintfprintf。printfprintfprintfprintf是一个库函数。是一个库函数。是一个库函数。是一个库函数。 为了完成

4、一个特定的任务，在程序开发中一般要为了完成一个特定的任务，在程序开发中一般要为了完成一个特定的任务，在程序开发中一般要为了完成一个特定的任务，在程序开发中一般要定义若干函数。定义若干函数。定义若干函数。定义若干函数。二、二、C C语言程序的结构语言程序的结构44-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数的一般形式函数的一般形式 数据类型数据类型 函数名函数名 ( ( 形式参数说明表形式参数说明表 ) ) 语句语句 1.1.数据类型数据类型是说明函数中是说明函数中returnreturn语句返回的值的类型，语句返回的值的类型，我们称这个数据类型为该我们称这个数据

5、类型为该函数的类型函数的类型2.2.函数名函数名是标识符，是函数定义中是标识符，是函数定义中唯一唯一不可省略的不可省略的3.3.形式参数说明表形式参数说明表是用逗号分隔开的一组变量及类型的是用逗号分隔开的一组变量及类型的声明名。声明名。( )( )不可省略。不可省略。形式参数表形式参数表中的参数简称为中的参数简称为形参形参4.4. 括起来的部分是函数体。括起来的部分是函数体。 不可省略不可省略三、函数的结构与定义三、函数的结构与定义54-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数定义实例函数定义实例 1. 1.语言中一个语言中一个最简单最简单的函数：的函数： d

6、ummydummy ( )( ) /* /* 函数名：函数名：dummy */dummy */ 没有没有数据类型数据类型说明和说明和形参说明形参说明，函数体函数体为空。为空。 2. 2.求阶乘函数求阶乘函数factofacto的定义。的定义。 long long factofacto ( (intint x x ) ) long y; long y; for (y=1; x0; -x) for (y=1; x0; -x) y *= x; y *= x; returnreturn (y); (y); 函数名函数名形式参数列表形式参数列表函函数数类类型型函数体函数体函数返回函数返回64-1 4-1

7、 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数定义实例函数定义实例 3. 3.求两个变量的最大值。求两个变量的最大值。 main( )main( ) intint a,b,c; a,b,c; printf(printf(”EnterEnter a,bn a,bn”);); scanf(scanf(”%d,%d%d,%d”,&a,&a, &b );, &b ); c = c = maxmax( a,b );( a,b ); printf(printf(”MaxMax = &d = &d”, c);, c); intint maxmax ( (intint x x , , y y

8、 ) /*max) /*max函数的定义函数的定义* */ / intint z; z; z z = = x x y y ? ? x x : : y y ; ; return ( z return ( z );); 函数调用函数调用74-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l从函数返回的两种方法从函数返回的两种方法用用returnreturn语句从语句从被调被调函数中退出函数中退出，返回返回调用调用它的程它的程序中（也称为序中（也称为主调主调函数）函数）；被调函数如果没有被调函数如果没有returnreturn语句，被调函数执行结束语句，被调函数执行结束遇到遇到

9、最外面最外面的的 ，返回主调函数。，返回主调函数。lreturnreturn的两重作用：的两重作用：控制程序从当前函数控制程序从当前函数( (被调用函数被调用函数) )中退出，返回到中退出，返回到调用函数调用函数中继续执行中继续执行；从从被调用函数被调用函数向向主调函数主调函数返回一个值返回一个值（称为（称为返回值返回值）。四、函数的返回值与函数的数据类型四、函数的返回值与函数的数据类型84-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l返回语句的格式与功能返回语句的格式与功能 格式格式格式格式1 1 1 1： returnreturnreturnreturn； 功能：

10、功能：功能：功能：将控制从将控制从将控制从将控制从被被被被调函数调函数调函数调函数返回返回返回返回到到到到主主主主调函数。调函数。调函数。调函数。 格式格式格式格式2 2 2 2： return return return return ( ( ( (表达式表达式表达式表达式）；）；）；）； 或或或或：return return return return 表达式表达式表达式表达式 ； 功能：功能：功能：功能：在被调函数中计算在被调函数中计算在被调函数中计算在被调函数中计算表达式表达式表达式表达式的值，将计算结果的值，将计算结果的值，将计算结果的值，将计算结果按照函数说明的按照函数说明的按照函

11、数说明的按照函数说明的函数类型函数类型返回返回到到主主调函数，并将控调函数，并将控制返回主调函数。制返回主调函数。 例如：通过函数例如：通过函数maxmax求变量求变量a a和和b b的最大值。的最大值。 c =c = max max(a,b);(a,b);94-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l在调用函数之前，要先进行函数在调用函数之前，要先进行函数说明说明“说明说明”与与“定义定义” 的区别：的区别：n“说明说明”就是就是说明说明函数返回值的类型。函数返回值的类型。n“定义定义”是给出函数的程序体。是给出函数的程序体。五、函数说明五、函数说明104-1

12、4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数说明的一般形式函数说明的一般形式数据类型数据类型 函数名函数名（形参说明表）（形参说明表）；数据类型必须与函数定义时的函数类型一致。数据类型必须与函数定义时的函数类型一致。函数说明函数说明与与函数定义的首部函数定义的首部唯一区别：函数说唯一区别：函数说明语句的明语句的()()之后之后必须必须有有分号分号，而函数定义头部而函数定义头部的的()()之后之后没有没有分号。分号。五、函数说明五、函数说明114-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数的调用形式函数的调用形式 函数名函数名（ 实际参数

13、表实际参数表 ）；）； 函数调用时函数调用时实际参数表实际参数表中给出的数据简称为中给出的数据简称为实参实参。 实参实参的的数量数量、类型类型和和排列顺序排列顺序必须与必须与函数定函数定义义时形式参数表中形参的时形式参数表中形参的数量数量、类型类型和和排列顺排列顺序序一致一致，不允许不允许任意改变。任意改变。六、函数调用六、函数调用124-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l函数调用的过程函数调用的过程在一个函数中调用另一个函数时，程序将在一个函数中调用另一个函数时，程序将控控制制从调用函数处从调用函数处转移转移到被调用函数，并到被调用函数，并执行被执行被调用

14、函数调用函数。在执行完在执行完被调用函数被调用函数的所有语句或者遇到的所有语句或者遇到returnreturn语句时，程序的控制要语句时，程序的控制要返回返回到调用函数到调用函数中中原来原来调用函数的地方继续执行调用函数的地方继续执行。六、函数调用六、函数调用134-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回l例例C4-1.CC4-1.C：用函数用函数factofacto计算计算 m m 阶乘。阶乘。main( )main( ) intint m; long mm; m; long mm; longlong factofacto( ( int x)int x); ;

15、scanf(%dscanf(%d, &m);, &m); mm mm = = factofacto( ( m m ) ); ; printf(%dprintf(%d!=%ld.n, m, mm);!=%ld.n, m, mm); longlong factofacto ( (intint x x ) ) long y; long y; for ( y=1; x0; -x ) y *= x;for ( y=1; x0; -x ) y *= x; return return (y);(y); /* /* 函数定义函数定义 */ */* /* 函数说明函数说明 */ */ /* /* m:m:实参数

16、实参数, ,调用函数调用函数factofacto， 返回值送入变量返回值送入变量mmmm中中 */ */函数执行过程函数执行过程 main ( ) mm = facto( m );facto ( x ) return (y );调用调用返回返回144-1 4-1 函数的定义、说明、调用与返回函数的定义、说明、调用与返回七、函数的嵌套调用七、函数的嵌套调用mainmainmainmain函数函数函数函数 调用函调用函调用函调用函数数数数 A;A;A;A; 函数函数函数函数 A A A A 调用函数调用函数调用函数调用函数 B B； 函数函数函数函数 B B B B 调用调用调用调用返回返回返回返

17、回154-2 4-2 函数间参数传递函数间参数传递l在不同的函数之间传递数据，有三种方式：在不同的函数之间传递数据，有三种方式：参参 数：数：通过通过形式参数形式参数和和实际参数实际参数返返 回回 值值：用：用returnreturn语句返回计算结果语句返回计算结果全局变量：全局变量：外部变量外部变量函数间数据传递方式函数间数据传递方式164-2 4-2 函数间参数传递函数间参数传递l函数参数的传递规则函数参数的传递规则值传递值传递 值传递值传递：在调用函数时，将：在调用函数时，将实参实参变量的变量的值值取出来，复制给取出来，复制给形参形参变量，使变量，使形参形参变量在变量在数数值值上与上与实

18、参实参相等相等。 在函数在函数内部内部使用从实参中复制来的使用从实参中复制来的值值进行进行处理。处理。 中的实参可以是一个中的实参可以是一个表达式表达式，调用时先，调用时先计算表达式的计算表达式的值值，再，再将结果将结果（值值）复制到形参复制到形参变量变量中。中。174-2 4-2 函数间参数传递函数间参数传递l例例C4-2.CC4-2.C：用函数交换两个变量的值。用函数交换两个变量的值。 main ( )main ( ) intint a, b; a, b; a=5; b=10; /* a=5; b=10; /* 说明两个变量并赋初值说明两个变量并赋初值 */ */ printfprintf

19、 ( (brfortbrfort swap a=%d, b=%dn, a, b); swap a=%d, b=%dn, a, b); swap(swap(a a, , b b);); /* /* 用变量用变量a a和和b b作为实际参数调用函数作为实际参数调用函数 */ */ printfprintf (after swap a=%d, b=%dn, a, b); (after swap a=%d, b=%dn, a, b); swapswap ( ( x x, , y y) ) intint x, y; /* x, y; /* 借助临时变量交换两个形参变量的值借助临时变量交换两个形参变量的值

20、 */ */ intint temptemp; ; temptemp=x; x=y; y=x; x=y; y=temptemp; ; printfprintf (in swap x=%d, y=%dn, x, y); (in swap x=%d, y=%dn, x, y); 184-2 4-2 函数间参数传递函数间参数传递main main 函数函数 a a = 5;= 5; b b = 10;= 10; swap(swap(a a, , b b);); swapswap ( ( x x, , y y ) ) 函数函数 temptemp = = x x; ; 语句语句 x x = = y y;

21、 ; 语句语句 y y = = temptemp; ; 语句语句 510实参变量实参变量 a实参变量实参变量 b510形参变量形参变量 x形参变量形参变量 y变量变量 temp复制复制复制复制 temp = x x = y y = temp105 5swap函数的执行过程和各个变量的变化过程函数的执行过程和各个变量的变化过程 调用调用swap函数函数调用调用swap函数函数调用调用swap函数函数执行执行swap函数函数执行执行swap函数函数执行执行swap函数函数194-2 4-2 函数间参数传递函数间参数传递l l值传递方式的特点值传递方式的特点 值传递值传递方式方式也称也称“数据复制数

22、据复制”方式。方式。 函数间函数间形参形参变量与变量与实参实参变量的变量的值值的传递过程类似的传递过程类似于日常生活中的于日常生活中的“复印复印”操作。操作。值传递的优点值传递的优点值传递的优点值传递的优点 值传递的优点在于：被调用的函数不可能改变调用值传递的优点在于：被调用的函数不可能改变调用值传递的优点在于：被调用的函数不可能改变调用值传递的优点在于：被调用的函数不可能改变调用函数中变量的值，而只能改变它的局部的临时副本。这函数中变量的值，而只能改变它的局部的临时副本。这函数中变量的值，而只能改变它的局部的临时副本。这函数中变量的值，而只能改变它的局部的临时副本。这样就可以避免被调用函数的

23、操作，对主调函数中的变量样就可以避免被调用函数的操作，对主调函数中的变量样就可以避免被调用函数的操作，对主调函数中的变量样就可以避免被调用函数的操作，对主调函数中的变量可能产生的副作用。可能产生的副作用。可能产生的副作用。可能产生的副作用。值传递的缺点值传递的缺点 在值传递方式下，每个形式参数仅能传递一个数据，在值传递方式下，每个形式参数仅能传递一个数据，在值传递方式下，每个形式参数仅能传递一个数据，在值传递方式下，每个形式参数仅能传递一个数据，当需要在函数之间传递大量数据时，值传递方式显然不当需要在函数之间传递大量数据时，值传递方式显然不当需要在函数之间传递大量数据时，值传递方式显然不当需要

24、在函数之间传递大量数据时，值传递方式显然不适用。适用。适用。适用。20l数组与函数的关系数组与函数的关系在函数之间传递数组中的在函数之间传递数组中的单个元素单个元素在函数之间传递在函数之间传递整个数组整个数组l在函数之间传递数组中的元素在函数之间传递数组中的元素数数组组中中的的元元素素具具有有一一般般变变量量的的特特点点，可可以以象象在在函函数数之之间间传传递递一一般般变变量量那那样样，在在函函数数之之间间也也可可以以进进行行值传递值传递或或地址传递地址传递。 向函数传递一个数组元素的向函数传递一个数组元素的值值：实际参数实际参数为为数组元素数组元素( ( ak )ak )，形式参数形式参数为

25、为一般变量一般变量( ( x )x ) 向函数出传递一个数组元素的向函数出传递一个数组元素的地址地址：实际参数实际参数为为数组元素的地址数组元素的地址( &( &ak )ak )，形式参数形式参数为为指针变量指针变量( *( *pxpx ) )4-3 4-3 数组与函数数组与函数21l向函数传递数组元素的值向函数传递数组元素的值例例C4-4.C：求满足条件的三位正整数求满足条件的三位正整数 abc=a!+b!+c!。 main ( )main ( ) int i, j, k, m, a3, int i, j, k, m, a3, flagflag; ;/* /* flagflag标志变量标志变

26、量 */ */forfor ( j=101; j ( j=101; j6 600; j+ )00; j+ ) /* /* 用穷举法用穷举法 */ */ for for ( ( k=j, i=0k=j, i=0; ; i3i3; ; i+, k=k/10i+, k=k/10 ) ) /* /* 分解整数分解整数 */ */ai=k%10;ai=k%10; forfor ( ( flag=1flag=1, m=i=0; i3 & , m=i=0; i6 ) ( ai6 ) flagflag = = 0 0; ; elseelse m += fac( m += fac( aiai ); ); /*

27、/* 实参实参 */ */ ifif ( ( flagflag & m & m=j )j )printf(”%d=%d!+%d!+%d!n”,m,a2,a1,a0);printf(”%d=%d!+%d!+%d!n”,m,a2,a1,a0); fac ( int fac ( int m m ) ) /* /* 求求m!m!。形参为一般变量形参为一般变量 */ */ int n;int n;for ( n=1; m0 ; m- ) n *= m;for ( n=1; m0 ; m- ) n *= m;return (n);return (n); 4-3 4-3 数组与函数数组与函数- -传递数组元

28、素的值传递数组元素的值例例例例C4-4C4-4C4-4C4-422l在函数之间传递整个一维数组在函数之间传递整个一维数组实际参数实际参数用用数组名数组名。形形式式参参数数用用数数组组名名，但但在在数数组组名名的的后后面面是是一对一对空的空的方括号方括号 。 说明说明形形参参数数组组的的大大小小由由调调用用函函数数的的实实参参数数组组的的大小决定。大小决定。这这种种用用数数组组名名作作为为实实际际参参数数传传递递方方法法，实实际际是是在在函函数数之之间间传传递递整整个个数数组组的的首首地地址址，并并没有没有复制整个数组。复制整个数组。 即即调调用用函函数数和和被被调调函函数数使使用用的的是是同同

29、一一个个数组。数组。4-3 4-3 数组与函数数组与函数- -传递一维数组传递一维数组23l例例C4-5.CC4-5.C：求给定一维数组求给定一维数组 a a 中各元素的平均值。中各元素的平均值。main ( )main ( ) float average( ); float average( ); static float static float a10a10 = = 1, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9; 1, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9; printfprintf (Th

30、e average array is %fn, average( (The average array is %fn, average( a a, 10); , 10); float average ( float float average ( float a a , , intint n ) n ) /* n /* n 为数组为数组 a a 中元素的个数中元素的个数 */ */ intint i; float sum=0; i; float sum=0; for for ( i=0; in; i+ ) ( i=0; in; i+ ) /* /* 求数组求数组a a中中n n个元素的累加和个

31、元素的累加和 */ */ sum += sum += aiai; ; return ( sum/n ); return ( sum/n ); /* /* 返回平均值返回平均值 */ */ 4-3 4-3 数组与函数数组与函数- -传递一维数组传递一维数组例例例例C4-5C4-5C4-5C4-5在被调用函数中可以通过下标正常使用数组在被调用函数中可以通过下标正常使用数组24l在函数之间传递多维数组在函数之间传递多维数组实际参数实际参数用用数组名数组名。形形式式参参数数用用数数组组名名。在在数数组组名名的的后后面面可可直直接接说说明明形形参参数数组组的的大大小小，也也可可以以采采用用省省略略形形式

32、式，但但只只能能省略第一维的大小省略第一维的大小说明。说明。l例如：例如： 将二维数组作为形式参数，可说明为：将二维数组作为形式参数，可说明为： intint a34; a34; 或或 intint a 4; a 4;将三维数组作为形式参数，可说明为：将三维数组作为形式参数，可说明为： intint a334; a334; 或或 intint a 34; a 34;不能说明为：不能说明为： intint a 4; a 4; intint a3 4; a3 4; intint a33 ; a33 ; intint a ; a ;4-3 4-3 数组与函数数组与函数- -传递多维数组传递多维数组2

33、5l例例C4-6.C：给定年月日，计算它是这一年的第几天。给定年月日，计算它是这一年的第几天。main( )main( ) static static intint day_tab2day_tab21313 = = 0, 31, 0, 31, 2828, 31, 30, 31,30,31,31,30,31,30,31, 31, 30, 31,30,31,31,30,31,30,31 , , 0, 31, 0, 31, 2929, 31, 30, 31,30,31,31,30,31,30,31, 31, 30, 31,30,31,31,30,31,30,31 ; ;intint y,m,d; y

34、,m,d;scanfscanf (%d%d%d, &y, &m, &d); (%d%d%d, &y, &m, &d);printf(%dnprintf(%dn, day_of_year( , day_of_year( day_tabday_tab, y, m, d) );, y, m, d) ); day_of_year ( day_of_year ( day_tabday_tab, year, month, day ), year, month, day ) intint day_tab day_tab 1313 ; ; /* /* 形参：二维数组形式的天数表形参：二维数组形式的天数表 */

35、 */ intint year, month, day; year, month, day; intint i,j; i,j;i = ( year%4i = ( year%4=0 & year%100!=0 ) | year%4000 & year%100!=0 ) | year%400=0 ;0 ; /* /* 判定为闰年还是平年，判定为闰年还是平年，i=0i=0为平年，为平年，i=1i=1为闰年为闰年 */ */forfor ( j=1; jmonth; j+ )( j=1; j0 ) 0 ) printf(%c,chprintf(%c,ch); ); 建立一个建立一个voivoid d型

36、的函数：重复输出型的函数：重复输出 n n 个字符个字符 chch284-4 4-4 voidvoid类型函数类型函数main( )main( ) intint m,n,i;m,n,i; voidvoid ptpt( ( ); ); /* /* 函数说明函数说明 * */ / scanfscanf(%d(%d, &n);, &n); for for (i=n-1; i=-n+1; i(i=n-1; i=-n+1; i-) ) /* /* 2 2N-1N-1 行，从行，从 - -N+1N+1 到到 N-1N-1 */ */ m = (i0) ? i : -i; m = (i0) ? i : -i

37、; pt (m, pt (m, ); ); /* /* 输出空格，定位输出空格，定位 * * 的位置的位置 */ */ ifif ( i ( i = n-1 | i n-1 | i = -n+1 )-n+1 ) pt(n, pt(n,* *);); pt(1, pt(1,nn); ); /*/* 输出第一行和最后一行输出第一行和最后一行 */ */ else else pt(1, pt(1, * *); ); /*/* 输出其余行的第一个输出其余行的第一个 * * */ */ pt(3*n-2*m-4pt(3*n-2*m-4, , ); ); /*/* 输出其余行的中间的空格输出其余行的中间的

38、空格 */ */ pt(1, pt(1, * *); ); /*/* 输出其余行的最后一个输出其余行的最后一个 * * */ */ pt(1pt(1, , nn);); /* /* 结束结束 for for 循环循环 */ */ 例例例例C4-8C4-8C4-8C4-8294-5 4-5 变量的存储类型与作用域变量的存储类型与作用域l变量的数据类型变量的数据类型 char 型型 int 型型 float 型型 double 型型总结总结总结总结：数据类型数据类型数据类型数据类型决定为变量分配的内存单元的决定为变量分配的内存单元的决定为变量分配的内存单元的决定为变量分配的内存单元的长度长度长度长

39、度，数据的，数据的，数据的，数据的存在存在存在存在 形式。形式。形式。形式。（从程序设计角度，决定了（从程序设计角度，决定了（从程序设计角度，决定了（从程序设计角度，决定了可以表示的可以表示的可以表示的可以表示的数的范围数的范围数的范围数的范围）问题问题：1. 何时何时为变量分配内存单元为变量分配内存单元？ 2. 变量在程序数据空间的什么变量在程序数据空间的什么位置位置？ 3. 变量的有效变量的有效作用范围作用范围？30l变量的变量的作用域作用域是指变量使用的有效范围是指变量使用的有效范围一个函数一个函数一个文件一个文件一个程序一个程序l变量存贮类型有变量存贮类型有四种四种-存贮类型说明符存贮

40、类型说明符自动变量（自动变量（autoauto）静态变量（静态变量（staticstatic）外部变量（外部变量（externextern）寄存器变量（寄存器变量（registerregister）l变量说明的一般形式变量说明的一般形式存贮类型说明符存贮类型说明符 类型说明符类型说明符 变量名称；变量名称；4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域314-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -自动变量自动变量l自动变量是最常见的一类变量自动变量是最常见的一类变量 例如语句：例如语句：auto auto intint a; a; auto float p

41、i; auto float pi; 说明符说明符“autoauto”可以可以省略省略。按照这种默认。按照这种默认的规定，以前所使用的全部变量都是自动变量。的规定，以前所使用的全部变量都是自动变量。l说明说明 1. 1.说明自动变量必须在一个说明自动变量必须在一个函数体的内部函数体的内部。 2. 2.函数的函数的形参形参也是自动变量。也是自动变量。324-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -自动变量自动变量l作用域作用域 自动变量的自动变量的作用域作用域是在所说明的是在所说明的函数内部函数内部。实。实质上是一个函数内部的质上是一个函数内部的局部变量局部变量。l生存期生存

42、期 只有在函数被调用时才存在，从函数中返回时只有在函数被调用时才存在，从函数中返回时即消失，它们的值也仅限于说明它的函数，在其它即消失，它们的值也仅限于说明它的函数，在其它的函数中的函数中不能不能存取。存取。 由于自动变量具有局部性，所以在两个由于自动变量具有局部性，所以在两个不同的不同的函数函数中可以分别使用中可以分别使用同名的变量同名的变量而互不影响。而互不影响。334-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -自动变量自动变量l例例4-9.C4-9.C：分析程序打印结果：分析程序打印结果： # #include include main( )main( ) intin

43、t x x = 1; /* = 1; /* 函数函数mainmain中的自动变量中的自动变量x */x */ void f1( ), f2( ); void f1( ), f2( ); f1( ); f1( ); f2(x); /* f2(x); /* 分别调用函数分别调用函数f1f1和和f2 */f2 */ printfprintf (x=%dn, x); (x=%dn, x); void f1 ( void )void f1 ( void ) intint x x = 3; /* = 3; /* 函数函数f1f1中的自动变量中的自动变量x */x */ printfprintf (x=%d

44、t, x); (x=%dt, x); voidvoid f2 ( x ) f2 ( x ) intint x x; /* ; /* 函数函数f2f2中的形参中的形参x x也是自动变量也是自动变量 */ */ printfprintf (x=%dt, +x); /* x (x=%dt, +x); /* x加加1 */1 */ 例例例例C4-9C4-9C4-9C4-9344-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -寄存器变量寄存器变量l寄存器变量与其他类型变量的区别寄存器变量与其他类型变量的区别 将变量定义为寄存器变量将变量定义为寄存器变量可以提高程序运行速可以提高程序运行速

45、度度。 由于受硬件寄存器长度的限制，所以寄存器变由于受硬件寄存器长度的限制，所以寄存器变量只能是量只能是charchar、intint或或指针型指针型。 寄存器说明符寄存器说明符只能只能用于说明用于说明函数函数中的中的变量变量和函和函数的数的形参形参，外部变量外部变量或或静态变量静态变量不能是不能是registerregister。 寄存器是与机器硬件密切相关的，不同的计算寄存器是与机器硬件密切相关的，不同的计算机，寄存器的数目不一样，通常为机，寄存器的数目不一样，通常为2 2到到3 3个，若在一个，若在一个函数中说明多于个函数中说明多于2 2到到3 3个寄存器变量，编译程序会个寄存器变量，编

46、译程序会自动地将它们变为自动变量。自动地将它们变为自动变量。354-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量l定义在所有函数之定义在所有函数之外外的的全局变量全局变量。 可被所有的函数访问，函数之间可被所有的函数访问，函数之间可通过外可通过外部变量传递数据部变量传递数据。 intint x x = 0;= 0; /* /* 说明外部变量说明外部变量x */x */ main main ( ) ( ) . . 364-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量l例例C4-10.CC4-10.C: : 分析程序运行结果分析程

47、序运行结果intint x x = 0; = 0; /* /* 说明外部变量说明外部变量x */x */main ( )main ( ) void void addoneaddone( ), ( ), subonesubone( );( ); x = 1; x = 1; /* /* 为外部变量为外部变量x x赋值赋值 */ */ printfprintf (x begins is %dn, x); (x begins is %dn, x); addoneaddone( ); ( ); subonesubone( ); ( ); subonesubone( );( );addoneaddone(

48、 );( );addoneaddone( );( ); printfprintf (x winds up as %dn, x); (x winds up as %dn, x); void void addoneaddone ( void ) ( void ) x x +; +; /* /* 使用外部变量使用外部变量x */x */ printfprintf (add 1 to make %dn, x); (add 1 to make %dn, x); void void subonesubone ( void ) ( void ) x x -; ; /* /* 使用外部变量使用外部变量x */

49、x */ printfprintf ( (substractsubstract 1 to make %dn, x); 1 to make %dn, x); 37l外部变量与自动变量的区别外部变量与自动变量的区别1.1.外外部部变变量量在在编编译译时时由由编编译译系系统统在在数数据据段段分分配配永永久久性的存储空间性的存储空间；自自动动变变量量则则是是在在函函数数每每次次被被调调用用时时才才在在堆堆栈栈中中分分配配临时性的存储空间临时性的存储空间。识。识动态分配动态分配产生的。产生的。2.2.外外部部变变量量如如果果没没有有赋赋初初值值，则则为为0 0；自自动动变变量量没没有有赋初值，则值赋初值

50、，则值不定不定。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量38l实例实例程序程序1 1： # #include include main ( )main ( ) intint x; x; /* /* 自动变量自动变量 */ */ printfprintf ( (”x=%dx=%d”, x):, x): 程序程序2 2： # #include include intint x;x; /* /* 外部变量外部变量 */ */main ( )main ( ) printfprintf ( (”x=%dx=%d”, x):, x): 4-5 4-5 变量的存储类

51、型与作用域变量的存储类型与作用域- -外部变量外部变量39l在不同的文件中使用在不同的文件中使用外部变量外部变量和和函数函数l对对于于大大系系统统而而言言，可可将将一一个个程程序序分分割割为为多多个个文文件件，通过通过工程文件工程文件，可以将整个系统连为一个整体。，可以将整个系统连为一个整体。l一个函数要在一个文件中，不能分割。一个函数要在一个文件中，不能分割。l如如果果外外部部变变量量的的说说明明与与使使用用在在同同一一个个文文件件中中，则则在在该文件的函数中使用外部变量时，可直接使用。该文件的函数中使用外部变量时，可直接使用。l当当外外部部变变量量的的说说明明与与使使用用在在不不同同的的文

52、文件件，要要使使用用在在其其它它文文件件中中说说明明的的外外部部变变量量，就就必必须须在在使使用用该该外外部部变变量量之之前前，使使用用“externextern”存存储储类类型型说说明明符符进进行行变变量量“外部外部”说明。说明。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量40l在不同的文件中使用在不同的文件中使用外部变量外部变量和和函数函数( (续续) )lexternextern仅仅仅仅是是说说明明变变量量是是“外外部部的的”，以以及及它它的的类类型型，并并不不真真正正分分配配存存储储空空间间。在在将将若若干干个个文文件件连连接接生生成成一一个个完完

53、整整的的可可运运行行程程序序时时，系系统统会会将将不不同同文文件件中中使使用用的的同同一一外外部部变变量量连连在在一一起起，使使用用同同一一个个系系统统分配的存储单元。分配的存储单元。l当当被被调调用用的的函函数数在在另另一一个个文文件件中中时时，在在调调用用该该函函数数时时，无无论论被被调调用用的的函函数数是是什什么么类类型型，都都必必须须用用externextern说明符说明被调用函数是说明符说明被调用函数是“外部函数外部函数”。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量41l例例C4-10.CC4-10.C: : 下列程序由两个文件组成，请分析运行

54、结果。下列程序由两个文件组成，请分析运行结果。/* /* 文件一文件一 */ */ intint x x = 10; /* = 10; /* 定义外部变量定义外部变量x x和和y */y */ intint y y = 10; = 10; void add ( void ) void add ( void ) y y = 10+x; = 10+x; x x *= 2; *= 2; main ( ) main ( ) externextern void void subsub( ); /* ( ); /* 说明说明subsub是是voidvoid型的外部函数型的外部函数 */ */ x x +=

55、 5; += 5; add( ); sub( ); /* add( ); sub( ); /* 分别调用函数分别调用函数 */ */ printfprintf (x=%d; y=%dn, x, y); (x=%d; y=%dn, x, y); /* /* 文件二文件二 */ */ void void subsub ( void ) /* ( void ) /* 函数函数subsub定义在另一个文件中定义在另一个文件中 */ */ externextern intint x x; /* ; /* 说明在另一个文件中的外部变量说明在另一个文件中的外部变量x */x */ x x -= 5;-= 5

56、; 4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -外部变量外部变量42l静态变量的说明是在变量说明前加静态变量的说明是在变量说明前加 staticstatic。l静态变量有两种：静态变量有两种：外部外部静态变量静态变量，内部内部静态变量静态变量。l静静态态变变量量与与外外部部变变量量的的相相同同点点：具具有有永永久久的的存存储储空空间；由编译器进行初始化。间；由编译器进行初始化。l外外部部静静态态变变量量与与外外部部变变量量的的区区别别：外外部部静静态态变变量量仅仅仅仅在在定定义义它它的的一一个个文文件件中中有有效效，而而外外部部变变量量作作用用于于整个程序。整个程序。l内

57、内部部静静态态变变量量与与外外部部静静态态变变量量的的区区别别：内内部部静静态态变变量作用于定义它的当前函数。量作用于定义它的当前函数。l内内部部静静态态变变量量与与自自动动变变量量的的区区别别：内内部部静静态态变变量量占占用用永永久久性性的的存存储储单单元元，在在每每次次调调用用的的过过程程中中能能够够保保持数据的连续性；自动变量不能。持数据的连续性；自动变量不能。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -静态变量静态变量43l 例例C4_4401C4_4401.C: .C: 分析下列程序的运行结果。分析下列程序的运行结果。/* /* 文件一文件一 */ */ sta

58、tic static intint x x = 2; /* = 2; /* 说明外部静态变量说明外部静态变量x */x */ intint y y = 3; /* = 3; /* 说明外部变量说明外部变量y */y */ extern void add2( ); /* extern void add2( ); /* 说明外部函数说明外部函数add2 */add2 */ void add1( ); void add1( ); main ( )main ( ) add1( ); add2( ); add1( ); add2( ); add1( ); add2( ); add1( ); add2(

59、); printfprintf (x=%d; y=%dn, (x=%d; y=%dn, x x, , y y);); void add1( void ) /* void add1( void ) /* 定义函数定义函数add1 */add1 */ x x += 2; += 2; y y += 3; += 3; printfprintf (in add1 x=%dn, (in add1 x=%dn, x x);); /* /* 文件二文件二 */ */ static static intint x=10; /* x=10; /* 说明外部静态变量说明外部静态变量x */x */ void add

60、2( void ) /* void add2( void ) /* 定义函数定义函数add2 */add2 */ extern extern intint y y; /* ; /* 说明另一个文件中的外部变量说明另一个文件中的外部变量y */y */ x += 10; x += 10; y y += 2; += 2; printfprintf (in add2 x=%dn, (in add2 x=%dn, x);x); 4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -静态变量静态变量44l例例C4_4402.CC4_4402.C: : 分析下列程序的运行结果。分析下列程序的运

61、行结果。 # #include include main ( ) main ( ) void inc1( ), inc2( ); void inc1( ), inc2( ); inc1( ); inc1( ); inc1( ); inc1( ); inc1( ); inc1( ); inc2( ); inc2( ); inc2( ); inc2( ); inc2( ); inc2( ); void inc1( ) void inc1( ) intint x x = 0; = 0; /* /* 说明自动变量说明自动变量 x x 并赋初值并赋初值 */ */ x x+;+; printfprint

62、f (in inc1 x=%dn, (in inc1 x=%dn, x x);); void inc2( ) void inc2( ) static static intint x x=0; =0; /* /* 说明内部静态变量说明内部静态变量 x x 并初始化并初始化 */ */ x x+;+; printfprintf (in inc2 x=%dn, (in inc2 x=%dn, x);x); 4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -静态变量静态变量45l变量初始化与赋初值的区别变量初始化与赋初值的区别 对对于于自自动动变变量量和和寄寄存存器器变变量量：变变量量

63、的的初初始始化化要要在在运运行行时时，由由赋赋值值操操作作进进行行。在在刚刚进进入入一一个个函函数数时时，函函数数中中说说明明的的自自动动变变量量和和寄寄存存器器变变量的量的值值是是不定不定的。的。 对于外部变量和静态变量，变量的初始化对于外部变量和静态变量，变量的初始化工作是工作是由编译由编译系统控制。在编译程序时，系统系统控制。在编译程序时，系统为外部变量和静态变量分配永久性的存储单元为外部变量和静态变量分配永久性的存储单元并并进行初始化进行初始化。在运行程序时，外部变量和静。在运行程序时，外部变量和静态变量的初值是一定的。态变量的初值是一定的。4-5 4-5 变量的存储类型与作用域变量的

64、存储类型与作用域- -变量初始化变量初始化46l在在函函数数中中说说明明自自动动变变量量或或寄寄存存器器变变量量时时，可可使用这样的语句：使用这样的语句： main ( )main ( ) intint x=3; x=3; registerregister intint y=4; y=4; . . 这这不不是是给给自自动动变变量量或或寄寄存存器器变变量量初初始始化化，是是在在运运行行时时执执行行赋赋值值操操作作为为自自动动变变量量或或寄寄存存器变量器变量赋初值赋初值。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -变量初始化变量初始化47l在在函函数数中中说说明明外外部部变变

65、量量或或静静态态变变量量时时，可可使使用用这这样样的的语句：语句： intint x1=2, x2; x1=2, x2; static static intint y=3; y=3; main ( ) main ( ) static static intint z=10; z=10; . . 这这时时编编译译程程序序会会自自动动为为 x1x1、x2x2、y y 和和 z z 进进行行初初始化。不需要程序在运行时再做赋值操作了。始化。不需要程序在运行时再做赋值操作了。对对于于象象变变量量x2x2在在说说明明时时没没指指定定初初值值的的外外部部变变量量或或静态变量，编译系统自动将初值置为静态变量，

66、编译系统自动将初值置为0 0。4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -变量初始化变量初始化48 性性 能能 自动变量自动变量 外部变量外部变量 外部静态外部静态 内部静态内部静态 寄存器变量寄存器变量记忆能力记忆能力 无无 有有 有有 有有 无无多个函数共享多个函数共享 否否 可可 可可 否否 否否在不同文件共享性在不同文件共享性 否否 可可 否否 否否 否否未显示赋值的取值未显示赋值的取值 不定不定 不定不定变量初始化变量初始化 程序控制程序控制 编译器编译器 编译器编译器 编译器编译器 程序控制程序控制数组与结构初始化数组与结构初始化 有有 可可 可可 可可 否否

67、作用域作用域 当前函数当前函数 整个程序整个程序 文件文件 函数函数 当前函数当前函数4-5 4-5 变量的存储类型与作用域变量的存储类型与作用域- -存储类型小结存储类型小结49l递归的概念递归的概念递递归归是是一一种种常常用用的的程程序序设设计计技技术术，在在一一个个程程序序中中，若若存存在在程程序序自自己己调调用用自自己己的的现现象象就就是构成了递归。是构成了递归。如如果果函函数数funAfunA在在执执行行过过程程又又调调用用函函数数funAfunA自己，则称函数自己，则称函数funAfunA 为为直接递归直接递归。如如果果函函数数funAfunA在在执执行行过过程程中中先先调调用用函

68、函数数funBfunB，函函数数funBfunB在在执执行行过过程程中中又又调调用用函函数数funAfunA，则称函数则称函数funAfunA为间接递归。为间接递归。4-6 4-6 递归递归50 例例C4-11.CC4-11.C：用递归函数求用递归函数求n! n! 。已知：已知：n n阶乘的阶乘的递归定义递归定义为：为：n! = n! = 1 1 当当 n = 1 n = 1 时时n! = n * (n-1)! n! = n * (n-1)! 当当 n 1 n 1 时时 main ( )main ( ) intint n, p; n, p; printfprintf (N=?); (N=?);

69、 scanfscanf (%d, &n); (%d, &n); p = p = factofacto (n); (n); printfprintf (%d!=%dn, n, p); (%d!=%dn, n, p); factofacto ( n ) ( n ) intint n; n; intint r; r; if ( n if ( n = 1 ) r = 1; 1 ) r = 1; else r = n * else r = n * factofacto(n-1); (n-1); /*/* 递归调用递归调用 */*/ return (r);return (r); 4-6 4-6 递归递归-

70、 -递归程序的执行过程递归程序的执行过程51主函数主函数 第一次第一次调用调用 第二次第二次 第三次第三次 第四次第四次 n=4 n=4 p=facto(4) p=facto(4) 调用调用 n=4n=4 r=4*r=4*factofacto(3)(3) 调用调用 n=3n=3 r=3*r=3*factofacto(2)(2) 调用调用 n=2n=2 r=2*r=2*factofacto(1)(1) n=1n=1 returnreturn( (1 1) ) 返回返回 r=2* 1r=2* 1 =2 =2 returnreturn( (2 2) ) 返回返回 r=3* 2r=3* 2 =6 =6

71、 returnreturn( (6 6) ) 返回返回 r=4* 6r=4* 6 =24 =24 returnreturn( (2424) ) 返回返回 p=24 p=24 打印打印 24 24factofacto ( n ) ( n ) intint n; n; intint r; r; if (n=1) if (n=1) r = 1; r = 1; else else r=n* r=n*factofacto(n-1);(n-1); return (r); return (r); 递归递归返回返回过程过程递归递归调用调用过程过程4-6 4-6 递归递归- -递归程序的执行过程递归程序的执行过

72、程524-6 4-6 递归递归- -递归程序的执行过程递归程序的执行过程递归调用的执行过程递归调用的执行过程递归调用的执行过程递归调用的执行过程factofacto ( n ) ( n ) intint n; n; intint r;r; if ( n if ( n = 1 ) 1 ) r r = 1; = 1; else else r r = n * = n * factofacto(n-1); (n-1); return return (r);(r); facto facto facto facto ( ( ( ( intintintint n n n n ) ) ) ) intintin

73、tint r r r r; ; ; ; if ( if ( if ( if ( n n n n = 1 1 1 1 ) ) ) ) r r r r = 1; = 1; = 1; = 1; else else else else r r r r = = = = facto facto facto facto ( ( ( (n-1n-1n-1n-1);););); r r r r = = = = n*r;n*r;n*r;n*r; return return return return (r);(r);(r);(r); 等价于等价于等价于等价于当当 n = 1 n = 1 时时n! = n! = 1

74、 1当当 n 1 n 1 时时n! = n * (n-1)!n! = n * (n-1)!534-6 4-6 递归递归- -递归程序的执行过程递归程序的执行过程facto(intfacto(int n) n) intint r r; ; if(n= =1) if(n= =1) r r = 1; = 1; else else r=r=facto(n-1);facto(n-1); r=n*r;r=n*r; return(r);return(r); facto(intfacto(int n) n)intint r r; ;if(n= =1)if(n= =1)facto(intfacto(int n)

75、 n) intint r r; ; if(n= =1) if(n= =1) r r = 1; = 1; else else r=r=facto(n-1);facto(n-1); r=n*r;r=n*r; return(r);return(r); r r= =facto(n-1)facto(n-1)facto(intfacto(int n) n)intint r r; ;if(if(n n= = =1) =1)facto(intfacto(int n n) ) intint r r; ; if(n= =1) if(n= =1) r r = 1; = 1; else else r=r=facto(

76、n-1);facto(n-1); r=n*r;r=n*r; return(r);return(r); r r=facto(n-1=facto(n-1) )facto(intfacto(int n) n) intint r r; ; if(n= =1) if(n= =1) r r = 1; = 1; else else r=r=facto(n-1);facto(n-1); r=n*r;r=n*r; return(r);return(r); facto(intfacto(int n) n)facto(intfacto(int n) n)intint r r; ;intint r r; ;if(if

77、(n n= = =1) =1)if(n= =1)if(n= =1)r r= =facto(n-1)facto(n-1)r r = = 1 1return(return(1 1) )r r=n*=n*r r= =2 2* *1 1return(return(2 2) )return(return(6 6) )r r=n*=n*r r= =3 3* *2 2r r=n*=n*r r= =4 4* *6 6return(return(24)24)1调调调调用用用用234调调调调用用用用调调调调用用用用321返回返回返回返回返回返回返回返回返回返回N=4N=3N=2N=154l例例C4-12.CC4-

78、12.C：采用递归方法计算采用递归方法计算 x x 的的 n n 次方。次方。x xn n = 1 = 1 当当 n = 0n = 0 时时x xn n = x * x = x * xn-1n-1 当当 n 0 n 0 时时 # #include include main( )main( ) intint x, n; x, n; printfprintf ( x=? n=? ); ( x=? n=? );scanf(%d%dscanf(%d%d, &x, &n);, &x, &n); printfprintf (%d*%d=%dn, x, n, (%d*%d=%dn, x, n, power

79、power(x,n) );(x,n) ); powerpower (x, n) (x, n) intint x, n; x, n; if ( if ( n n=0 0 ) return (1); ) return (1); /* /* 递归结束条件递归结束条件 */ */ else return ( x*else return ( x*powerpower( x, n-1 ) );( x, n-1 ) ); 4-6 4-6 递归递归- -下一个实例下一个实例例例例例C4-12C4-12C4-12C4-1255l l递归的基础递归的基础语言本身语言本身语言本身语言本身支持递归调用支持递归调用支持

80、递归调用支持递归调用。变变变变量量量量存存存存储储储储类类类类型型型型（自自自自动动动动变变变变量量量量）的的的的特特特特点点点点，保保保保证证证证了了了了在在在在每每每每层层层层递递递递归归归归调调调调用用用用的的的的过过过过程程程程中中中中，变变变变量量量量可可可可以以以以保保保保持持持持相相相相对对对对于于于于各各各各个个个个层层层层次的独立性，不会发生相互干扰。次的独立性，不会发生相互干扰。次的独立性，不会发生相互干扰。次的独立性，不会发生相互干扰。l l对递归的认识对递归的认识所有的递归问题一定可以用非递归算法实现所有的递归问题一定可以用非递归算法实现所有的递归问题一定可以用非递归算

81、法实现所有的递归问题一定可以用非递归算法实现。 一些问题本身已经蕴涵了递归关系且结构复杂，一些问题本身已经蕴涵了递归关系且结构复杂，一些问题本身已经蕴涵了递归关系且结构复杂，一些问题本身已经蕴涵了递归关系且结构复杂，用非递归算法可能会使程序结构非常复杂，采用递用非递归算法可能会使程序结构非常复杂，采用递用非递归算法可能会使程序结构非常复杂，采用递用非递归算法可能会使程序结构非常复杂，采用递归算法实现，可使程序简洁，提高程序的可读性归算法实现，可使程序简洁，提高程序的可读性归算法实现，可使程序简洁，提高程序的可读性归算法实现，可使程序简洁，提高程序的可读性。递归调用会递归调用会递归调用会递归调用

82、会增加增加增加增加存储存储存储存储空间空间空间空间和执行和执行和执行和执行时间时间时间时间上的开销上的开销上的开销上的开销。4-6 4-6 递归递归- -讨论讨论56l递归问题的分类递归问题的分类数值性数值性递归问题递归问题非数值性非数值性递归问题递归问题对于不同类型的问题对于不同类型的问题, ,可以采用不同的解决方法。可以采用不同的解决方法。l编写递归程序的关键编写递归程序的关键建立递归模型建立递归模型 问问题题的的递递归归定定义义（递递归归描描述述）是是编编写写递递归归程程序的基础。序的基础。递归结束条件递归结束条件 是保证递归可以正常结束的前提是保证递归可以正常结束的前提。4-6 4-6

83、 递归递归- -编写递归程序的一般方法编写递归程序的一般方法57l数值型问题的递归求解一般方法数值型问题的递归求解一般方法从从数数学学公公式式入入手手：推推导导出出问问题题的的递递归归定定义义；确确定定问问题题的的边界条件边界条件；再得到问题的；再得到问题的递归算法递归算法和和递归结束条件递归结束条件l例例C4-13C4-13：求自然数求自然数 1 1 到到 n n 之和。之和。建立问题的建立问题的递归定义递归定义：f(n) = 1 f(n) = 1 当当 n=1 n=1 时时f(n) = n + f(n-1) f(n) = n + f(n-1) 当当 n1 n1 时时程序程序：addadd

84、( n )( n )intint n; n; if ( n if ( n=1 ) return (1); /* 1 ) return (1); /* 递归结束条件递归结束条件 */ */i if ( n1 ) return ( n + f ( n1 ) return ( n + add(n-1)add(n-1) ); ); 递归结束条件递归结束条件递归算法递归算法4-6 4-6 递归递归- -编写数值型递归程序编写数值型递归程序例例例例C4-13C4-13C4-13C4-1358l例例C4-14C4-14：求求菲菲波波那那奇奇序序列列：1 1，1 1，2 2，3 3，5 5，8 8，1313，

85、2121，3434，建立问题的建立问题的递归定义递归定义： f(nf(n) ) = = 1 1 当当 n=1n=1或或n=2n=2 时时 f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2) 当当 n2n2 时时程序程序：f f ( n ) ( n )intint n; n; if (if (n n=1|1|n n=2 2) return (1); ) return (1); /*/* 结束条件结束条件 */*/i if ( n2 ) return ( f ( n2 ) return ( f(n-1)f(n-1)+ +f(n-2)f(n-2) ); ); else retu

86、rn ( -1 ); else return ( -1 ); /* /* 返回返回-1-1表示出错表示出错 * */ / 递归结束条件递归结束条件递归算法递归算法4-6 4-6 递归递归- -编写数值型递归程序编写数值型递归程序例例例例C4-14C4-14C4-14C4-1459l例例C4-15C4-15：打印杨辉三角型：打印杨辉三角型：1 1 1 1 1 1 1 2 1 1 2 1 1 3 3 1 1 3 3 1 1 4 6 4 1 1 4 6 4 1 1 5 10 10 5 1 1 5 10 10 5 1 建立问题的建立问题的递归定义递归定义 对于第对于第 x x 行的第行的第 y y 个

87、值，建立如下数学模型：个值，建立如下数学模型：c(c(x x, ,y y) = ) = 1 1 x x=0=0，y y=1 =1 或或 y y= =x x+1+1c(c(x x, ,y y) = c() = c(x x-1,-1,y y-1) + c(-1) + c(x x-1,-1,y y) ) 其它其它程序程序：intint c c ( x, y ) ( x, y ) /* /* 求第求第 x x 行第行第 y y 列的值列的值 */ */ intint x, y; x, y; if ( x=0 &(y if ( x=0 &(y=1)|(y1)|(y=x+1) ) return(1);x+

88、1) ) return(1); return ( return ( c c(x-1,y-1) + (x-1,y-1) + c c(x-1,y) );(x-1,y) ); 4-6 4-6 递归递归- -编写数值型递归程序编写数值型递归程序例例例例C4-15C4-15C4-15C4-1560l例例C4-16.CC4-16.C：请用递归的方法计算下列函数的值：请用递归的方法计算下列函数的值： px(x,npx(x,n) = x - x) = x - x2 2 + x + x3 3 - x - x4 4 + . (-1) + . (-1)n-1n-1x xn n n0 n0已知程序：已知程序：doub

89、le double pxpx ( x, n ) ( x, n ) intint n; n; double x; double x; if (n if (n=1) return (1) return ( ); ); else return ( x *else return ( x * ) ;) ; 请填写适当的语句，使之成为正确的程序。请填写适当的语句，使之成为正确的程序。4-6 4-6 递归递归- -编写数值型递归程序编写数值型递归程序61l分析分析：px(x,npx(x,n)= x - x)= x - x2 2 + x + x3 3 - x - x4 4 + . (-1) + . (-1)n

90、-1n-1x xn n n0 n0 = = x x * * ( ( 1 - x + x1 - x + x2 2 - x - x3 3 + . (-1) + . (-1)n-1n-1x xn-1n-1 ) ) = = x x * * ( ( 1 1 - - ( (x - xx - x2 2 + x + x3 3 - . (-1) - . (-1)n-2n-2x xn-1n-1 ) ) ) = = x x * * ( ( 1 1 - - px(x,n-1) px(x,n-1) ) )可将原来的非递归定义形式转化为等价的递归定义：可将原来的非递归定义形式转化为等价的递归定义：px(x,npx(x,n

91、) =) = x x 当当 n=1n=1 时时px(x,npx(x,n) = ) = x * ( 1 - px(x,n-1) )x * ( 1 - px(x,n-1) ) 当当 n1n1 时时l程序：程序：double double pxpx ( x, n ) ( x, n ) intint n; n; double x; double x; if (n if (n=1) return (1) return ( ); ); else return ( x *else return ( x * ) ;) ; x( 1 - ( 1 - pxpx(x,n-1) )(x,n-1) )4-6 4-6 递

92、归递归- -编写数值型递归程序编写数值型递归程序62l非数值型问题的递归求解一般方法非数值型问题的递归求解一般方法1.1.将问题将问题化简化简：分析在：分析在最简最简单情况下问题的求解方法。单情况下问题的求解方法。 此此时时，求求解解的的方方法法一一定定是是非非递递归归的的算算法法，而而且且应应该该十分简单。十分简单。2.2.分分解解：将将一一般般的的问问题题分分解解为为两两个个( (或或多多个个) )小小问问题题，且且每每个个分分解解后后的的小小问问题题与与原原来来的的问问题题仍仍然然是是相相似似的的，具具有相同的性质有相同的性质，只是在问题的，只是在问题的规模上有所缩小规模上有所缩小。3.

93、3.建建立立模模型型：假假设设分分解解后后的的小小问问题题已已经经全全部部可可以以解解决决，将将每每个个小小问问题题看看作作一一个个整整体体，不不再再对对小小问问题题进进行行分分解解，建立用建立用小问题小问题解决一般问题的解决一般问题的算法算法。4.4.由由1 1可以产生可以产生递归结束条件递归结束条件，由，由3 3可以推出可以推出递归算法递归算法。思路类似于思路类似于“数学归纳法数学归纳法”4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序63l例例C4-17C4-17：反序输出反序输出整数整数n(n(n=0)n=0)。 例如：例如：n=12345n=12345，输出输出

94、5432154321。l问题分析问题分析：1.1. 若若n n为为1 1位整数（位整数（00n n9 9）：）：则可直接输出。则可直接输出。2.2. 将任一个整数将任一个整数 n n ( (*+ +)()(n=10)n=10)分为分为两部分两部分： 个位个位( (+ +) ) 除个位以外的其余部分除个位以外的其余部分( (*) )3.3. 将将分分解解后后的的两两部部分分分分别别看看成成一一个个整整体体，则则解解决决原原来问题的算法可以描述为：来问题的算法可以描述为： 输出输出 n n 的个位的个位( (+ +) ) 反序输出反序输出 n n 的的除个位以外除个位以外的其余部分的其余部分( (

95、*) )由由 1 1 推出推出递归终止条件递归终止条件。由由 3 3 得到得到递归算法递归算法。4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序641 1 2 2 3 3 4 54 55 51 1 2 2 3 43 44 41 1 2 32 33 31 21 22 21 11 14-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序l递归算法描述递归算法描述：若若：整数：整数 n n 只有只有 1 1 位数字位数字 则则： 输出该整数输出该整数 n n； 否则否则：输出输出 n n 的个位的个位； 反序输出反序输出 n n 的除个的除个 位以外的位以外的其

96、余部分其余部分。进行递归进行递归n/10printn(nprintn(n) )65l程序程序：printnprintn ( ( intint n ) n ) ifif ( 0=n & n=9 ) ( 0=n & n=9 ) printfprintf ( (”%d%d”, n);, n); else else printfprintf ( (”%d%d”, , n%10 n%10 );); /* /* 输输出出个个位位 * */ /printnprintn ( n/10 ); ( n/10 ); /* /* 递归递归 * */ / 4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递

97、归程序例例例例C4-17C4-17C4-17C4-1766l例例C4-18C4-18：输输入入n值值，输输出出高高度度为为n的的等等边边三三角角形形。例如当例如当 n=4 时的图形如下：时的图形如下： * * * * * * * *l程序填空程序填空main ( )main ( ) intint i, n; i, n; scanfscanf (%d, &n); (%d, &n); forfor ( i=1; i=n; i+ ) ( i=1; i0 ) if ( n0 ) printfprintf ( (”%c%c”, c ); /* , c ); /* 输出一个字符输出一个字符 */ */ ;

98、 /* ; /* 递归调用递归调用 */ */ l问题分析问题分析：函数函数 prtprt 的功能是：输出的功能是：输出 n n 个字符个字符 c c。 如果如果 n0 n0 ，则：输出则：输出 1 1 个字符；个字符； 输出其余输出其余 n-1n-1 个字符；个字符； 否则：结束否则：结束l答案答案：prtprt (c, n-1) (c, n-1)4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序684-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序l l汉诺塔问题汉诺塔问题 据说在约十九世纪末欧洲的商店中出售一种智力据说在约十九世纪末欧洲的商店中出售

99、一种智力据说在约十九世纪末欧洲的商店中出售一种智力据说在约十九世纪末欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上玩具，在一块铜板上有三根杆，最左边的杆上自上玩具，在一块铜板上有三根杆，最左边的杆上自上玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由而下、由小到大顺序串着由而下、由小到大顺序串着由而下、由小到大顺序串着由 64 64 64 64 个圆盘构成的塔。个圆盘构成的塔。个圆盘构成的塔。个圆盘构成的塔。 游戏的目的是将最左边游戏的目的是将最左边游戏的目的是将最左边游戏的目的是将最左边杆杆杆杆上的圆盘，借助最右上的圆盘，借助最右上的圆盘，借助最右上

100、的圆盘，借助最右边的边的边的边的杆杆杆杆，全部移到中间的，全部移到中间的，全部移到中间的，全部移到中间的杆杆杆杆上，条件是上，条件是上，条件是上，条件是一次仅一次仅一次仅一次仅能移动一个盘能移动一个盘能移动一个盘能移动一个盘，且，且，且，且不允许大盘放在小盘的上面不允许大盘放在小盘的上面不允许大盘放在小盘的上面不允许大盘放在小盘的上面。6464片片片片初始杆初始杆初始杆初始杆中间杆中间杆中间杆中间杆目的杆目的杆目的杆目的杆1 1 n n18,446,744,073,709,551,61518,446,744,073,709,551,61518,446,744,073,709,551,61518

101、,446,744,073,709,551,615次次次次18441844亿亿次。每次亿亿次。每次亿亿次。每次亿亿次。每次1 1微秒，需要微秒，需要微秒，需要微秒，需要6060万年万年万年万年69l第第1 1步步，将将问问题题简简化化。假假设设 A A杆杆 上上只只有有 2 2 个个圆圆盘盘，即汉诺塔有即汉诺塔有 2 2 层，层，N N2 2。4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序A杆杆C C杆杆杆杆B杆杆移动方法：移动方法： 1. 1. 将上面将上面小片小片移到移到 C C杆杆 上。上。 2. 2. 将下面的将下面的大片大片由由 A A杆杆 移到移到 B B杆杆

102、 上。上。 3. 3. 将将 C C杆杆 上的上的小片小片移到移到 B B杆杆 上。上。l分析：分析：对对A A杆杆上上的的全全部部N N个个圆圆盘盘从从小小到到大大顺顺序序编编号号，最最小小的的圆圆盘为盘为1 1号，次之为号，次之为2 2号号则最下面的圆盘的编号为则最下面的圆盘的编号为 N N。70A杆杆C C杆杆杆杆B杆杆4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序l第第2 2步步，对对于于一一个个有有N N(N1)(N1)个个圆圆盘盘的的汉汉诺诺塔塔，将将N N个个圆圆盘盘分分为为两两部部分分：上上面面的的N-1N-1个个圆圆盘盘和和最最下下面面的的 N N号号

103、圆盘。将圆盘。将“上面的上面的N-1N-1个圆盘个圆盘”看成一个整体。看成一个整体。l第第3 3步步，为解决，为解决 N N 个圆盘的汉诺塔，可按如下方式个圆盘的汉诺塔，可按如下方式进行操作：进行操作： 将将A A杆杆上面的上面的N-1N-1个个盘子，借助盘子，借助B B杆杆，移到，移到C C杆杆上；上； 将将 A A杆杆 上剩下的上剩下的 N N号号 盘子移到盘子移到 B B杆杆 上；上； 将将 C C杆杆 上的上的 N-1N-1个个 盘子，借助盘子，借助A A杆杆，移到，移到B B杆杆上上71整整理理分分析析结结果果：把把第第1 1步步中中化化简简问问题题的的条条件件作作为为递递归归 结束

104、条件结束条件，将，将第第3 3步步分析得到的算法作为分析得到的算法作为递归算法递归算法。 定定义义函函数数movediscmovedisc( ( n n，fromneedlefromneedle，toneedletoneedle，usingneedleusingneedle) )。将将 fromneedlefromneedle 杆杆上上的的 N N 个个圆圆盘盘，借助借助 usingneedleusingneedle 杆，移动到杆，移动到 toneedletoneedle 杆上。杆上。l移动移动N N个圆盘的递归算法描述如下个圆盘的递归算法描述如下：movediscmovedisc ( ( n

105、 n，fromneedlefromneedle，toneedletoneedle，usingneedleusingneedle ) ) ifif ( n ( n=1 ) 1 ) 将将 n n 号圆盘从号圆盘从 fromneedlefromneedle 上移到上移到 toneedletoneedle; ; else else movediscmovedisc ( ( n-1n-1，fromneedlefromneedle，usingneedleusingneedle，toneedle toneedle ) ) 将将 n n 号圆盘从号圆盘从 fromneedlefromneedle 上移到上移到

106、 toneedletoneedle; ; movediscmovedisc ( ( n-1n-1，usingneedleusingneedle，toneedletoneedle，fromneedle fromneedle ) ) 4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序72l程序程序C4-19.CC4-19.Cintint i=0; i=0; /* /* 移动圆盘数量计数器移动圆盘数量计数器 */ */main( )main( ) unsigned n; unsigned n; scanfscanf (%d, &n); (%d, &n); movediscmove

107、disc ( ( n,n,a a, ,b b, ,c c); ); /* /* 将将A A上上的的N N个个圆圆盘盘借借助助C C将将移移动动到到B B上上 */ */ printfprintf( t Total: %dn, i );( t Total: %dn, i ); movediscmovedisc ( ( n n, , fromneedlefromneedle, , toneedletoneedle, , usingneedleusingneedle ) ) unsigned n; unsigned n; char char fromneedlefromneedle, , tonee

108、dletoneedle, , usingneedleusingneedle; ; ifif ( n ( n = 1 ) 1 ) printf(%2d-(%2d): %c = % printf(%2d-(%2d): %c = %cn,+icn,+i, , n n, ,fromneedlefromneedle, ,toneedletoneedle);); else else movediscmovedisc ( ( n-1n-1, , fromneedlefromneedle, , usingneedleusingneedle, , toneedletoneedle ); ); printf(%2

109、d-(%2d): %c = % printf(%2d-(%2d): %c = %cn,+icn,+i, , n n, ,fromneedlefromneedle, ,toneedletoneedle);); movediscmovedisc ( ( n-1n-1, , usingneedleusingneedle, , toneedletoneedle, , fromneedlefromneedle ); ); 4-6 4-6 递归递归- -编写非数值型递归程序编写非数值型递归程序例例例例C4-19C4-19C4-19C4-1973l程序执行过程程序执行过程当当N=N=3 3时，程序递归调用的

110、完整执行过程时，程序递归调用的完整执行过程在在mainmain函数中函数中 递归调用第一层递归调用第一层 递归调用第二层递归调用第二层 递归调用第三层递归调用第三层 递归递归 递归递归 move(1,a,b,c)move(1,a,b,c) 输出：输出：1-(1):1-(1):a=ba=b 返回递归第二层返回递归第二层 输出：输出：2-(2):2-(2):a=ca=c 调用调用 move(1,b,c,a)move(1,b,c,a) 输出：输出：3-(1):3-(1):b=cb=c move(2,a,c,b)move(2,a,c,b) 返回递归返回递归第二层第二层 返回递归调用返回递归调用第一层第

111、一层move(3,a,b,c) move(3,a,b,c) 输出：输出：4-(3):4-(3):a=ba=b move(2,c,b,a)move(2,c,b,a) move(1,c,a,b)move(1,c,a,b) 输出：输出：5-(1):5-(1):c=ac=a 返回递归第二层返回递归第二层 输出：输出：6-(2):6-(2):c=bc=b 返回返回mainmain函数函数 move(1,a,b,c)move(1,a,b,c) 输出：输出：7-(1):7-(1):a=ba=b 返回递归返回递归第二层第二层 返回递归调用返回递归调用第一层第一层4-6 4-6 递归递归- -编写非数值型递归程

112、序编写非数值型递归程序74 库库函函数数不不是是C C语语言言的的一一部部分分，它它是是由由编编译译程程序序根根据据一般用户的需要编制并提供用户使用的一组程序。一般用户的需要编制并提供用户使用的一组程序。l基本概念基本概念 函函数数库库：函函数数库库是是由由系系统统建建立立的的具具有有一一定定功功能能的的函函数数的的集集合合。库库中中存存放放函函数数的的名名称称和和对对应应的的目目标标代代码码，以以及及连连接接过过程程中中所所需需的的重重定定位位信信息息。用用户户也也可可根根据据需需要建立自己的用户函数库。要建立自己的用户函数库。 库函数库函数：存放在函数库中的函数。：存放在函数库中的函数。库

113、函数具有明确的库函数具有明确的功能功能、入口调用参数入口调用参数和和返回值返回值。 连连接接程程序序：将将编编译译程程序序生生成成的的目目标标码码连连接接起起生生成成可可执行文件。执行文件。 头头文文件件：也也称称为为包包含含文文件件。C C语语言言库库函函数数与与用用户户程程序序之之间间进进行行信信息息通通信信时时要要使使用用的的数数据据和和变变量量，在在使使用用某一库函数时，都要在程序中嵌入（用某一库函数时，都要在程序中嵌入（用# #includeinclude）。）。4-7 4-7 库函数简介库函数简介75lTubroTubro C C库函数分为库函数分为9 9大类：大类：1.1.I/O

114、I/O函数函数包括各种包括各种控制台控制台I/OI/O、缓冲型文件缓冲型文件I/OI/O和和UNIXUNIX式式非缓冲型文件非缓冲型文件I/OI/O操作。操作。需要的包含文件：需要的包含文件：stdio.hstdio.h例如：例如：getchargetchar，putcharputchar，printfprintf，scanfscanf，fopenfopen, , fclosefclose，fgetcfgetc，fgetsfgets，fprintffprintf，fsacnffsacnf，fputcfputc，fputsfputs，fseekfseek，freadfread，fwritefwr

115、ite 等。等。4-7 4-7 库函数简介库函数简介762.2.字符串、内存和字符函数字符串、内存和字符函数包括对字符串进行各种操作和对字符进行操作包括对字符串进行各种操作和对字符进行操作的函数。的函数。需要的包含文件：需要的包含文件：string.hstring.h、mem.hmem.h、ctype.hctype.h或或string.hstring.h例如：例如： 用于检查字符的函数：用于检查字符的函数：isalnumisalnum，isalphaisalpha， isdigitisdigit，islowerislower，isspaceisspace等。等。 用于字符串操作函数：用于字符串

116、操作函数：strcatstrcat，strchrstrchr，strcmpstrcmp，strcpystrcpy，strlenstrlen，strstrstrstr等。等。4-7 4-7 库函数简介库函数简介773.3.数学函数数学函数 包括各种常用的三角函数、双曲线函数、指数和对包括各种常用的三角函数、双曲线函数、指数和对数函数等。数函数等。 需要的包含文件：需要的包含文件：math.hmath.h 例如：例如：sinsin，coscos，expexp（e e的的x x次方），次方），loglog，sqrtsqrt（开平方），开平方），powpow（x x的的y y次方）等。次方）等。4.4

117、.时间、日期及与系统有关的函数时间、日期及与系统有关的函数 对时间、日期的操作和设置计算机系统状态等。对时间、日期的操作和设置计算机系统状态等。 需要的包含文件：需要的包含文件：time.htime.h 例如：例如：timetime返回系统的时间；返回系统的时间；asctimeasctime返回以字符返回以字符串形式表示的日期和时间。串形式表示的日期和时间。4-7 4-7 库函数简介库函数简介785.5.动态存储分配动态存储分配 包括包括“申请分配申请分配”和和“释放释放”内存空间的函内存空间的函数。数。 需要的包含文件：需要的包含文件：alloc.halloc.h 或或 stdlib.hst

118、dlib.h 例如：例如：calloccalloc，freefree，mallocmalloc，reallocrealloc等。等。6.6.目录管理目录管理 包括：建立磁盘目录、查询、改变等对磁盘包括：建立磁盘目录、查询、改变等对磁盘目录操作的函数。目录操作的函数。4-7 4-7 库函数简介库函数简介797.7.过程控制过程控制 包括最基本的过程控制函数。包括最基本的过程控制函数。8.8.字符屏幕和图形功能字符屏幕和图形功能 包括各种绘制点、线、圆、方和填色等的包括各种绘制点、线、圆、方和填色等的函数。函数。9.9.其它函数其它函数4-7 4-7 库函数简介库函数简介80l库函数使用注意事项库函数使用注意事项 在使用库函数时应清楚的了解以下在使用库函数时应清楚的了解以下4 4个方面的个方面的内容：内容： 函数的功能及所能完成的操作；函数的功能及所能完成的操作； 参数的数目和顺序，以及每个参数的物理参数的数目和顺序，以及每个参数的物理意义及类型；意义及类型； 返回值的意义及类型；返回值的意义及类型； 需要使用的包含文件（头文件）。需要使用的包含文件（头文件）。这些是要正确使用库函数的必要条件。这些是要正确使用库函数的必要条件。4-7 4-7 库函数简介库函数简介81