《在结构化程序设计中函数是将任务进行模块划分的基本单位课件.ppt》由会员分享，可在线阅读，更多相关《在结构化程序设计中函数是将任务进行模块划分的基本单位课件.ppt（106页珍藏版）》请在三一办公上搜索。
1、在结构化程序设计中，函数是将任务进行模块划分的基本单位。,第四章 函数,要掌握函数的使用，必须理解函数调用时的内部实现机制，以及与此相关的内存分配机制、变量生命期和作用域。,本章还将介绍关于函数重载的概念，介绍递归算法、内联函数、默认参数函数以及多文件组织、编译预处理、工程文件的概念和运行库函数。,第四章 函数,41 函数的定义与调用,4 5 作用域与存储类型,44 函数调用机制,43 全局变量和局部变量,42 函数的参数传递,返回值及函数原型说明,49 编译预处理,4 8 头文件与多文件结构,4 7 函数的一些高级议题,4 6 函数的递归调用,4.1 函数的定义与调用,4.1.1 函数概述,
2、4.1.2 函数的定义,4.1.3 函数的调用,4.1C+的系统库函数,C+提供了一个很大的常用函数库，该函数库本身并不是C+语言的组成部分，所有库中的函数用户都可以自己定义，但直接使用库函数能给编程带来很大方便。系统函数库实际上是一系列源程序文件，每个文件中定义了若干常用函数及标识符，具有相同或相似功能的函数和标识符集中放在一个文件中。这些文件均以.h的形式命名，存放在系统目录的include子目录下。例如文件iostream.h中定义了与控制台输入输出和文件输入输出相关对象和成员函数，math.h中定义了大量数学函数，string.h中定义了大量与字符串操作相关的函数。,4.1C+的系统库
3、函数,C+提供了一个很大的常用函数库，该函数库本身并不是C+语言的组成部分，所有库中的函数用户都可以自己定义，但直接使用库函数能给编程带来很大方便。系统函数库实际上是一系列源程序文件，每个文件中定义了若干常用函数及标识符，具有相同或相似功能的函数和标识符集中放在一个文件中。这些文件均以.h的形式命名，存放在系统目录的include子目录下。例如文件iostream.h中定义了与控制台输入输出和文件输入输出相关对象和成员函数，math.h中定义了大量数学函数，string.h中定义了大量与字符串操作相关的函数。,math.h中几个常用的数学函数,4.1.1 函数概述,4.1.1 函数概述,函数按
4、是否带有参数，分为:无参函数和有参函数,4.1.1结束,函数按其是否系统预定义分为两类：一类是编译系统预定义的，称为库函数或标准函数，如一些常用的数学计算函数、字符串处理函数、图形处理函数、标准输入输出函数等。这些库函数都按功能分类，集中说明在不同的头文件中。用户只需在自己的程序中包含某个头文件，就可直接使用该文件中定义的函数。另一类是用户自定义函数，用户可以根据需要将某个具有相对独立功能的程序定义为函数。,4.1.2 函数的定义,1.无参函数,2.有参函数,1 无参函数,定义格式为：数据类型函数名(void)函数体,例:下面函数的功能是打印一个表头void TableHead()cout*e
5、ndl；cout*example*endl;cout*endl；,有参函数,有参函数的定义格式为数据类型函数名(参数类型1形式参数1,参数类型2形式参数2,函数体,例:下面函数的功能是返回两个整数中较大一个的值 int max(int a,int b)return(a=b?a:b);,定义函数时可能会涉及若干个变量，究竟哪些变量应当作为函数的参数？哪些应当定义在函数体内？这有一个原则：作为一个相对独立的模块，函数在使用时完全可以被看成“黑匣子”，除了输入输出外，其他部分可不必关心。从函数的定义看出，函数头正是用来反映函数的功能和使用接口，它所定义的是“做什么”，在这部分必须明确“黑匣子”的输入
6、输出部分，输出就是函数的返回值，输入就是参数。因此，只有那些功能上起自变量作用的变量才必须作为参数定义在参数表中；函数体中具体描述“如何做”，因此除参数之外的为实现算法所需用的变量应当定义在函数体内。C+中不允许函数的嵌套定义，即在一个函数中定义另一个函数。,提示,4.1.3 函数的调用,在C+中，除了主函数外，其他任何函数都不能单独作为程序运行。任何函数功能的实现都是通过被主函数直接或间接调用进行的。所谓函数调用，就是使程序转去执行函数体。无参函数的调用格式为：函数名();有参函数的调用格式为：函数名(实际参数表);其中实际参数简称实参，用来将实际参数的值传递给形参，因此可以是常量、具有值的
7、变量或表达式。,4.1.3 函数的调用,main()函数,调用max(2.5,4.7),函数max(2.5,4.7),return 4.7,主程序后续语句,【例41】输入两个实数，输出其中较大的数。其中求两个实数中的较大数用函数完成。程序如下：#includefloat max(float x,float y)return(x=y?x:y);void main()float x,y;coutxy;coutx和y中较大数为max(x,y)endl;,4.2 函数的参数传递、返回值及函数原型说明,421 函数的参数传递及传值调用,423 函数原型说明,422 函数返回值,函数调用首先要进行参数传递
8、，参数传递的方向是由实参传递给形参。传递过程是，先计算实参表达式的值，再将该值传递给对应的形参变量。一般情况下，实参和形参的个数和排列顺序应一一对应，并且对应参数应类型匹配（赋值兼容）,即实参的类型可以转化为形参类型。而对应参数的参数名则不要求相同。,4.2.1 函数的参数传递及传值调用,按照参数形式的不同，C+有两种调用方式：传值调用和引用调用。顾名思义，传值调用传递的是实参的值，本章主要介绍传值调用。,4.2.1 函数的参数传递及传值调用,调用power(4.6,3),函数power(4.6,3),return 97.336,主程序后续语句,【例42】说明实参和形参对应关系的示例。#inc
9、lude#includefloat power(float x,int n)/求x的n次幂float pow=1;while(n-)pow*=x;return pow;void 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;,4.2.1 函数的参数传递及传值调用,调用power(a,3),函数power(a,3),return 912673,主程序后续语句,【例42】说明实参和形参对应关系的示
10、例。#include#includefloat power(float x,int n)/求x的n次幂float pow=1;while(n-)pow*=x;return pow;void 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;,4.2.1 函数的参数传递及传值调用,调用power(3,4.6),函数power(3,4.6),return 81,主程序后续语句,【例42】说明实参和形参
11、对应关系的示例。#include#includefloat power(float x,int n)/求x的n次幂float pow=1;while(n-)pow*=x;return pow;void 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;,4.2.2 函数返回值,return语句的一般格式为：return 表达式；函数的计算结果通过该语句传递回主调函数。,【例43】设计函数，根据三角
12、形的三边长求面积。如果不能构成三角形，给出提示信息。分析：函数为计算三角形面积，一般三角形返回面积值，若不能构成三角形则返回-1。设计一个主函数完成函数测试。根据返回值情况输出相应结果。程序见下页：,#include#includefloat TriangleArea(float a,float b,float c)if(a+babc;area=TriangleArea(a,b,c);if(area=-1)cout(a,b,c)不能构成三角形！endl;elsecout三角形(a,b,c)面积为：areaendl;,4.2.2 函数返回值,函数可以有返回值，也可以没有返回值。对于没有返回值的函
13、数，功能只是完成一定操作，应将返回值类型定义为void，函数体内可以没有return语句，当需要在程序指定位置退出时，可以在该处放置一个：,return；,4.2.2结束,4.2.3 函数原型说明,函数原型是一条以分号结束的语句，实际上就是所定义函数的函数头，形如：函数返回值类型函数名(形参表);,语法上对程序文件中函数的排列次序是没有固定要求的，只要满足先定义后使用即可。但从结构化程序设计的角度，通常是先调用后定义。使用函数原型，则既符合由粗到精的思维方式，又满足了语法要求。,其中形参表可以逐个列出每个参数的类型和参数名，也可以列出每个形参的类型，参数名可省略，各形参之间以逗号分隔。函数原型
14、和所定义的函数必须在返回值类型、函数名、形参个数和类型及次序等方面完全对应一致，否则将导致编译错误。,下面是一个使用结构化程序设计思想开发的企业管理报表程序的框架。它使用了函数原型说明。#include void menu_print();void account_report();void engineering_report();void marketing_report();void main()int choice;do menu_print();cinchoice;while(choice=4);switch(choice)case 1:account_report();break;
15、case 2:engineering_report();break;case 3:marketing_report();break;,void menu_print()cout”系统功能：”endl;cout”1财务报表”endl;cout”2工程报表”endl;cout”3市场报表”endl;cout”选择业务序号：”;void account_report()/生成财务报表void engineering_report()/生成工程报表 void marketing_report()/生成市场报表；,4.2.3 函数原型说明,【例44】输出所有满足下列条件的正整数m：10m1000且m、m
16、2、m3均为回文数。,分析：回文指左右对称的序列。如121、353等就是回文数。判断整数是否回文数用函数实现，其思想是将该数各位拆开后反向组成新的整数，如果该整数与原数相等则为回文数。,程序如下：#include#includebool palindrome(int);/函数原型,void main()cout0);for(intj=0;ji;j+)n=n*10+digitj;return(n=m);,4.2.3 函数原型说明,m m*m m*m*m11 121 1331101 10201 1030301111 12321 1367631,运行结果：,4.3 全局变量和局部变量,431 变量的
17、存储机制与C+的内存布局,432 全局变量,433 局部变量,4.3.1 变量的存储机制与C+的内存布局,操作系统为一个C+程序的运行所分配的内存分为四个区域，如图，程序在内存中的区域所示：,（1）代码区（Code area）：存放程序代码，即程序中各个函数的代码块；（2）全局数据区（Data area）：存放全局数据和静态数据；分配该区时内存全部清零。（3）栈区（Stack area）：存放局部变量，如函数中的变量等；分配栈区时内存不处理。（4）堆区（Heap area）：存放与指针相关的动态数据。分配堆区时内存不处理。,4.3.1 变量的存储机制与C+的内存布局,4.3.2 全局变量,在所
18、有函数之外定义的变量称为全局变量。,全局变量在编译时建立在全局数据区，在未给出初始化值时系统自动初始化为全0。,全局变量可定义在程序开头，也可定义在中间位置，该全局变量在定义处之后的任何位置都是可以访问的，称为可见的。,请看下例：,4.3.2 全局变量,打印200,调用func(),函数func(),200*2=400,打印400,n=100,n=100*2=200,【例45】多个函数使用全局变量的例子。#includeint n=100;void func()n*=2;void main()n*=2;coutnendl;func();coutnendl;,4.3.3 局部变量,定义在函数内或
19、块内的变量称为局部变量。,程序中使用的绝大多数变量都是局部变量。,局部变量在程序运行到它所在的块时建立在栈中，该块执行完毕局部变量占有的空间即被释放。,局部变量在定义时可加修饰词auto，但通常省略。局部变量在定义时若未初始化，其值为随机数。,4.3.3 局部变量,打印main()中的t=3.5,调用fun(),函数fun(),打印fun()中的t=5,打印main()中的t=3.5,t=5,【例49】使用局部变量的例子。#includevoid fun()auto int t=5;/fun()中的局部变量，auto可省略coutfun()中的t=tendl;void main()float
20、t=3.5;/main()函数中的局部变量coutmain()中的t=tendl;fun();coutmain()中的t=tendl;,4.4 函数调用机制,局部变量占用的内存是在程序执行过程中“动态”地建立和释放的。这种“动态”是通过栈由系统自动管理进行的。当任何一个函数调用发生时，系统都要作以下工作：,（1）建立栈空间；,（6）恢复现场：取主调函数运行状态及返回地址，释放栈空间；,（7）继续主调函数后续语句。,（5）释放被调函数中局部变量占用的栈空间；,（4）执行被调函数函数体；,（3）为被调函数中的局部变量分配空间，完成参数传递；,（2）保护现场：主调函数运行状态和返回地址入栈；,4.4
21、 函数调用机制,void fun1(int,int);void fun2(float);void main()int x=1;y=2;fun1(x,y);void fun1(int a,int b)float x=3;fun2(x);void fun2(float y)int x;,此图例说明在程序执行过程中怎样通过栈“动态”地建立和释放局部变量占用的内存的,4.5 作用域与存储类型,4.5.1 作 用 域,4.5.2 变量的存储类型,4.5.3外部存储类型与静态存储类型,4.5.4 生命期与可见性,4.5.1 作用域,1 块作用域,3 文件作用域,2 函数原型作用域,作用域指标识符能够被使用
22、的范围。只有在作用域内标识符才可以被访问（称为可见）。,本节只讨论局部域和文件域（全局域），其中局部域包括块域和函数原型域。任何标识符作用域的起始点均为标识符说明处。,下面分别介绍：,参和函数体中定义的局部变量，作用域都在该函数内，也称作函数域。,块域,块指一对大括号括起来的程序段。块中定义的标识符，作用域在块内。,复合语句是一个块。,函数也是一个块。,复合语句中定义的标识符，,作用域仅在该复合语句中。,函数中定义的标识符，包括形,块域,3,5,a=3 b=5,a=5 b=3,【例47】输入两数，按从大到小的顺序保存，并输出结果。,结果,栈,t,=3,#includevoid main()in
23、t a,b;/具有函数域 coutab;cout=a)int t;/具有块域 t=a;a=b;b=t;/交换a,b的值 couta=atb=bendl;,【例48】设计函数完成两数交换，用主函数进行测试。#includevoid swap(int,int);void main()int a,b;/a,b作用域为main()coutab;cout调用前：实参a=a,b=bendl;swap(a,b);/传值 cout调用后：实参a=a,b=bendl;void swap(int a,int b)/a,b作用域为swap()cout调用中endl;cout交换前：形参a=“a,b=bendl;in
24、t t;t=a;a=b;b=t;/交换swap()中的a,b的值 cout交换后：形参a=a,b=bendl;,块作用域,由VC+平台运行，结果如下：输入两整数：3 5调用前：实参a=3,b=5调用中交换前：形参a=3,b=5交换后：形参a=5,b=3调用后：实参a=3,b=5 交换失败,局部变量具有局部作用域使得程序在不同块中可以使用同名变量。这些同名变量各自在自己的作用域中可见，在其它地方不可见。,块作用域,对于块中嵌套其它块的情况，如果嵌套块中有同名局部变量，服从局部优先原则，即在内层块中屏蔽外层块中的同名变量，换句话说，内层块中局部变量的作用域为内层块；外层块中局部变量的作用域为外层除
25、去包含同名变量的内层块部分。,如果块内定义的局部变量与全局变量同名，块内仍然局部变量优先，但与块作用域不同的是，在块内可以通过域运算符“：”访问同名的全局变量。,200 300,内 i=500,内 j=600,内n=500+600=1100,1100 500 600,100,200+300=500,500,500 200 300,外部 i=200,外部 j=300,【例49】显示同名变量可见性。int n=100;#includevoid main()int i=200,j=300;cout ntitjendl;/内部块 int i=500,j=600,n;n=i+j;cout ntitj e
26、ndl;/输出局部变量n cout:nendl;/输出全局变量n n=i+j;/修改全局变量cout ntitj endl;,函数原型作用域,函数原型不是定义函数，在作函数原型声明时，其中的形参作用域只在原型声明中，即作用域结束于右括号。正是由于形参不能被程序的其他地方引用，所以通常只要声明形参个数和类型，形参名可省略。,3 文件作用域,文件作用域也称全局作用域。定义在所有函数之外的标识符，具有文件作用域，作用域为从定义处到整个源文件结束。文件中定义的全局变量和函数都具有文件作用域。如果某个文件中说明了具有文件作用域的标识符，该文件又被另一个文件包含，则该标识符的作用域延伸到新的文件中。如ci
27、n和cout是在头文件iostream.h中说明的具有文件作用域的标识符，它们的作用域也延伸到嵌入iostream.h的文件中。,存储类型决定了变量的生命期，变量生命期指从获得空间到空间释放之间的时期。,4.5.2 变量的存储类型,存储类型的说明符有四个:auto,register,static和extern。前两者称为自动类型，后两者分别为静态和外部类型。,本节重点掌握static和extern这两种类型的使用和区别。具体说，区分局部变量和静态局部变量，全局变量和静态全局变量。,auto：前面提到的局部变量都是自动类型。其空间分配于块始，空间释放于块终，且由系统自动进行。自动变量保存在栈中，
28、且是在程序运行过程中获得和释放空间，未初始化时值为随机数。,4.5.2 变量的存储类型,register:为提高程序运行效率，可以将某些变量保存在寄存器中，即说明为寄存器变量，但不提倡使用。,static：静态变量。根据被修饰变量的位置不同，分为局部（内部）静态变量和全局（外部）静态变量。所有静态变量均存放在全局数据区，编译时获得存储空间，未初始化时自动全0，且只初始化一次。,局部静态变量的作用域为块域，但生命期为整个文件。即当块结束时，局部静态变量空间仍然保持，直到整个程序文件结束时该局部静态变量空间才释放，生命期结束。,局部静态变量,【例410】自动变量与局部静态变量的区别。（演示）,#i
29、nclude st()static int t=100;/局部静态变量 t+;return t;at()int t=100;/自动变量 t+;return t;void main()int i;for(i=0;i5;i+)coutat()t;coutendl;for(i=0;i5;i+)coutst()t;coutendl;,4.5.2 变量的存储类型,1,2,3,4,5,101,101,101,101,101,4.5.2 变量的存储类型,1,2,101,3,4,5,102,103,104,105,#include st()static int t=100;/局部静态变量 t+;return
30、t;at()int t=100;/自动变量 t+;return t;void main()int i;for(i=0;i5;i+)coutat()t;coutendl;for(i=0;i5;i+)coutst()t;coutendl;,全局静态变量,全局静态变量是指用static修饰的全局变量。有关内容在下节静态存储类型中介绍。,4.5.3 外部存储类型与静态存储类型,1.外部存储类型,2.静态存储类型,一个C+程序可以由多个源程序文件组成，编译系统将这若干个文件连接在一起，产生可执行程序。外部存储类型和静态存储类型确定了变量和函数在多文件程序中的联络关系。,1 外部存储类型,外部存储类型包括
31、外部变量和外部函数。在由多个源程序文件组成的程序中，如果一个文件要使用另一个文件中定义的全局变量或函数，这些源程序文件之间通过外部类型的变量和函数进行沟通。,在一个文件中定义的全局变量和函数都缺省为外部的，即其作用域可以延伸到程序的其他文件中。但其他文件如果要使用这个文件中定义的全局变量和函数，必须在使用前用“extern”作外部声明，外部声明通常放在文件的开头。,变量定义时编译器为其分配存储空间，而变量声明指明该全局变量已在其他地方说明过，编译系统不再分配存储空间，直接使用变量定义时所分配的空间。,函数声明缺省为外部的，因此修饰词extern通常省略。,1 外部存储类型,【例4.11】外部存
32、储类型的例子。假定程序包含两个源程序文件Ex4_11_1.cpp和Ex4_11_2.cpp，程序结构如下：/*Ex4_11_1.cpp，由main()组成*/#include void fun2();/外部函数声明，等价于extern void fun2();int n;/全局变量定义void main()n=1;fun2();/fun2()定义在文件Ex4_11_2.cpp中 coutn=nendl;/*Ex4_11_2.cpp，由fun2()组成*/extern int n;/外部变量声明，n定义在文件Ex4_11_1.cpp中void fun2()/fun2()被文件Ex4_11_1.c
33、pp中的函数调用n=3;运行结果：n=3,2 静态存储类型,静态存储类型包括静态全局变量和静态函数。在定义全局变量或函数时加说明符static，就成为静态变量或静态函数。静态存储类型的作用域与外部存储类型相反，一旦定义为静态存储类型，就限制该变量或函数只能在定义它的文件中使用。静态全局变量在编译时分配存储空间，如果定义时不指定初值，则编译系统将其初始化为全0。,一个全局变量和一个静态全局变量在使用上是不同的，其他文件通过外部变量声明可以使用一个全局变量，但却无法使用静态全局变量，静态全局变量只能被定义它的文件所独享。函数与静态函数之间的区别是相同的。,4.5.4 生命期与可见性,1.生命期,2
34、.可见性,1 生命期,（1）静态生命期,（2）局部生命期,（3）动态生命期,生命期（Life time）也叫生存期。生命期与存储区域相关，存储区域分为代码区、静态数据区、栈区和堆区，相应地，生命期分为静态生命期、局部生命期和动态生命期。,（1）静态生命期,静态生命期指的是标识符从程序开始运行时存在，即具有存储空间，到程序运行结束时消亡，即释放存储空间。具有静态生命期的标识符存放在静态数据区，属于静态存储类型，如全局变量、静态全局变量、静态局部变量。具有静态生命期的标识符在未被用户初始化的情况下，系统会自动将其初始化为全0。函数驻留在代码区，也具有静态生命期。所有具有文件作用域的标识符都具有静态
35、生命期。,（2）局部生命期,在函数内部或块中定义的标识符具有局部生命期，其生命期开始于执行到该函数或块的标识符声明处，结束于该函数或块的结束处。具有静态生命期的标识符存放在栈区。具有局部生命期的标识符如果未被初始化，其内容是随机的，不可用。具有局部生命期的标识符必定具有局部作用域；但反之不然，静态局部变量具有局部作用域，但却具有静态生命期。,（3）动态生命期,具有动态生命期的标识符由特定的函数调用或运算来创建和释放，如调用malloc()或用new运算符为变量分配存储空间时，变量的生命期开始，而调用free()或用delete运算符释放空间或程序结束时，变量生命期结束。具有动态生命期的变量存放
36、在堆区。关于new运算和delete运算将在指针一章中介绍。,可见性,可见性从另一个角度说明标识符的有效性，可见性与作用域具有一定的一致性。标识符的作用域包含可见范围，可见范围不会超过作用域。可见性在理解同名标识符的作用域嵌套时十分直观。对于外层块与内层块定义了同名标识符的，在外层作用域中，内层所定义的标识符是不可见的，即外层引用的是外层所定义的标识符；同样，在内层作用域中，外层的标识符将被内层的同名标识符屏蔽，变得不可见，即外层中同名标识符的可见范围为作用域中挖去内层块的范围。图4.6显示下面程序段中变量的作用域与可见性。,可见性,下面的程序段和图示显示作用域与可见性。int m=1;flo
37、at x;float m=3.5;X=5.5;m+;,int m,float x作用域int m可见float m不可见x可见,float m作用域float m可见int m不可见x可见,4.6 函数的递归调用,递归是一种描述问题的方法，或称算法。递归的思想可以简单地描述为“自己调用自己”。例如用如下方法定义阶乘：,可以看出是用阶乘定义阶乘，这种自己定义自己的方法称为递归定义。,在函数调用中，有这样两种情况，一种是在函数A的定义中有调用函数A的语句，即自己调用自己；另一种是函数A的定义中出现调用函数B的语句，而函数B的定义中也出现调用函数A的语句，即相互调用。前者称直接递归，后者称间接递归。
38、本节只介绍直接递归。递归函数必须定义递归终止条件（Stopping condition），避免无穷递归（Infinite Recursion）。递归定义的阶乘算法用函数描述为：fac(int n)if(n=0|n=1)return 1;else return n*fac(n-1);只要设计主函数调用阶乘函数，即可实现计算阶乘。,4.6 函数的递归调用,【例412】求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;void main()coutn4!=fac(4)endl
39、;,n=4,cout4;y=4*fac(3);,fac(4)=,cout2;y=2*fac(1);,n=2,cout1;y=1;cout1;return 1;,n=1,n=3,cout3;y=3*fac(2);,cout24;return 24;,cout6;return 6;,cout2;return 2;,24,递归函数的执行分为“递推”和“回归”两个过程，这两个过程由递归终止条件控制，即逐层递推，直至递归终止条件，然后逐层回归。每次调用发生时都首先判断递归终止条件。递归调用同普通的函数调用一样，每当调用发生时，在栈中分配单元保存返回地址以及参数和局部变量；而与普通的函数调用不同的是，由于
40、递推的过程是一个逐层调用的过程，因此存在一个逐层连续的参数入栈过程，直至遇到递归终止条件时，才开始回归，这时才逐层释放栈空间，返回到上一层，直至最后返回到主调函数。,4.6 函数的递归调用,4.6 函数的递归调用,【例413】汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由A柱搬动到C柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。,分析：1 A柱只有一个盘子的情况：A柱C柱；2 A柱有两个盘子的情况：小盘A柱B柱，大盘A柱C柱，小盘B柱C柱。3 A柱有n个盘子的情况：将此问题看成上面
41、n-1个盘子和最下面第n个盘子的情况。n-1个盘子A柱B柱，第n个盘子A柱C柱，n-1个盘子B柱C柱。问题转化成搬动n-1个盘子的问题，同样，将n-1个盘子看成上面n-2个盘子和下面第n-1个盘子的情况，进一步转化为搬动n-2个盘子的问题，类推下去，一直到最后成为搬动一个盘子的问题。这是一个典型的递归问题，递归结束于只搬动一个盘子。,4.6 函数的递归调用,4.6 函数的递归调用,算法可以描述为：1 n-1个盘子A柱B柱，借助于C柱；2 第n个盘子A柱C柱；3 n-1个盘子B柱C柱，借助于A柱；其中步骤1和步骤3继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递归函数，命名为
42、hanoi(int n,char source,char temp,char target)，实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move(char source,char target)，用来输出搬动一个盘子的提示信息。,#include void move(char source,char target)coutn;hanoi(n,A,B,C);,【例414】输入一个整数，用递归算法将整数倒序输出。分析：在递归过程的递推步骤中用求余运算将整数的各个位分离，并打印出来。#includevoid backward(int n)coutn;cou
43、t原整数：nendl反向数：;backward(n);coutendl;,4.6 函数的递归调用,n=247,cout7;backward(24);,n=2,cout2;return;,n=24,cout4;backward(2);,backward(247),return;,return;,coutendl;,求余总是取当前整数的最右一位，所以先输出余数后递归可实现倒序输出。如果先递归后输出余数，则是在回归的过程中输出，实现的就是正序输出。,从以上几例可以看出，递归算法一般不需要借助循环，但通过不断递推和回归的过程实现了其他算法用循环完成的功能。因此，递归的终止条件非常重要，否则将会无休止地
44、递归下去，陷入死循环状态。,【例4.15】在【例3.11】中采用递推法求解Fibonacii数列，本例用递归法求解。本例的递归调用过程参见图4.11。#include#includeint fib(int n)if(n=0)return 0;else if(n=1)return 1;else return fib(n-1)+fib(n-2);void main()for(int i=0;i=19;i+)/将19改为69，可以看出计算到后面越来越缓慢。if(i%5=0)coutendl;coutsetw(6)fib(i);coutendl;,4.6 函数的递归调用,图4.11 递归求解斐波那契数
45、列调用树,同其他算法相比，用递归算法编制的程序非常简洁易读，但缺点是增加了内存的开销，在递推的过程中会占用大量栈空间，且连续的调用返回操作占用较多CPU时间。因此是否选择使用递归算法取决于所解决的问题及应用的场合。,4.6 函数的递归调用,C+不允许对函数作嵌套定义，也就是说在一个函数中不能完整地包含另一个函数。在一个程序中每一个函数的定义都是互相平行和独立的。虽然C+不能嵌套定义函数，但可以嵌套调用函数，也就是说，在调用一个函数的过程中，又调用另一个函数。见下图4。,函数的嵌套调用,在程序中实现函数嵌套调用时，需要注意的是：在调用函数之前，需要对每一个被调用的函数作声明(除非定义在前，调用在
46、后)。例4.9 用弦截法求方程f(x)=x3-5x2+16x-80=0的根。这是一个数值求解问题，需要先分析用弦截法求根的算法。根据数学知识，可以列出以下的解题步骤：(1)取两个不同点x1,x2,如果f（x1）和f（x2）符号相反,则(x1,x2)区间内必有一个根。如果f（x1）与f(x2)同符号,则应改变x1,x2,直到f（x1）,f(x2)异号为止。注意x1、x2的值不应差太大,以保证(x1,x2)区间内只有一个根。(2)连接(x1,f（x1)）和(x2,f（x2）)两点,此线(即弦)交x轴于x,见图4.7。,x点坐标可用下式求出：x=x1f(x2)-x2f(x1)f(x2)-f(x1)再
47、从x求出f(x)。(3)若f(x)与f（x1）同符号,则根必在(x,x2)区间内,此时将x作为新的x1。如果f(x)与f（x2）同符号,则表示根在(x1,x)区间内,将x作为新的x2。(4)重复步骤(2)和(3)，直到 f(x)为止,为一个很小的正数,例如10-6。此时认为 f(x)0。这就是弦截法的算法，在程序中分别用以下几个函数来实现以上有关部分功能：(1)用函数f(x)代表x的函数：x3-5x2+16x-80。,(2)用函数xpoint(x1,x2)来求(x1,f(x1)和(x2,f(x2)的连线与x轴的交点x的坐标。(3)用函数root(x1,x2)来求(x1,x2)区间的那个实根。显
48、然,执行root函数的过程中要用到xpoint函数,而执行xpoint函数的过程中要用到f函数。根据以上算法，可以编写出下面的程序:#include#include#include using namespace std;double f(double);/函数声明 double xpoint(double,double);/函数声明double root(double,double);/函数声明int main()double x1,x2,f1,f2,x;,do coutx1x2;f1=f(x1);f2=f(x2);while(f1*f2=0);x=root(x1,x2);coutsetio
49、sflags(iosfixed)setprecision(7);/指定输出7位小数 coutA root of equation is xendl;return 0;double f(double x)/定义f函数，以实现f(x)double y;y=x*x*x-5*x*x+16*x-80;return y;,double xpoint(double x1,double x2)/定义xpoint函数，求出弦与轴交点double y;y=(x1*f(x2)-x2*f(x1)/(f(x2)-f(x1);/在xpoint函数中调用f函数 return y;double root(double x1,
50、double x2)/定义root函数，求近似根double x,y,y1;y1=f(x1);do x=xpoint(x1,x2);/在root函数中调用xpoint函数 y=f(x);/在root函数中调用f函数 if(y*y10)y1=y;x1=x;elsex2=x;while(fabs(y)=0.00001);return x;,运行情况如下：input x1,x2：2.5 6.7A root of equation is 5.0000000对程序的说明：(1)在定义函数时，函数名为f，xpoint和root的3个函数是互相独立的，并不互相从属。这3个函数均定为双精度型。(2)3个函数的
