ch08-再论函数

1、第八章 再论函数,参数 返回指针的函数 作用域 递归 本章小结,int u,v ; void p( int x , int y) y = x+y; printf(“%d %dn” , x,y ) ; void main(void) u = 3; v = 4; p( u , v ); printf(“%d %dn” , u , v ); p( 6 , u+v ); printf(“%d %d %dn” , u, v ，u+v ); ,4,内存空间,3,p.y,p.x,main.v,main.u,3,4,7,3 7,3 4,7,6,13,6 13,3 4 7,程序输出：,C参数传递规则,指针作参数

2、,一般意义上，函数的形参是指针类型 对应调用时，相应实参也应是指针类型表达式 例子 void f(int * x) void main(void) int * v； f(v) ,但是真正应用指针参数，其作用是相当大的 由于在函数内部，指针参数变量可以指向它的调用处（外层程序）的其它变量 它起到了其它程序设计语言中变量参数的作用。 如下例程序的功能是对随意输入的两个整数，按由大到小的顺序输出。 函数swap的功能是交换两个整数变量的值。,void swap(int *xx, int *yy) int temp; temp=*xx; *xx=*yy; *yy=temp; void main() i

3、nt x,y; int *px,*py; scanf(%d %d, ,6,3,py,px,y,x,2348,2344,2342,2340,返回值,xx,234E,234C,yy,2352,temp,2356,main,swap,2340,2342,2340,2342,3,6,3,程序输出：6 3,void swap(int *xx, int *yy) int temp; temp=*xx; *xx=*yy; *yy=temp; void main() int x,y; int *px,*py; scanf(%d %d, ,6,3,y,x,2342,2340,返回值,xx,2346,2344,y

4、y,234A,temp,234E,main,swap,2340,2342,3,6,3,程序输出：6 3,第四章验证PASCAL定理例题4.4的程序，传递信息时让人感到十分别扭，函数不能把多个计算结果带回调用处。使用指针参数可以解决这个问题，例题4.4的程序可以改写。,例8-3 改写例4.4 。验证 Pascal 定理，圆的内接 六边形三双对边延线的交点在一条直线上。,/*PROGRAM Pascal theorem*/ #include math.h #include stdio.h #define PI 3.1415927 #define eps 1e-5 float radius; /*

5、圆的半径 */ float theta1,theta2,theta3,theta4,theta5,theta6; /* 六个极角的度数 */ float xa,ya,xb,yb,xc,yc,xd,yd,xe,ye,xf,yf; /* 六个顶点的直角坐标 */ float b1_x,b1_y,b2_x,b2_y,b3_x,b3_y; /* 三个交点的直角坐标 */,/*主程序之前这段为“函数原型”以及各个函数返回结果所用变量*/ void trans_abcdef(); /*计算六个顶点直角坐标*/ void coordinate(float ,float，float *,float * );

6、/*计算一个顶点直角坐标*/ void three_inter(); /*求三个交点*/ void intersection(float,float,float,float,float,float,float,float ,float*,float*); /*已知四点，求两条直线交点*/ void equation(float,float,float,float,float,float,float,float ,float*,float*,float*,float*); /*已知四点求两条直线方程*/ void straightline(float,float,float,float , fl

7、oat*,float*); /*已知两点求直线方程斜率(a)和截距(b)*/ void inter(float,float,float,float, float*,float*); /*已知两个直线方程的斜率和截距 求交点*/ int test(float,float,float,float,float,float); /* 检验 */,/*主函数*/ void main() /*读入圆形的半径*/ printf(please input the radius of the circle:); scanf(%f, ,/*计算六个顶点直角坐标*/ void trans_abcdef() coor

8、dinate(radius,theta1, ,/*求三个交点*/ void three_inter() intersection(xa,ya,xb,yb,xd,yd,xe,ye, ,/*已知四点，求两条直线方程*/ void equation(float rx,float ry,float sx,float sy , float tx,float ty,float ux,float uy , float *ma,float *mb,float *na,float *nb) straightline(rx,ry,sx,sy,ma,mb); straightline(tx,ty,ux,uy,na,

9、nb); /*计算由两点确定直线方程的斜率（a）和截距（b）*/ void straightline(float ex,float ey,float fx,float fy,float *a,float *b) *a=(fy-ey)/(fx-ex); /* 斜率 */ *b=ey-a*ex; /* 截距 */ ,/*已知两个直线方程的斜率和截距，求它们交点*/ void inter(float ma,float mb,float na,float nb,float *wx,float *wy) *wx=(nb-mb)/(ma-na); *wy=ma*wx+mb; /* 检验 */ bool t

10、est(float b1_x,float b1_y, float b2_x,float b2_y, float b3_x,float b3_y) float pa,pb; /* B1、B2连线方程系数 */ straightline(b1_x,b1_y,b2_x,b2_y, ,在该程序中，计算一个顶点在直角坐标系中坐标的函数 coordinate 用指针参数px 、py 代替了原来的全局量传递计算结果坐标。使用形式是： 在函数声明中，增加形式参数px 、py ，并把它声明成指针类型，构成指针参数； void coordinate ( float r , float theta ，float *

11、px , float *py ) 在函数调用中，用变量的指针（地址）作实在参数，对应相应形式参数。对应点A有： coordinete( r , theta1 , 在这种参数中， 函数调用时实在参数把变量xa 、ya的指针分别送入形式参数px 、py中，因此px 、py分别指向xa 、ya ； 函数内部，以间接寻址方式赋值，分别通过*px 、*py把值送入px 、py所指的变量中，也就是xa 、ya中。 当函数返回后，xa 、ya中自然是函数内部给它们赋的值。,在本程序中， 求两条直线交点函数intersection的参数hx 、hy ； 计算直线方程系数函数straightline的参数a 、

12、b ； 求两个直线方程交点函数inter的参数wx 、wy 等等都是指针参数。他们都以上述方式传递函数的计算结果。,函数three_inter 、intersection 、inter之间的参数传递 函数intersection有指针参数hx 、hy 函数inter有指针参数wx 、wy 函数intersection调用inter时 直接使用形式参数hx 、hy对应 函数inter的形式参数wx 、wy 那么wx 、wy指向什么？ void three_inter( void ) intersection( . , ,该参数传递过程是： 函数three_inter调用函数intersectio

13、n( . , 则用如下形式调用函数 f(a) 函数调用f(a)把数组a的首地址送入函数f的形参x中，在函数执行期间，形参x指向实参数组a ，用a参与进一步运算。也就是说，形参和实参使用一个数组。,使用数组作函数参数的形式一般是： 形式参数用数组声明符说明，如下例子说明形式参数x是10个元素的数组。 int f ( float x 10 ) 实在参数用数组名对应形式参数数组，例如若有声明 float a10 ; 则用如下形式调用函数 f(a) 函数调用f(a)把数组a的首地址送入函数f的形式参数x中，在函数执行期间，形式参数x指向实在参数数组a ，用a参与进一步运算。也就是说，形式参数和实在参数

14、使用一个数组。,数组与指针有极其密切的关系 数组作参数，传递给形参的实际是实参数组的首地址 也就是把实参数组名的值送入形参中 在函数内，形参数组实际是使用实参数组名字开始的那片存储区 事实上C是把数组参数当作指针来处理的。 数组作参数，形参是一指针类型变量 实参数组名实际也是一个指针值 参数结合时，把实参指针值送入形参 实际是把数组首地址送入指针变量中，然后形参指向实参数组第一个元素 上述例子中，经过函数调用、参数结合后，形式参数x指向a0。 C参数都是值方式的 数组参数传递给函数的值不是整个数组的值，而是数组名的值，也就是实参数组首地址 在函数内不给形参开辟数组存储空间，只给它开辟一个指针空

15、间 参数传递的是实参数组名字的指针值。,省略数组形式参数最外层的尺寸 最外层的尺寸对计算数组元素的地址不起作用，在对数组参数的形式参数声明时，可以省略最外层尺寸。前述f的函数定义说明符可以使用形式 int f ( float x ) 这种形式的形式参数声明与前边所述形式等价，形参的具体尺寸由函数调用时的实参数组决定。多维情况也是这样。例如 int q ( float y 20 ) 声明两维数组参数y ，y每行20个元素，具体多少行由实参数数组决定。设有声明 float u1020 , v1520 ; 则函数调用q(u) ,进入函数q执行时 形式参数y表记实在参数数组u ，它是10行20列的数组

16、； 而函数调用q(v) ，进入同一个函数q执行时，形参数y表记实参数组v 是15行20列的数组。,数组参数可以有各种变形,与数组初值一样，省略尺寸的只能是最外层，下述函数定义说明符都是错误的。 int r ( float z ) int s ( float z10 ) int t ( float z10 20 ),形式参数用指针形式 前述函数f的函数定义说明符还可以用形式 int f ( float *x ) 这种形式的形式参数声明与上述1中形式等价，形式参数的具体尺寸由函数调用时的实在参数数组决定。设有声明 float c20 , b15 ; 则函数调用f(c) , 进入函数 f 执行时，形

17、式参数x表记实在参数数组c ，它是20个元素的一维数组； 而函数调用f(b) ，进入同一个函数f执行时，形式参数x表记实在参数数组b ，它是15个元素的一维数组。,使用指针作实在参数 上述，形参是一个指针，对应实参数可以是数组； 反之形参是数组，对应实在参数也可以是指针。 下述应用是正确的 float a15,b20; float *p ; int f ( float x ) . . . int q ( . ) . . . p = a ; /* 赋值后，指针p就是数组a */ . f(p) . /* 以p作实在参数，函数f内x表记数组a */ p = b ; /* 赋值后，指针p就是数组b *

18、/ . f(p) . /* 以p作实在参数，函数f内x表记数组b */ ,形式参数和实在参数都使用指针形式 数组参数形式还可以是形参和实参都使用指针形式 即形参是一个指针，对应实参也是指针 下述应用是正确的 float a15,b20; float *p ; int f ( float *x ) . xi . int q ( . ) . . . p = a ; /* 赋值后，指针p就是数组a */ . f(p) . /* 以p作实在参数，函数f内x表记数组a */ p = b ; /* 赋值后，指针p就是数组b */ . f(p) . /* 以p作实在参数，函数f内x表记数组b */ ,第六章

19、的许多例题，都是使用全局量传递计算结果数组，显得很别扭。使用数组参数可以解决该问题。,例8-4 重写“主元排序”法,把被排序数组和数组长度都作为函数的参数。 调用时，被排序数组对应形参a ；数组长度对应形参 n void sort ( int a , int n ) int i,j,k,r ; for ( i=0 ; in-1 ; i+ ) j=i ; for ( k=i+1 ; kn ; k+ ) if ( ak aj ) j=k ; r = ai ; ai = aj ; aj = r ; ,例8-5 把给定数组中的n个整数反序存放,void inv(int x,int n) int tem

20、p,i,j; for(i=0;i=(n-1)/2;i+) j=n-1-i; temp=xi; xi=xj; xj=temp; 设有声明“int a10”，则可以用 “inv(a,10)” 调用该函数 若还有声明 “int *ptr” 和操作 “ptr=a”，则也可以用 “inv(ptr,10)” 调用该函数。,该函数还可以用指针形式编成如下形式，功能、调用方式相同 void inv(int *x,int n) int temp,*i,*j; / j 从后向前变化，I 从前向后变化 for(i=x,j=x+n-1; i=x+(n-1)/2; i+,j-) temp = *i; / temp保存i

21、所指数组元素xi的值 *i = *j; / xj的值送入xi *j = temp; / 把temp中保存的xi的值送入xj ,例8-6 从n个整数中找出最大和最小的数,void max_min_value( int x , int n , int *max , int *min) int *p; *max = *min = *x; / 把x0送入max、min所指变量中 for(p=x+1; p *max) / 求极大值，p指向当前数组元素 *max = *p; / max指向极大值单元if (*p *min) / 求极小值 *min = *p; ,设有声明 int a10,max_value

22、,min_value; 则调用该函数 max_min_value (a,10, ,若还有声明和操作 int *ptr; ptr=a; 则调用该函数 max_min_value (ptr,10, ,其它程序设计语言的参数类别,C只有值参数，函数调用时，一律把实参值送入形参变量 这种参数机制的优点是简化了参数概念，也降低了编译系统的复杂度 缺点是给程序设计带来不便，程序员要关心十分细致的函数之间的信息传递 许多程序设计语言还引进其它各类参数类别。 下边简单介绍 PASCAL的变量参数 ALGOL60的换名参数,所谓变量参数、换名参数都不是C的内容，它们分别属于不同程序设计语言 在此介绍它们，只是为

23、了开阔读者的眼界，不感兴趣的读者完全可以不看这节 尤其不要在C中试图使用这些成分。,PASCAL语言参数类别有两种 值参数 变量参数 求六个顶点的直角坐标部分的PASCAL程序片段,VAR r, theta1, theta2, theta3, theta4, theta5, theta6 : real ; 1 xa, ya, xb, yb, xc, yc, xd, yd, xe, ye, xf, yf : real; 2 以知矢径和极角求一点在直角坐标系中坐标坐标 3 PROCEDURE coordinate ( r, theta: real; VAR px, py: real); 4 BEG

24、IN 5 px:=r*cos(PI*theta/180); 6 py:=r*sin(PI*theta/180); 7 END; 8 计算六个顶点坐标 9 PROCEDURE trans_abcdef ； 10 BEGIN 11 coordinate(r,theta1,xa,ya); 12 coordinate(r,theta2,xb,yb); 13 coordinate(r,theta3,xc,yc); 14 coordinate(r,theta4,xd,yd); 15 coordinate(r,theta5,xe,ye); 16 coordinate(r,theta6,xf,yf); 17

25、END 18 ,该程序片段从过程（相当与C的函数）trans_abcdef开始执行 trans_abcdef 六次调用过程coordinate coordinate有四个形参，px, py是变量参数，r, theta是值参 调用过程coordinate时程序如下执行: 从第12行开始执行，以r,theta1,xa,ya为实参对应形参r, theta, px, py调用过程coordinate r, theta为值参，分别作为独立变量将被赋值以实参表达式r , theta1当前值 在coordinate执行开始r, theta分别具有r, theta1的当前值 px, py是变量参数，实参xa,

26、 ya将替换变量型形式参数px, py 在coordinate的整个执行期间px, py将分别表记实参变量xa, ya 执行coordinate的语句部分时，第6 、7两行的赋值语句 px:=r*cos(PI*theta/180); py:=r*sin(PI*theta/180); 给px, py赋值，就是给xa, ya赋值，从而把coordinate的执行结果带回主程序。,可以看出，值数与变参是不一样的 变量参数的特性是： 与变参对应的实参是一个变量访问，实参与形参要类型相同 变参的结合过程是: 首先确是实参变量； 以实参变量代替形参变量。 在整个函数活化期间，变参始终表记与其相对应的实参变

27、量 所以在函数内，对形参的一切操作，实际上都是对相应的实参的操作。 显然若在函数内改变形参的值将直接影响实参变量。 当函数执行结束返回后，实参值依赖于在函数活化期间是否改变了相应形参 并且其值就是在函数活化期间对相应形参的最后一次赋值操作的值。故可利用变参将函数的执行结果带回其调用处,从变量参数结合过程可知: 对变量参数而言，使用哪个变量代替形式参数在进入函数之前已 经确定 整个函数活化期间，相应形式参数始终表记那个确定的实在参数变量，不会改变了。,例8-8有如下程序片段 在函数 p中，x是变量参数 它的赋值语句x:=5是给下标变量v2赋值 还是给下标变量v3赋值？ VAR i : integ

28、er ; v : ARRAY 1.10 OF real ; PROCEDURE p ( VAR x : real ) ; BEGIN i:=3; x:=5 END; BEGIN i:=2; p ( vi ) END.,答案是：给v2赋值，而不是给v3。,该程序片段执行过程是： i:=2 执行函数调用p(vi)： 先确定实在参数变量， 这时i等于2，所以vi是v2 ； 再以v2替换函数 p的形式参数x 因而函数 p中的所有x都表记v2 ； 执行函数 p 的函数体： i:=3 ; 这时全局量i等于3 x:=5 ; 由于x表记v2而不是vi 所以i等于3对本语句无影响； 这里仍是给v2赋值5， 而不

29、是给v3赋值5； 相当于执行赋值语句v2:=5 。,ALGOL60语言参数类别有 值参数 换名参数 有如下ALGOL60程序片段。在函数 p中形式参数x是换名参数，y是值参数。P中赋值语句x:=5是给哪个变量赋值？INTEGER i , k ; INTEGER ARRAY v 1:10 ; PROCEDURE p ( x ，y ); VALUE y ; INTEGER x , y ; BEGIN i:=3 ; y:=0 ; x:=5; END; BEGIN i:=2; k:=10; p ( vi , k ) END,答案是：x:=5给v3赋值5， 而不是给v2。,本例题结合上述例 8-6还可以

30、看出变量参数和换名参数的区别。 i:=2 执行函数调用p(vi)： 以vi替换函数 p的形式参数x ， 函数 p中所有x都被替换成vi ； 执行函数 p 的函数体： i:=3 ; 这时全局量i等于3 。 x:=5 ; 由于x是vi， 执行的是赋值语句vi:=5 ； 而此时 i 等于3； 所以这里是给v3赋值5。,y是值参函数内给y:=0不影响实参k函数返回后，k值仍然是10,可以看出，换名参数是“用整个实在参数原封不动的替换形式参数”。在函数内部再确定具体操作。,返回指针的函数,函数返回类型不允许是数组类型和函数类型，除此之外允许一切类型，当然允许指针类型 本节仅介绍函数结果类型是一般指针类型

31、的形式 带回指针值的函数的函数定义说明符形式是： 类型名 *函数名( 形式参数表 ),float *f ( int x , int y ) f 是函数名； x 和 y 是两个 int 类型形参； 该函数的返回类型是“ float * ” 即指向 float 类型的指针。 可以这样解释该函数定义说明符。按运算符优先级规定，“ * ” 的级别低于 “（）”， f (int x, int y) 是一个函数，它的类型是 “ float *”,即函数 f 的类型是 float 类型指针函数f 是返回指针值的函数。,在函数内，return 语句后边的表达式类型应该是 “类型名 *” 。 比如若有声明 fl

32、oat u , *v ; 则，下述return语句都是正确的 return ,而语句 return u; 是错误的。,例8-10 读入月份数，输出该月份英文名称,char *month_name(int); char *name=“illegal month”, “Jan”, ”Feb”, ”Mar”, ”Apr”, ”May”, ”Jun”, “Jul”, ”Aug”, ”Sep”, ”Oct”, ”Nov”, ”Dec”; int main(void) int n; char *p; printf(“Input a number of a month:”); scanf(“%d”, ,程序

33、运行结果 Input a number of a month: 2 It is Feb,例8-11用4*3指针数组保存每个月份名称的字符串指针，完成上题,char * mp( char *43 ,int ) ; int main(void) char * name 3= “Jan”,”Feb”,”Mar”, “Apr”,”May”,”Jun”, “Jul”, ”Aug”,”Sep”, “Oct”,”Nov”,”Dec” ; char *p ; int m ; printf(“Inputer a number of month:”); /* 读入月份 */ scanf(“%d”, /* 列标 *

34、/ return *(*(cp+row)+col ) ； /* 返回月份字符串指针 */ ,Input a number of a month:,2,the 2th month is Feb,C指针函数只允许返回全局变量指针、静态变量指针、堆内空间地址，不允许把函数内部声明的局部变量指针（地址）作为返回值。在例8-10中，如果把字符串数组name放在函数mp内声明就错了。因为函数内部声明的局部变量在栈区分配空间，函数调用结束时，释放栈区中函数运行空间，会造成返回指针所指存储空间已不存在,作用域,作用域 就是程序中声明的标识符有定义的区域。 在一个标识符的作用域内，使用它是合法的； 且所使用的就

35、是相应声明的标识符。 作用域是一个静态概念 描述从程序静态行文上看，程序中一个被声明的标识符起作用的范围（一段程序行文） 本节所涉及的内容都是从程序的静态行文上看,声明点 C 程序中出现的每一个标识符都有一个声明点， 标识符的声明点就是“包含相应标识符词法记号的声明符的结尾处”。 int x /* 此处为x的声明点 */ ; u1020 /* 此处为u的声明点 */ ; 作用域规则 每个声明点都有作为程序正文的一部分的一个区域，称为声明的作用域。 声明的作用域是“相应声明有效的程序文本区域”，下表列出各种C标识符的作用域,C中，每个源程序编译单位，每个函数定义、函数原型、复合语句都各自构成一个

36、作用域区域。C规定： 在嵌套结构中，若里层区域的一个标识符与外层区域的某 标识符同名，则外层标识符的作用域不包括里层那个同名 标识符的作用域区域。 C 程序中使用的任意一个标识符必须声明；并且必须先声 明后使用；在同一区域内任何标识符不得重复声明。,例8-12 错误应用,生存期,生存期是一个动态概念 描述当程序运行起来后，一个对象（标识符）是否有效存在 所谓对象主要是指变量和函数 对于类型不同的变量和函数在程序运行时要分配存储空间，也就是具有存在性。 对象的生存期是保持所分配存储空间的那段程序的运行期间。 如果变量有一个初始化语句，则每次进入它的生存期创建它的同时，对它重新初始化。,静态生存期

37、 如果所分配的存储空间在程序执行前开始，并保持到程序执行终止，则称此对象具有静态生存期。C语言中 所有函数都具有静态生存期； 所有顶层声明的变量都具有静态生存期； 复合语句中声明的变量是否具有静态生存期，取决于存储类别； 函数形式参数是否具有静态生存期，取决于具体声明的存储类别 具有静态生存期的对象（变量、函数）在程序的整个运行期间全都存在。 程序开始运行它的生存期开始，并创建它；一直到程序运行结束，它的生存期结束并删除它。,本地生存期 如果对象在进入复合语句或函数时生成，在退出复合语句或函数时删除，则称为具有本地生存期。 具有本地生存期的对象 当程序运行进入复合语句或函数时创建它，并且它的生

38、存期开始 当程序运行退出复合语句或函数时删除它，并且它的生存期结束 C语言中把具有本地生存期的变量称为自动变量。 复合语句中声明的变量是否具有本地生存期，取决于具体声明的存储类别； 函数形式参数是否具有本地生存期，取决于具体声明的存储类别。,动态生存期 C中的数据对象还可以具有动态生存期 可以随意显式地创建和删除。 动态对象的创建和释放，通过动态存储分配函数（malloc、free等）显式实现。 复合语句中声明的变量、函数形式参数具有本地生存期还是具有静态生存期依赖于它的存储类别。 有关存储类别的概念我们不在这里介绍，有兴趣的读者可以查阅第13章或有关资料。目前我们使用它们的省缺存储类别。 所

39、有复合语句中声明的变量、函数形式参数全部具有本地生存期，全部为自动变量； 所有顶层声明的变量具有静态生存期，全部为静态变量； 所有函数都具有静态生存期。,局部量和全局量,由作用域规则可知 一个函数或复合语句引入的标识符只在本函数或复合语句内有效， 在本函数或复合语句外，便失去了它的意义 称它们是局部于声明它们的函数或复合语句 或称该标识符相对于声明它们的函数或复合语句来讲是局部量。,由作用域规则还可知 任何顶层声明的标识符在所有函数内部以及复合语句都可以使用 条件是在函数内部和复合语句中没有与它同名的其它声明 称顶层声明的标识符相对于函数和复合语句来讲是全局量 若一个复合语句嵌套在一个函数或另

40、一个复合语句之内 且某一个标识符在函数或其外层复合语句中声明 而且在内层复合语句中没有与相应标识符同名的声明 则函数或外层复合语句中关于这个标识符的声明在内层复合语句中仍然有效 即在内层复合语句中仍可使用这个标识符 称在函数或外层复合语句中声明的标识符相对于其内层复合语句来讲是全局量。,全局量和局部量是一个相对概念。 某标识符相对于某复合语句是局部的，相对于其内层复合语句却是全局的； 反之某标识符相对于里层某复合语句是全局的，但是相对于声明它本身的那个复合语句来讲却是局部的。 全局量在内层具有外层同样的意义 在内层对全局量的操作直接反应在外层程序中,例8-13 计算调合级数前项和,int ma

41、in(void) /* 23 */ int i ; /* 24 */ printf(please input the value of n:); /* 25 */ scanf(“%d”, /* 35 */ /* 36 */,int a,b,n; /* 2 */ void add ( int *e , int *f , int ii ) /* 3 */ *e = (*e) * ii + (*f) ; /* 4 */ *f = (*f) * ii ; /* 5 */ /* 6 */,int gcd( int u , int v ) /* 7 */ int r ; /* 8 */ r=v; /* 9

42、 */ while ( r!=0 ) /* 10 */ r = u % v ; /* 11 */ u = v ; /* 12 */ v = r ; /* 13 */ /* 14 */ return u ; /* 15 */ void reduce ( int *x , int *y ) /* 17 */ int g ; /* 18 */ g = gcd( x,y ) ; /* 19 */ *x = （*x） / g ; /* 20 */ *y = （*y） / g ; /* 21 */ /* 22 */,程序中各个变量的作用域 变量a, b, n; 函数main, add, reduce, g

43、cd在顶层声明，是全局量。 作用域是它们各自的声明符以后直到整个程序文件结束。 变量i在主函数main中声明，是main的局部量。 作用域是第24行它的声明符以后直到第36行 add的形式参数e, f, ii在add中声明，是add的局部量 作用域是第3行它们各自的声明符以后直到第6行。 gcd的形式参数u, v和在gcd内部复合语句中声明的变量r是局部于gcd的局部量。 作用域是第7、8行它们各自的声明符以后直到第16行。 reduce 的形参x, y和在reduce 内部复合语句中声明的变量g是局部于reduce 的局部量。 作用域是第17、18行它们各自的声明符以后直到第22行,第 30

44、 行调用函数add作加法。 以 p=1; for ( i=1 ; i=n ; i=i+1 ) p=p*i; return p ; ,现在换一个角度考虑问题，! 不仅是 1*2*3* . *n 还可以定义成,按照该定义，! 就是一个简单的条件语句和表达式计算， 可以编出如下函数： int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); ,问题：在函数 factorial 内又调用函数 factorial 本身，行吗？ 回答：行！ 首先按作用域规则，在函数 factorial 内又调用函数 factori

45、al 本身是合法的；其次 C 系统保证上述调用过程执行的正确性，这就是递归。 从静态行文看，在定义一个函数时，若在定义它的内部，又出现对它本身的调用，则称该函数是递归的，或递归定义的。 从动态执行角度看，当调用一个函数时，在进入相应函数，还没退出（返回）之前，又再一次的调用它本身，而再一次进入相应函数，则称之为递归，或称之为对相应函数的递归调用。 称递归定义的函数为递归函数。 上述函数 factorial 就是递归函数。若计算 5! ，使用函数调用factorial(5) ，观察其计算过程:,return 5*f(4),f(5),f=120,f(4),f(3),f(2),f(1),f(0),r

46、eturn 4*f(3),return 3*f(2),return 2*f(1),return 1*f(0),return 1,f=24,f=6,f=2,f=1,f=1,int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); void main() printf(“%dn”,f(5) ); ,递归程序设计,例8-15 X 的 n 次幂，可以定义为,float power ( float x, int n ) if ( n=0 ) return 1 ; else return x * power(x,n

47、-1) ; ,例8-16 n 次勒让德多项式,计算它的递归函数是: float p ( int n , float x ) if ( n=0 ) return 1 ; else if (n=1) return x ; else return ( (2*n-1)*x*p(n-1,x) - (n-1)*p(n-2,x) )/n ; ,递归程序设计的思想体现在： 用逐步求精原则，先把一个问题分解成若干子问题 这些子问题中有问题的与原始问题具有相同的特征属性，至多不过是某些参数不同，规模比原来小了 此时，就可以对这些子问题实施与原始问题同样的分析算法，直到规模小到问题容易解决或已经解决时为止。 也就是

48、说，若将整个问题的算法设计成一个函数，则解决这个子问题的算法就表现为对相应函数的递归调用.,再看 n! 的例子。该问题是：当n0 时，若能计算出 w=(n-1)! 则 r=n!=n*w 因此，得如下抽象算法： 1. 计算：w=(n-1)! 2. r=n*w 由于子算法 1 的特征属性与整个算法完全相同，只是参数不同，w 代替了 r ，n-1 代替了 n 。这时若将整个算法表示为 f( n,r ) 则子算法 1 就是 f( n-1,w ) 即是对f的递归调用。 再考虑n=0时，这时r=0!=1 ，从而得到计算 n! 的函数fact 。,void fact ( int n , int *r ) i

49、nt w ; if ( n=0 ) *r = 1 ; else factorial(n-1, *r = n*w ,若把该函数的参数r用函数值表示，就是前边的函数factorial 。,这里讲的只是一般规律和程序设计思想。实际使用时，设计递归函数要复杂得多。编写递归程序要注意： 递归程序漂亮、好看、好读、风格优美，但执行效率低。 计算! 的函数即可以写成循环形式，也可以写成递归形式。但是有些循环程序写成递归很困难。反之，有些递归程序写成循环也很困难，甚至是不可能的。 终结条件。程序一定要能终止，不能无限递归下去。 使用全局量要特别小心。用不好，单元发生冲突，将导致程序出错。,例8-17汉诺（ H

50、anoi ）塔游戏,该问题又称世界末日问题。相传，古印度布拉玛婆罗门神庙的憎侣们，当时作一种被称为 Hanoi塔的游戏。该游戏是：在一个平板上，有三根钻石针；在其中一根针上有成塔型落放的大小不等的64片金片；要求把这64片金片全部移到另一根钻石针上。移动规则是： 每次只允许移动一片金片； 移动过程中的任何时刻，都不允许有较大的金片放在较小的金片的上面； 移动过程中，三根钻石针都可以利用，但是金片不许放在除钻石针以外的任何地方。 不论白天黑夜都有一个憎侣在移动。据说当64片金片全部从一根钻石针移到另一根钻石针上那天，就是世界的末日。到那时他们的虔诚信徒可以升天，而其他人则要下地狱。,当然这只是传

51、说，按照规则把 64 片金片全部从一根针移到另一根针上，总的移动次数是 264-1次，若一秒移动一次，不发生错误，日夜不停的移动，约需 5849 亿年。而太阳系的寿命仅有100150亿年而已。,请编程序，打印金片的移动顺序。,解：不妨设三根钻石针顺次编号为 a 、b 、c ；开始所有 64 片金片全部在 a 针上；现在要把它们移动到 b 针上；移动过程中 c 针可以利用。如图所示,a b c,试想，若能够把a 针上的64片金片全部移动到b针上，必须能够先把a针顶部的63片金片移到c针上。 现在，可以很容易的把a针上的一片金片移到 b 针上。 最后，再按照把a针上的63片金片移到c针上的算法，把

52、c针上的63片金片全部移到b针上。从而，完成了题目要求的工作。 重新观察上述过程：,怎样进行移动？ 开始就遇到把a针最上边的金片先移到b针上，还是先移到c针上？没有任何根据作出决定，按一般方法是不好解决这个问题的。 下边换一个角度来考虑该问题：,按这个想法，移动 64 片金片的问题可以被分解成： 把a针上63片金片，从a针移到c针上，移动过程中b针可用； 把a针上一片金片移到b针上； 把c针上63片金片，从c针移到b针上，移动过程中a针可用。 到此，问题虽然没有解决，但是已经向解的方向前进了一步，移动64 片金片的问题变成移动 63 片金片的问题了。这一步虽然很小, 甚至是微不足道的，但是却是

53、十分重要的。,a b c,设若有一函数 move( n , x , y , z ) 能够完成：“把 x 针上的 n 片金片，移动到 y 针上，移动过程中可以利用 z 针。”， 则上述原始问题可以描述成对 move 的调用： move( 64 , a , b , c ) move( 63 , a , c , b ) move( 63 , c , b , a ),考虑move函数: 按分解移动 64 片金片问题的思路，问题： “把x针上的n片金片，移动到y针上，移动过程中z针可用”可被分解成： 把 x 针上 n-1 片金片，从 x 针移到 z 针，移动过程中 y 针可用 把 x 针上一片金片移到

54、y 针上； 把 z 针上 n-1 片金片，从 z 针移到 y 针，移动过程中 x 针可用 按该分解算法，并考虑递归出口 (显然，当移动金片的片数为 0 时，便不用移动了)，最后得到完整的 Hanoi 塔解法程序如下,void moveone ( char u , char v ) printf ( “%c - %cn” , u , v ); void move ( int n, char x, char y, char z ) if ( n0 ) move( n-1 , x,z,y ); moveone( x,y ); move( n-1 , z,y,x ) int main(void) in

55、t n ; printf( “pleace input n:”); scanf( “%d” , move ( n , a , b , c ) ,执行 hanoi 程序时不要输入太大的 n ，我们执行该程序。,执行主程序： 1、输出提示信息； 2、要求输入金片个数 n ，设输入“3”； 3、调用move函数：进入move ；n=30， 参数替换后，实际,printf( “pleace input n:”); scanf( “%d” , move ( n , a , b , c ),move( n-1 , x , z , y ); moveone( x , y ); move( n-1 , z ,

56、 y , x ),move( 2 , a , c , b ); moveone( a , b ); move( 2 , c , b , a ),执行调用move ( 2 , a , c , b )： 调用move函数：进入move ；n=20，执行 参数替换后，实际是执行：,printf( “pleace input n:”); scanf( “%d” , move ( n , a , b , c ),move( n-1 , x , z , y ); moveone( x , y ); move( n-1 , z , y , x );,move( 2 , a , c , b ); moveone( a , b ); move( 2 , c , b , a );,move( 1 , a , b , c ); moveone( a , c ); move( 1 , b , c , a );,执行调用move ( 1 , a , b , c )： 调用move函数：进入move ；n=10，执行