第3章函数精选PPT.ppt

《第3章函数精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章函数精选PPT.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章函数章函数第1页，本讲稿共88页main()fun2()fun1()fun3()funa()funb()func()图3.1 函数调用层次关系第2页，本讲稿共88页库函数和自定义函数：库函数或标准函数，是由编译系统预定义的，如一些常用的数学计算函数、字符串处理函数、图形处理函数、标准输入输出函数等。库函数都按功能分类，集中说明在不同的头文件中。用户只需在自己的程序中包含某个头文件，就可直接使用该文件中定义的函数。用户根据需要将某个具有相对独立功能的程序定义为函数，称自定义函数。第3页，本讲稿共88页3.1.2 函数的定义函数的定义函数声明的语法形式函数声明的语法形式类型标识符类型标识符

2、 函数名（形式参数表）函数名（形式参数表）语句序列语句序列若无参数，可省略或写若无参数，可省略或写void若无返回值，写若无返回值，写voidl l 形式参数表形式参数表 name1,name2,.,namenl 函数的返回值函数的返回值n由由 return 语句给出，例如：语句给出，例如：return 0；n无返回值的函数（无返回值的函数（void类型），不必写类型），不必写return语句。语句。第4页，本讲稿共88页/打印一个表头打印一个表头void TableHead()cout*endl;cout*example *endl;cout*endl;int input()/输入满足要求的

3、数据输入满足要求的数据int n;cout输入一个大于输入一个大于5的整数：的整数：n;while(n=b?a:b);1）有参函数的参数表中列出所有形式参数的类型和参数名称。各参数即使类型相同也必须分别加以说明。2）形式参数简称形参，只能是变量名，不允许是常量或表达式。3）C+中不允许函数的嵌套定义，即不允许在一个函数中定义另一个函数。void delay(long n)int i;for(i=0;in;i+);/延时一段时间延时一段时间第6页，本讲稿共88页3.1.3 函数的调用函数的调用函数调用：所谓函数调用，就是使程序转去执行函数体。无参函数的调用格式：函数名()有参函数的调用格式：函数

4、名(实际参数表)其中实际参数简称实参，用来将实际参数的值传递给形参，因此可以是常量、具有值的变量或表达式。第7页，本讲稿共88页程序如下：#include using namespace std;float max(float a,float b)return(a=b?a:b);int main()float x,y;cout输入两个实数：xy;coutx和y中较大数为max(x,y)endl;return 0；main()函数函数调用调用max(2.5,4.7)函数函数max(2.5,4.7)return 4.7 主程序后续语主程序后续语句句【例3.1】输入两个实数，输出其中较大的数。其中求

5、两个实数中的较大数用函数完成。第8页，本讲稿共88页3.2 函数的参数传递、返回值及函数声明函数的参数传递、返回值及函数声明 3.2.1 函数的参数传递及传值调用函数的参数传递及传值调用 传值调用和引用调用：传值调用和引用调用：按照参数形式的不同，按照参数形式的不同，C+有两种调用方式：有两种调用方式：传值调用传值调用和和引用调用引用调用。传值调用传递的是实参的值，本章介绍。传值调用传递的是实参的值，本章介绍传值调用。传值调用。第9页，本讲稿共88页传值调用：将实参的值复制给形参，在函数中参加运算的是形参，而实参不会发生任何改变。传值调用起了一种隔离作用。第10页，本讲稿共88页调用调用pow

6、er(4.6,3)函数函数power(4.6,3)return 97.336 主程序后续语主程序后续语句句n=3x=4.6c=a【例3.2】实参和形参对应关系的示例。float power(float x,int n)/求x的n次幂float p=1;while(n-)p*=x;return p;int main()int n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;return 0;第11页，本讲稿共88页调

7、用调用power(a,3)函数函数power(97,3)return 912673 主程序后续语句主程序后续语句n=3x=4.6c=a【例32】实参和形参对应关系。float power(float x,int n)/求x的n次幂float p=1;while(n-)p*=x;return p;int main()int n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;return 0;第12页，本讲稿共88页调用

8、调用power(3,4.6)函数函数power(3,4)return 81 主程序后续语句主程序后续语句n=3x=4.6c=a【例32】实参和形参对应关系。float power(float x,int n)/求x的n次幂float p=1;while(n-)p*=x;return p;int main()int n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;return 0;第13页，本讲稿共88页3.2.2

9、函数返回值函数返回值return语句的格式：return 表达式；【例【例3.3】设计函数，根据三角形的三边长求面积。如果不】设计函数，根据三角形的三边长求面积。如果不能构成三角形，给出提示信息。能构成三角形，给出提示信息。分析：函数为计算三角形面积，一般三角形分析：函数为计算三角形面积，一般三角形返回面积值返回面积值，若不能构成三角形则若不能构成三角形则返回返回-1。设计一个主函数完成函数测。设计一个主函数完成函数测试。根据返回值情况输出相应结果。试。根据返回值情况输出相应结果。第14页，本讲稿共88页【例3.3】程序：float TriangleArea(float a,float b,f

10、loat c)if(a+b=c)|(a+c=b)|(b+c=a)return-1;float s;s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c);int main()float a,b,c,area;cout输入三角形三边a,b,c:abc;area=TriangleArea(a,b,c);if(area=-1)cout(a,b,c )不能构成三角形！endl;else cout三角形(a,b,c )面积为：areaendl;return 0;第15页，本讲稿共88页讨论：讨论：函数可以有返回值，也可以没有返回值。对于没有返回函数可以有返回值，也可以没有

11、返回值。对于没有返回值的函数，功能只是完成一定操作，应将返回值类型定值的函数，功能只是完成一定操作，应将返回值类型定义为义为void，函数体内可以没有，函数体内可以没有return语句，当需要在程序语句，当需要在程序指定位置退出时，可以在该处放置一个：指定位置退出时，可以在该处放置一个：return；返回值是如何返回到调用处的？返回值是如何返回到调用处的？第16页，本讲稿共88页3.2.3 函数声明函数声明 函数声明是一条以分号结束的语句：类型标识符 函数名（形式参数表）；为什么需要函数声明？函数声明的格式：第17页，本讲稿共88页例如【例例如【例3.33.3】中求三角形面积的】中求三角形面积

12、的函数声明函数声明为：为：float TriangleArea(float a,float b,float c);或或float TriangleArea(float,float,float);但下面的函数原型是错误的：但下面的函数原型是错误的：int TriangleArea(float,float,float);/错误，返回值类型不同错误，返回值类型不同float TriangleArea(int,int,int);/错误，参数类型不同错误，参数类型不同float TriangleArea(float,float);/错误，参数个数不同错误，参数个数不同float TriangleArea

13、(float a,float b,float c)if(a+b=c)|(a+c=b)|(b+cchoice;while(choice=4);switch(choice)case 1:account_report();break;case 2:engineering_report();break;case 3:marketing_report();break;return 0;第19页，本讲稿共88页void menu_print()cout”系统功能：系统功能：”endl;cout”1财务报表财务报表”endl;cout”2工程报表工程报表”endl;cout”3市场报表市场报表”endl;c

14、out”选择业务序号：选择业务序号：”;void account_report()/生成财务报表生成财务报表void engineering_report()/生成工程报表生成工程报表 void marketing_report()/生成市场报表；生成市场报表；第20页，本讲稿共88页【例3.4】输出所有满足下列条件的正整数m：10m1000且m、m2、m3均为回文数。分析：分析：回文指左右对称的序列。如回文指左右对称的序列。如121、353等就是回文等就是回文数。判断整数是否回文数用函数实现，其思想是将该数数。判断整数是否回文数用函数实现，其思想是将该数各位拆开后反向组成新的整数，如果该整数

15、与原数相等各位拆开后反向组成新的整数，如果该整数与原数相等则为回文数。则为回文数。m m*m m*m*m11 121 1331101 10201 1030301111 12321 1367631 运行结果：运行结果：第21页，本讲稿共88页bool palindrome(int);/函数声明函数声明int main()int m;coutsetw(10)msetw(20)m*m“setw(20)m*m*mendl;for(m=11;m1000;m+)if(palindrome(m)&palindrome(m*m)&palindrome(m*m*m)coutsetw(10)msetw(20)m*

16、msetw(20)m*m*0);for(j=0;ji;j+)n=n*10+digitj;return(n=m);第23页，本讲稿共88页课堂练习 编写函数把华氏温度转化为摄氏温度，编写函数把华氏温度转化为摄氏温度，公式为：公式为：C=（F-32）5/9；在主函数中计；在主函数中计算输出算输出30、35、40、45、50、55、60华氏华氏温度对应的摄氏温度对照表。温度对应的摄氏温度对照表。第24页，本讲稿共88页3.3 全局变量和局部变量全局变量和局部变量3.3.1 3.3.1 变量的存储机制与变量的存储机制与C+的内存布局的内存布局 操作系统为一个C+程序的运行所分配的内存分为四个区域，如图

17、所示：栈区（函数局部数据）全局数据区(全局、静态)代码区（程序代码）（main()函数局部数据）自由存储区(动态数据)第25页，本讲稿共88页 3.3.2 全局变量全局变量 在所有函数之外定义的变量称为在所有函数之外定义的变量称为全局变量全局变量。全全局局变变量量存存放放在在全全局局数数据据区区，因因编编译译器器自自动动将将该该区区清清为为全全0，如如果果用用户户在在定定义义时时不不显显式式给给出出初初始始化化值值，则则等等效初始化为全效初始化为全0。全全局局变变量量可可定定义义在在程程序序开开头头，也也可可定定义义在在中中间间位位置置，该该全全局局变变量量在在定定义义处处之之后后的的任任何何

18、位位置置都都是是可可以以访访问问的的，称称为为可见的可见的。【例【例3.5】多个函数使用全局变量的例子。多个函数使用全局变量的例子。全局变量引入：第26页，本讲稿共88页打印打印200调用调用func()函数函数func()200*2=400打印打印400n=100n=100*2=200【例3.5】多个函数使用全局变量的例子。int n=100;void func()n*=2;int main()n*=2;coutnendl;func();coutnendl;return 0;第27页，本讲稿共88页3.3.3 局部变量局部变量 定义在函数内或块内的变量称为定义在函数内或块内的变量称为局部变量

19、局部变量。程序中使用的绝大多数变量都是局部变量。程序中使用的绝大多数变量都是局部变量。局局部部变变量量在在程程序序运运行行到到它它所所在在的的块块时时建建立立在在栈栈中中，该该块块执执行行完完毕毕局局部部变变量量占占有有的的空空间间即即被被释释放放。故故亦亦称称为为自自动动变量变量。局局部部变变量量在在定定义义时时可可加加修修饰饰词词auto，但但通通常常省省略略。局局部变量在定义时若未初始化，其值为部变量在定义时若未初始化，其值为随机数随机数。局部变量引入：【例3.6】使用局部变量的例子。第28页，本讲稿共88页打印打印main()中中的的t=3.5调用调用fun()函数函数fun()打印打

20、印fun()中的中的t=5 打印打印main()中中的的t=3.5t=3.5t=5【例3.6】使用局部变量的例子。void fun()auto int t=5;/fun()中的局部变量，auto可省略coutfun()中的t=tendl;int main()float t=3.5;/main()函数中的局部变量coutmain()中的t=tendl;fun();coutmain()中的t=tendl;return 0;第29页，本讲稿共88页3.4 函数调用机制函数调用机制 局局部部变变量量占占用用的的内内存存是是在在程程序序执执行行过过程程中中“动动态态”地地建建立立和和释释放放的。这种的。

21、这种“动态动态”是通过栈由系统是通过栈由系统自动自动管理进行的。管理进行的。（1）建立栈空间；）建立栈空间；（6）恢复现场：取主调函数运行状态及返回地址，释放栈空间；）恢复现场：取主调函数运行状态及返回地址，释放栈空间；（7）继续主调函数后续语句。）继续主调函数后续语句。（5）释放被调函数中局部变量占用的栈空间；）释放被调函数中局部变量占用的栈空间；（4）执行被调函数函数体；）执行被调函数函数体；（3）为被调函数中的局部变量分配空间，完成参数传递；）为被调函数中的局部变量分配空间，完成参数传递；（2）保护现场：主调函数运行状态和返回地址入栈；）保护现场：主调函数运行状态和返回地址入栈；调用过程

22、：第30页，本讲稿共88页void fun1(int,int);void fun2(float);int main()int x=1;y=2;fun1(x,y);return o;void fun1(int a,int b)float x=3;fun2(x);void fun2(float y)int x;x栈顶栈底y3fun2()fun1()运行状态及返回地址x3b2a1fun1()main()运行状态及返回地址y2x1main()操作系统运行状态及返回地址此图例说明在程序执行过程中怎样通过栈此图例说明在程序执行过程中怎样通过栈“动态动态”地地建立和释放局部变量占用的内存的建立和释放局部变量

23、占用的内存的第31页，本讲稿共88页 3.5 作用域与标识符的可见性作用域与标识符的可见性3 文件域 2 函数声明域 作作用用域域：指指标标识识符符能能够够被被使使用用的的范范围围。只只有有在在作作用用域域内内标标识符才可以被访问（称为可见）。识符才可以被访问（称为可见）。本本节节重重点点讨讨论论局局部部域域和和文文件件域域（全全局局域域），其其中中局局部部域域包包括括块块域域和和函函数数声声明明域域。任任何何标标识识符符作作用用域域的的起起始始点点均为均为标识符说明标识符说明处。处。下面分别介绍：1 块域 第32页，本讲稿共88页 函函数数中中定定义义的的标标识识符符，包包括括形形参参和和函

24、函数数体体中中定定义义的的局局部部变量，作用域都在该函数内，也称作变量，作用域都在该函数内，也称作函数域函数域。1、块域块块指指一一对对大大括括号号括括起起来来的的程程序序段段。块块中中定定义义的的标标识识符符，作用域在块内。作用域在块内。复合语句是一个块。复合语句是一个块。函数也是一个块。函数也是一个块。复合语句中定义的标识符，复合语句中定义的标识符，作用域仅在该复合语句中。作用域仅在该复合语句中。【例【例3.7】输入两数，按从大到小的顺序保存。输入两数，按从大到小的顺序保存。块的引入：第33页，本讲稿共88页a=3 b=535a=3 b=5a=5 b=3【例3.7】输入两数，按从大到小的顺

25、序保存，并输出结果。结果栈t=3 int main()int a,b;/具有函数域具有函数域 cout输入两整数：输入两整数：ab;cout“a=atb=b=a)int t;/具有块域具有块域 t=a;a=b;b=t;/交换交换a,b的值的值 couta=atb=bendl;return 0;上述程序若在最后一个cout语句处增加：couttendl;则编译时会提示错误，因为变量t的作用域只在if语句中，其它地方不可见。第34页，本讲稿共88页由由VC+运行，结果如下：运行，结果如下：输入两整数：输入两整数：3 5调用前：实参调用前：实参a=3,b=5调用中调用中交换前：形参交换前：形参a=3

26、,b=5交换后：形参交换后：形参a=5,b=3调用后：实参调用后：实参a=3,b=5 交换失败交换失败局部变量具有局部作用域使得程序在不同块中可以使用同名变量。局部变量具有局部作用域使得程序在不同块中可以使用同名变量。这些同名变量各自在自己的作用域中可见，在其它地方不可见。这些同名变量各自在自己的作用域中可见，在其它地方不可见。【例3.8】设计函数完成两数交换，用主函数进行测试。操作系统运行状态及返回地址操作系统运行状态及返回地址main()3a5bmain()运行状态及返回地址运行状态及返回地址swap()3a5b3t35第35页，本讲稿共88页【例【例3.8】设计函数完成两数交换，用主函数

27、进行测试。】设计函数完成两数交换，用主函数进行测试。void swap(int,int);int main()int a,b;/a,b作用域为作用域为main()cout输入两整数：输入两整数：ab;cout调用前：实参调用前：实参a=a,b=bendl;swap(a,b);/传值传值 cout调用后：实参调用后：实参a=a,b=bendl;return 0;void swap(int a,int b)/a,b作用域为作用域为swap()cout调用中调用中endl;cout交换前：形参交换前：形参a=a,b=bendl;int t;t=a;a=b;b=t;/交换交换swap()中的中的a,b

28、的值的值 cout交换后：形参交换后：形参a=a,b=bendl;第36页，本讲稿共88页如果块内定义的局部变量与全局变量同名，块内仍然局如果块内定义的局部变量与全局变量同名，块内仍然局部变量优先，但与块作用域不同的是，在块内可以通过部变量优先，但与块作用域不同的是，在块内可以通过域运算符域运算符“:”访问同名的全局变量。访问同名的全局变量。【例3.9】显示同名变量可见性。第37页，本讲稿共88页全局n=100100 200 300内内 i=500内内 j=600内内n=500+600 =11001100 500 600100200+300=500500 500 200 300外部外部 i=2

29、00外部外部 j=300【例3.9】显示同名变量可见性。int n=100;#include int main()int i=200,j=300;cout ntitjendl;/内部块 int i=500,j=600,n;n=i+j;cout ntitj endl;/输出局部变量n cout:nendl;/输出全局变量n n=i+j;/修改全局变量cout ntitj endl;return 0;第38页，本讲稿共88页2、函数声明域、函数声明域 函数声明不是定义函数，在作函数声明时，其中的形参作用域只在声明中，即作用域结束于右括号。正是由于形参不能被程序的其他地方引用，所以通常只要声明形参个

30、数和类型，形参名可省略。第39页，本讲稿共88页3、文件域、文件域 文件域也称全局域。定义在所有函数之外的标识符作用域为从定义处到整个源文件结束，即文件域。文件中定义的全局变量和函数的作用域为文件域。第40页，本讲稿共88页存存储储类类型型（storage class）决决定定标标识识符符的的存存储储区区域域，即即编编译译系系统统在在不不同同区区域域为为不不同同存存储储类类型型的的标标识识符符分分配配空空间间。由由于于存存储储区区域域不不同同，标标识识符符的的生生命命期期也也不不同同。所所谓谓生生命命期期，指指的的是是标标识识符符从从获获得得空空间间到到空空间间释释放放之之间间的的期期间间，标

31、标识识符符只只有有在在生生存存期期中中、并并且且在在其其自自己的作用域中才能被访问。己的作用域中才能被访问。3.6 存储类型与标识符的生命期存储类型与标识符的生命期 第41页，本讲稿共88页3.6.1 存储类型存储类型 存储类型的说明符（storage class specifier）autoregisterstaticextern 其中用auto和register修饰的称为自动存储类型，用static修饰的称为静态存储类型，用extern修饰的称为外部存储类型。第42页，本讲稿共88页1、自动存储类型自动变量为用自动变量为用auto说明的变量，通常说明的变量，通常auto缺省。局部变量缺省。

32、局部变量都是自动变量，生命期开始于块的执行，结束于块的结束，都是自动变量，生命期开始于块的执行，结束于块的结束，其原因是自动变量的空间分配在栈中，块开始执行时系统其原因是自动变量的空间分配在栈中，块开始执行时系统自动分配空间，块执行结束时系统自动释放空间。故自动自动分配空间，块执行结束时系统自动释放空间。故自动变量的生命期和作用域是一致的。变量的生命期和作用域是一致的。为提高程序运行效率，可以将某些变量保存在为提高程序运行效率，可以将某些变量保存在寄存器中，即用寄存器中，即用register说明为寄存器变量，说明为寄存器变量，但不提倡使用但不提倡使用。第43页，本讲稿共88页static说明的

33、变量称为静态变量。说明的变量称为静态变量。位位置置不不同同区区别别局局部部静静态态变变量量和和全全局局静静态态变变量，也称内部静态变量和外部静态变量。量，也称内部静态变量和外部静态变量。静静态态变变量量均均存存储储在在全全局局数数据据区区，如如果果程程序序未显式给出初始化值，则未显式给出初始化值，则等效初始化为全等效初始化为全0。静静态态变变量量占占有有的的空空间间要要到到整整个个程程序序执执行行结结束束才才释释放放，故故静静态态变变量量具具有有整整个个程程序序执执行行期期间间的生命期。的生命期。2、静态存储类型第44页，本讲稿共88页局局部部静静态态变变量量是是定定义义在在块块中中的的静静态

34、态变变量量，编编译译系系统统在在全全局局数数据据区区为为其其开开辟辟空空间间并并保保存存数数据据，如如果果显显式式给给出出初初始始化化值值，则则在在该该块块第第一一次次执执行行时完成，且只进行一次。时完成，且只进行一次。【例3.10】自动变量与局部静态变量的区别第45页，本讲稿共88页【例3.10】自动变量与局部静态变量的区别 int st()static int t=100;/局部静态变量 t+;return t;int at()int t=100;/自动变量 t+;return t;int main()int i;for(i=0;i5;i+)coutat()t;coutendl;for(i

35、=0;i5;i+)coutst()t;coutendl;return 0;i=0t=10012345101101101101101第46页，本讲稿共88页i=0t=10012101345102103104105【例【例3.10】自动变量与局部静态变量的区别自动变量与局部静态变量的区别 int st()static int t=100;/局部静态变量局部静态变量 t+;return t;int at()int t=100;/自动变量自动变量 t+;return t;int main()int i;for(i=0;i5;i+)coutat()=t;coutendl;for(i=0;i5;i+)co

36、utst()t;coutendl;return 0;第47页，本讲稿共88页3.6.2 生命期生命期1.静态生命期 静态生命期（Static extent或Static storage duration）指的是标识符从程序开始运行时就存在，到程序运行结束时消亡，释放存储空间。具有静态生命期的标识符存放在全局数据区，具有静态生命期的标识符在未被用户初始化的情况下，系统会等效将其初始化为全0。函数驻留在代码区，也具有静态生命期。所有具有文件作用域的标识符都具有静态生命期。第48页，本讲稿共88页2.2.2.2.局部生命期局部生命期局部生命期局部生命期 在函数内部或块中定义的标识符具有局部生命期（A

37、utomatic extent或Automatic storage duration），其生命期开始于执行到该函数或块的标识符定义处，结束于该函数或块的结束处。具有局部生命期的标识符存放在栈区。具有局部生命期的标识符如果未被初始化，其内容是随机的，不可引用。具有局部生命期的标识符必定具有局部作用域；但反之不然，静态局部变量具有局部作用域，但却具有静态生命期。第49页，本讲稿共88页具有动态生命期（dynamic extent或dynamic storage duration）的标识符存放在自由存储区，由特定的函数调用或运算来创建和释放，如用new运算符（或调用malloc()函数）为变量分配存

38、储空间时，变量的生命期开始，而用delete运算符（或调用free()函数）释放空间或程序结束时，变量生命期结束。关于new运算符和delete运算符将在第七章中介绍。3.动态生命期第50页，本讲稿共88页3.7 函数的递归调用函数的递归调用 递递归归是是一一种种描描述述问问题题的的方方法法，或或称称算算法法。递递归归的的思思想想可可以以简单地描述为简单地描述为“自己调用自己自己调用自己”。例如用如下方法定义阶乘：。例如用如下方法定义阶乘：可以看出是用阶乘定义阶乘，这种自己定义自己的方法称为递归定义。递归的引入：递归的分类直接递归间接递归本节只介绍直接递归。第51页，本讲稿共88页递归定义的阶

39、乘函数：fac(int n)int y;if(n=0|n=1)y=1;else y=n*fac(n-1);return y;只要设计主函数调用阶乘函数，即可实现计算阶乘。递归函数必须定义递归终止条件（Stopping condition），避免无穷递归（Infinite Recursion）。【例3.12】求4！运行结果：4 3 2 1 1 2 6 244!=24第52页，本讲稿共88页【例3.12】求4！#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;int main()

40、coutn4!=fac(4)endl;return o;n=4cout4;y=4*fac(3);fac(4)=cout2;y=2*fac(1);n=2cout1;y=1;cout1;return 1;n=1 n=3cout3;y=3*fac(2);cout24;return 24;cout6;return 6;cout2;return 2;24第53页，本讲稿共88页递归过程的分析：递归过程的分析：递归函数的执行分为递归函数的执行分为“递推递推”和和“回归回归”两个两个过程，这两个过程由递归终止条件控制，即过程，这两个过程由递归终止条件控制，即逐层逐层递推递推，直至，直至递归终止条件递归终止条

41、件，然后，然后逐层回归逐层回归。每次。每次调用发生时都首先判断递归终止条件。调用发生时都首先判断递归终止条件。第54页，本讲稿共88页现场与返回地址现场与返回地址第一层第一层fac(4)域域4n4*624y现场与返回地址现场与返回地址第二层第二层fac(3)域域3n3*26y现场与返回地址现场与返回地址第三层第三层fac(2)域域2n2*12y现场与返回地址现场与返回地址第四层第四层fac(1)域域ny11存存fac(1)返回值返回值存存fac(2)返回值返回值存存fac(3)返回值返回值126fac(4)返回值返回值=24main()域注意：注意：右图中存右图中存“fac(fac(1 1)返

42、回值返回值”等的存储单元是等的存储单元是无名临时局无名临时局部变量部变量，其生命期在表达式，其生命期在表达式y=n*fac(n-1)中。中。因为被调函数的返回语句格因为被调函数的返回语句格式为：式为：return 表达式表达式;为返回表达式的值，必须有为返回表达式的值，必须有一个一个无名临时局部变量无名临时局部变量来来承承载载这个值。这个值。然后由主调函数然后由主调函数中包含调用的表达式语句从中包含调用的表达式语句从该临时变量中取得值，表达该临时变量中取得值，表达式语句执行后该临时变量撤式语句执行后该临时变量撤销。销。存存fac(4)返回值返回值24第55页，本讲稿共88页【例3.14】输入一

43、个整数，用递归算法将整数倒序输出【例3.13】汉诺塔问题第56页，本讲稿共88页【例3.13】汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由A柱搬动到C柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。第57页，本讲稿共88页分析：分析：1 A1 A柱只有一个盘子的情况：柱只有一个盘子的情况：A A柱柱C C柱；柱；2 2 A A柱柱有有两两个个盘盘子子的的情情况况：小小盘盘A A柱柱B B柱柱，大大盘盘A A柱柱C C柱柱，小盘小盘B B柱柱C C柱。柱。3 3 A A柱柱有有n n

44、个个盘盘子子的的情情况况：将将此此问问题题看看成成上上面面n-1n-1个个盘盘子子和和最最下下面面第第n n个个盘盘子子的的情情况况。n-1n-1个个盘盘子子A A柱柱B B柱柱，第第n n个个盘盘子子A A柱柱C C柱柱，n-1n-1个个盘盘子子B B柱柱C C柱柱。问问题题转转化化成成搬搬动动n-1n-1个个盘盘子子的的问问题题，同同样样，将将n-1n-1个个盘盘子子看看成成上上面面n-2n-2个个盘盘子子和和下下面面第第n-1n-1个个盘盘子子的的情情况况，进进一一步步转转化化为为搬搬动动n-2n-2个个盘盘子子的的问问题题，类类推推下下去去，一一直直到到最最后后成成为为搬搬动动一一个个

45、盘盘子子的的问问题题。这是一个典型的递归问题，递归结束于只搬动一个盘子。这是一个典型的递归问题，递归结束于只搬动一个盘子。第58页，本讲稿共88页算法：可以定义两个函数:一个是递归函数，命名为hanoi(int n,char source,char temp,char target)，实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move(char source,char target)，用来输出搬动一个盘子的提示信息。第59页，本讲稿共88页void move(char source,char target)coutsourcetargetendl;v

46、oid hanoi(int n,char source,char temp,char target)if(n=1)move(source,target);elsehanoi(n-1,source,target,temp);/将n-1个盘子搬到中间柱 move(source,target);/将最后一个盘子搬到目标柱hanoi(n-1,temp,source,target);/将n-1个盘子搬到目标柱 int main()int n;cout输入盘子数：n;hanoi(n,A,B,C);return 0;第60页，本讲稿共88页【例3.14】输入一个整数，用递归算法将整数倒序输出。分析：在递归过

47、程的递推步骤中用求余运算将整数的各个位分离，并打印出来。void backward(int n)if(n=10)coutnendl;return;else coutn%10;backward(n/10);void main()int n;cout输入整数：n;cout原整数：nendl反向数：;backward(n);coutendl;return 0;第61页，本讲稿共88页图3.10 递归求解斐波那契数列调用树同其他算法相比，用递归算法编制的程序非常简洁易读，但缺点是增加了内存的开销，在递推的过程中会占用大量栈空间，且连续的调用返回操作占用较多CPU时间。因此是否选择使用递归算法取决于所解

48、决的问题及应用的场合。【例3.15】采用递推法求解Fibonacii数列第62页，本讲稿共88页【例3.15】采用递推法求解Fibonacii数列，本例的递归调用过程参见图3.10。int fib(int n)if(n=0)return 0;else if(n=1)return 1;else return fib(n-1)+fib(n-2);int main()int i;for(i=0;i=19;i+)/将19改为69，可以看出计算到后面越来越缓慢。if(i%5=0)coutendl;coutsetw(6)fib(i);coutendl;return 0;第63页，本讲稿共88页从以上几例可

49、以看出，递归算法一般不需要借助循环，但通过不断递推和回归的过程实现了其他算法用循环完成的功能。因此，递归的终止条件非常重要，否则将会无休止地递归下去，陷入死循环状态。第64页，本讲稿共88页3.8.1 函数重载函数重载 重载的引入：在C+中，如果需要定义几个功能相似，而参数类型不同的函数，那么这样的几个函数可以使用相同的函数名，这就是函数重载。例：求和函数对应不同的参数类型可以定义如下几个重载函数：int sum(int a,int b)double sum(double a,double b)float sum(float a,float b,float c)3.8 函数的一些高级议题函数的

50、一些高级议题 第65页，本讲稿共88页重载匹配：重载匹配：当某个函数中调用到重载函数时，编译器会根据实当某个函数中调用到重载函数时，编译器会根据实参的类型去对应地调用相应的函数。匹配过程按如下步参的类型去对应地调用相应的函数。匹配过程按如下步骤进行：骤进行：（1）如果有严格匹配的函数，就调用该函数；）如果有严格匹配的函数，就调用该函数；（2）参数内部转换后如果匹配，调用该函数；）参数内部转换后如果匹配，调用该函数；（3）通过用户定义的转换寻求匹配。）通过用户定义的转换寻求匹配。因此在定义重载函数时必须保证参数类型不同，仅仅返回值类因此在定义重载函数时必须保证参数类型不同，仅仅返回值类型不同是不