C++程序设计函数ppt课件.pptx

《C++程序设计函数ppt课件.pptx》由会员分享，可在线阅读，更多相关《C++程序设计函数ppt课件.pptx（103页珍藏版）》请在三一办公上搜索。

1、程序设计与算法语言 C+程序设计,函数,本章内容,简要介绍函数调用时的内部实现机制，以及与此相关的内存分配机制、变量生命期和作用域；函数重载，递归算法、内联函数、默认参数函数以及多文件组织、编译预处理、工程文件和运行库函数。,信息科学与工程学院,第3章 函数,2,内容安排,3.1 函数的定义与调用3.2 函数的参数传递、返回值及函数声明3.3 全局变量和局部变量3.4 函数调用机制3.5 作用域与标示符的可见性3.6 存储类型与标示符的生命期3.7 函数的递归调用3.8 函数的重载、内联及默认参数,信息科学与工程学院,第3章 函数,3,3.1 函数的定义与调用,3.1.1 函数概述3.1.2

2、函数的定义3.1.3 函数的调用,信息科学与工程学院,第3章 函数,4,3.1.1 函数概述,函数是程序基本组成模块，可重复使用相对独立经常使用可把一个复杂任务分解成为若干个易于解决的小任务，充分体现逐步细化的设计思想使用时只考虑其功能和接口,信息科学与工程学院,第3章 函数,5,3.1.1 函数概述,C+程序由若干函数组成一般函数可调用其他函数，也可被其他函数调用其中存在一个函数称为主函数（入口函数）。入口函数是程序执行的入口，它可调用其他函数，但不可被调用main()WinMain(),信息科学与工程学院,第3章 函数,6,3.1.1 函数概述,函数调用层次关系,信息科学与工程学院,第3章

3、 函数,7,3.1.1 函数概述,函数按是否系统预定义可分为库函数（或标准函数）：是由编译系统预定义的。例如：一些常用的数学计算函数、字符串处理函数、图形处理函数、标准输入输出函数等库函数都按功能分类，集中说明在不同的头文件中用户只需在自己的程序中包含某个头文件，就可直接使用该文件中定义（准确说是声明）的函数用户根据需要将某个具有相对独立功能的程序定义为函数，称为自定义函数,信息科学与工程学院,第3章 函数,8,3.1.1 函数概述,函数按是否带有参数可分为无参函数：不需要输入参数的函数有参函数：有输入参数的函数,信息科学与工程学院,第3章 函数,9,3.1.2 函数的定义,函数定义：func

4、tion definition函数构成函数头：定义函数功能和接口的全部要素函数名：the name of the function函数参数：the types and number of parameters（arguments）函数返回值类型：the return type函数体：定义函数的算法实现函数必须先定义后使用,信息科学与工程学院,第3章 函数,10,3.1.2 函数的定义,无参函数基本格式数据类型函数名(void)函数体数据类型指函数返回值类型，可是任一种数据类型，默认为返回整型值（但新标准要求写明，不用默认方式）。没有返回值应将返回值类型定义为void函数名采用合法标识符表示参数

5、括号中的void通常省略，但括号不能省略函数体由一系列语句组成（函数体可为空，称为空函数）,信息科学与工程学院,第3章 函数,11,void sayHello()couthello world!;,3.1.2 函数的定义,有参函数基本格式数据类型函数名(参数类型1形式参数1,参数类型2形式参数2,)函数体 参数表中列出所有形式参数（form/formal parameters）的类型和参数名称各参数即使类型相同也必须分别加以说明形式参数简称形参，只能是变量名，不允许是常量或表达式,信息科学与工程学院,第3章 函数,12,3.1.2 函数的定义,信息科学与工程学院,第3章 函数,13,int m

6、ax(int a,int b)return(a=b?a:b);,3.1.2 函数的定义,根据参数和返回值，有4种类型函数需要参数，并返回值需要参数，不返回值不需参数，但返回值不需参数，不返回值,信息科学与工程学院,第3章 函数,14,3.1.2 函数的定义,函数头用来反映函数的功能和使用接口，它所定义的是“做什么”。即，明确了“黑匣子”的输入输出部分，输入就是参数，输出就是函数的返回值。只有那些功能上起自变量作用的变量才必须作为参数定义在参数表中函数体中具体描述“如何做”，因此除参数之外的为实现算法所需用的变量定义在函数体内C+中不允许函数的嵌套定义，即，在一个函数中定义另一个函数,信息科学与

7、工程学院,第3章 函数,15,3.1.3 函数的调用,所谓函数调用，就是使程序转去执行函数体除主函数外，其他任何函数都不能单独作为程序运行任何函数功能的实现都是通过被主函数直接或间接调用进行的,信息科学与工程学院,第3章 函数,16,3.1.3 函数的调用,无参函数的调用格式函数名()有参函数的调用格式函数名(实际参数表)实际参数（actual arguments）简称实参，用来将实际参数的值传递给形参，因此可是常量、具有值的变量或表达式,信息科学与工程学院,第3章 函数,17,Parameters are the names of the values passed to a functio

8、n by a function call.Arguments are the values the function expects to receive.,3.1.3 函数的调用,调用无返回值的函数可单独成为函数调用语句，即调用格式加分号调用有返回值的函数将产生一个数据值，因此函数调用通常出现在表达式中返回值参与表达式计算，例如：赋值在条件语句中直接参与逻辑运算,信息科学与工程学院,第3章 函数,18,3.1.3 函数的调用,信息科学与工程学院,第3章 函数,19,【例3.1】输入两个实数，输出其中较大的数。其中求两个实 数中的较大数用函数完成float max(float x,float

9、y)return(x=y?x:y);int main()float x,y;coutxy;coutx和y中较大数max(x,y)endl;return 0;,3.2 函数的参数传递、返回值及函数声明,3.2.1 函数的参数传递及传值调用3.2.2 函数返回值3.2.3 函数声明,信息科学与工程学院,第3章 函数,20,3.2.1 函数的参数传递及传值调用,函数调用首先要进行参数传递传递的方向是由实参传递给形参传递过程先计算实参表达式的值再将该值传递给对应的形参变量一般情况下，实参和形参的个数和排列顺序应一一对应，并且对应参数应类型匹配（赋值兼容）。即，实参的类型可转化为形参类型，而对应参数的参

10、数名则不要求相同,信息科学与工程学院,第3章 函数,21,3.2.1 函数的参数传递及传值调用,调用形式传值（value）：传递实参的值，需要复制引用（reference）：传递实参的别名（alias）,信息科学与工程学院,第3章 函数,22,3.2.1 函数的参数传递及传值调用,传值调用将实参的值复制给形参。当两者不匹配时，编译器将实参转化为与形参一致的类型按参数位置对应，而不是按参数名对应在函数中参加运算的是形参，而实参不会发生任何改变起了一种隔离作用,信息科学与工程学院,第3章 函数,23,信息科学与工程学院,第3章 函数,24,【例3.2】说明实参和形参对应关系的示例float pow

11、er(float x,int n)/求x的n次幂float pow=1;while(n-)pow*=x;return pow;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;,power(4.6,3)=97.336power(a,3)=912673power(3,4.6)=81,3.2.1 函数的参数传递及传值调用,传地址（address）一种特殊的传值方式虽然复制的也

12、是值，但是可直接对地址所指向的内容进行读写操作，即，无法直接隔离形参对实参的影响包括指针（pointer）和数组的名称（the name of the array）都可实现传地址的任务,信息科学与工程学院,第3章 函数,25,3.2.2 函数返回值,对于有返回值的函数，在函数的出口处必须用return语句将要返回的值返回给调用者格式：return 表达式;步骤计算表达式类型转化返回值,信息科学与工程学院,第3章 函数,26,3.2.2 函数返回值,函数一旦执行到return语句便会终止函数执行，返回调用单元对于没有返回值的函数，应将返回值类型定义为void，函数体内可没有return语句，当需

13、要在程序指定位置退出时，可在该处放置一个：return;,信息科学与工程学院,第3章 函数,27,信息科学与工程学院,第3章 函数,28,【例3.3】设计函数，根据三角形的三边长求面积。如果不能构成三角形，给出提示信息float TriangleArea(float a,float b,float c)if(a+b abc;area=TriangleArea(a,b,c);if(area=-1)cout(a,b,c)不能构成三角形！endl;elsecout三角形(a,b,c)面积为：areaendl;return 0;,3.2.3 函数声明,函数声明的引入语法上对程序文件中函数的排列次序要求

14、满足先定义后使用但从结构化程序设计的角度，通常是先调用后定义使用函数声明（function declarations），则既符合由粗到精的思维方式，又满足了语法要求,信息科学与工程学院,第3章 函数,29,3.2.3 函数声明,函数声明的格式 函数返回值类型函数名(形参表);是一条以分号结束的语句各形参之间以逗号分隔形参表可逐个列出每个参数的类型和参数名，也可只列出每个形参的类型，而参数名可省略,信息科学与工程学院,第3章 函数,30,3.2.3 函数声明,函数声明和所定义的函数必须在以下几方面完全对应一致，否则将导致编译错误返回值类型函数名形参个数形参类型形参次序,信息科学与工程学院,第3章

15、 函数,31,信息科学与工程学院,第3章 函数,32,【例3.4】输出所有满足下列条件的正整数m：10 0);for(int j=0;j i;j+)n=n*10+digitj;/反向装配return(n=m);,作业,P102：习题3.1.1。抄写P102：习题3.1.7的(2)P103：习题3.3,信息科学与工程学院,第3章 函数,33,2013年11月21日实验内容,必作部分实验六：“文本文件的简单应用”中的实验内容3和4实验七：“函数的基本概念”中的实验内容3和4教材习题3.5选作部分实验七：“函数的基本概念”中的范例2,信息科学与工程学院,第3章 函数,34,3.3 全局变量和局部变量

16、,变量由于定义位置的不同，在程序中的可见（可被使用）性也随之不同3.3.1 变量的存储机制与C+的内存布局3.3.2 全局变量3.3.3 局部变量,信息科学与工程学院,第3章 函数,35,3.3.1 变量的存储机制与C+的内存布局,程序运行时内存空间的分配,信息科学与工程学院,第3章 函数,36,存储区域说明代码区：存放程序代码，即程序中各个函数的代码块全局数据区：存放全局数据和静态数据（分配该区时内存全部清零，结果变量的所有字节自动初始化为零）栈区：存放局部变量，如函数中的变量等（分配栈区时不处理内存，即变量取随机值）自由存储区（堆）：存放与指针相关的动态数据（分配自由存储区时不处理内存）,

17、信息科学与工程学院,第3章 函数,37,3.3.1 变量的存储机制与C+的内存布局,3.3.2 全局变量,全局变量：在所有函数之外定义的变量全局变量可定义在程序开头，也可定义在任何位置该全局变量在定义处之后的任何位置都是可以访问的作为共享数据的一种常规方法,信息科学与工程学院,第3章 函数,38,3.3.2 全局变量,信息科学与工程学院,第3章 函数,39,【例3.5】多个函数使用全局变量的例子int n=100;void func()n*=2;int main()n*=2;coutnendl;func();coutnendl;return 0;,200400,3.3.3 局部变量,局部变量：

18、定义在函数内或块（例如：复合语句）内的变量存储在栈中动态分配是程序中使用最广泛的变量形式局部变量在程序运行到它所在的块时建立在栈中，该块执行完毕局部变量占有的空间即被释放,信息科学与工程学院,第3章 函数,40,3.3.3 局部变量,信息科学与工程学院,第3章 函数,41,【例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;ret

19、urn 0;,3.4 函数调用机制,调用过程建立栈空间保护现场：主调函数运行状态和返回地址入栈为被调函数中的局部变量（包括形参）在栈上分配空间，并完成参数传递执行被调函数函数体释放被调函数中局部变量占用的栈空间恢复现场：取主调函数运行状态及返回地址，释放栈空间继续主调函数后续语句,信息科学与工程学院,第3章 函数,42,3.4 函数调用机制,信息科学与工程学院,第3章 函数,43,函数调用时内存变化的例子void fun1(int,int);void fun2(float);int main()int x=1,y=2;fun1(x,y);return 0;void fun1(int a,int

20、 b)float x=3;fun2(x);void fun2(float y)int x;,3.4 函数调用机制,任何一个函数的在执行过程中只能使用该函数中定义的局部变量函数执行完毕后其变量单元即被释放不同函数中的局部变量各自独立，即使变量名相同，这是由于它们各自占用不同的内存单元,信息科学与工程学院,第3章 函数,44,3.5 作用域与标示符的可见性,作用域：指标识符能够被使用的范围只在作用域内标识符才可被访问（称为可见）任何标识符作用域的起始点为标识符说明处局部域块域函数声明域文件域（全局域）,信息科学与工程学院,第3章 函数,45,3.5 作用域与标示符的可见性,块域块指一对大括号（）括

21、起来的程序段块中定义的标识符，作用域在块内复合语句中定义的标识符，作用域仅在该复合语句中由于函数也是一个块，因此函数中定义的标识符，包括形参和函数体中定义的局部变量，作用域都在该函数内，也称作函数域,信息科学与工程学院,第3章 函数,46,信息科学与工程学院,第3章 函数,47,【例3.7】输入两数，将两数按从大到小的顺序保存，并输出结果int main()int a,b;/函数内定义局部变量，具有函数域coutab;cout=a)/使a中保存大数，b中保存小数int t;/块中定义局部变量，具有块作用域t=a;a=b;b=t;/交换a和b的值couta=atb=bendl;return 0;

22、,couttendl;,3.5 作用域与标示符的可见性,块域局部变量具有局部作用域程序在不同块中可以使用同名变量。这些同名变量各自在自己的作用域中可见，在其他地方不可见,信息科学与工程学院,第3章 函数,48,信息科学与工程学院,第3章 函数,49,【例3.8】设计函数完成两数交换，并用主函数进行测试，看是否成功void swap(int,int);int main()int a,b;/main()中定义的a和b，作用域为main()coutab;cout调用前：实参a=a,b=bendl;swap(a,b);cout调用后：实参a=a,b=bendl;/发现交换失败return 0;void

23、 swap(int a,int b)/swap()中定义的a和b，作用域为swap()cout调用中endl;cout交换前：形参a=a,b=bendl;int t;t=a;a=b;b=t;/交换a和b的值cout交换后：形参a=a,b=bendl;,信息科学与工程学院,第3章 函数,50,【例3.8】设计函数完成两数交换，并用主函数进行测试，看是否成功,执行main(),调用swap(),执行swap(),返回main(),3.5 作用域与标示符的可见性,块域对于嵌套块中有同名局部变量，服从局部优先原则如果块内定义的局部变量与全局变量同名，块内仍然局部变量优先。但与块作用域不同的是，在块内可

24、以通过域运算符“:”访问同名的全局变量,信息科学与工程学院,第3章 函数,51,信息科学与工程学院,第3章 函数,52,【例3.9】显示同名变量可见性的例子int n=100;int main()int i=200,j=300;/输出全局变量n和外层局部变量i和jcout ntitjendl;int i=500,j=600,n;/内层块 n=i+j;/输出内层局部变量n、i和j cout ntitj endl;/输出全局变量n cout:nendl;n=i+j;/修改全局变量/输出全局变量n和外层局部变量i和jcout ntitj endl;return 0;,3.5 作用域与标示符的可见性,

25、函数声明域函数声明不是定义函数，在函数声明时，其中的形参作用域只在声明中，即作用域结束于右括号正是由于形参不能被程序的其他地方引用，所以通常只要声明形参个数和类型，形参名可省略,信息科学与工程学院,第3章 函数,53,3.5 作用域与标示符的可见性,文件作用域（也称全局作用域）定义在所有函数之外的标识符，具有文件作用域，作用域为从定义处到整个源文件结束文件中定义的全局变量和函数都具有文件作用域如果某个文件中说明了具有文件作用域的标识符，该文件又被另一个文件包含，则该标识符的作用域延伸到新的文件中,信息科学与工程学院,第3章 函数,54,3.6 存储类型与标示符的生命期,存储类型决定标识符的存储

26、区域编译系统在不同区域为不同存储类型的标识符分配空间生命期指的是标识符从获得空间到空间释放之间的时间由于存储区域不同，标识符的生命期也不同标识符被访问条件在其生命期在其作用域,信息科学与工程学院,第3章 函数,55,3.6.1 存储类型,C+中关于存储类型的说明符有四个autoregisterstaticextern用auto和register修饰的称为自动存储类型用static修饰的称为静态存储类型用extern修饰的称为外部存储类型,信息科学与工程学院,第3章 函数,56,3.6.1 存储类型,自动存储类型自动变量为用auto说明的变量（通常auto省略）局部变量都是自动变量，生命期开始于

27、块的执行，结束于块的结束自动变量的空间分配在栈中，块开始执行时系统自动分配空间，块执行结束时系统自动释放空间自动变量的生命期和作用域是一致的为提高程序运行效率，可将某些变量保存在寄存器中，即，用register说明为寄存器变量（但不提倡使用）register int i;,信息科学与工程学院,第3章 函数,57,3.6.1 存储类型,静态存储类型static说明的变量称为静态变量。根据定义的位置不同，还分为局部静态变量，也称内部静态变量全局静态变量，也称外部静态变量静态变量均存储在全局数据区，如果程序未显式给出初始化值，系统自动初始化为全零，且初始化只进行一次静态变量占有的空间要到整个程序执行

28、结束才释放，故静态变量具有全局生命期,信息科学与工程学院,第3章 函数,58,3.6.1 存储类型,静态存储类型局部静态变量是定义在块中的静态变量，当块第一次被执行时，编译系统在全局数据区为其开辟空间并保存数据，该空间一直到整个程序结束才释放具有局部作用域但却具有全局生命期全局静态变量具有全局作用域和生命期,信息科学与工程学院,第3章 函数,59,信息科学与工程学院,第3章 函数,60,【例3.10】自动变量与局部静态变量的区别int st();int at();int main()int i;for(i=0;i 5;i+)coutat()t;coutendl;for(i=0;i 5;i+)c

29、outst()t;coutendl;return 0;,101 101 101 101101 102 103 104 105,int st()/局部静态变量static int t=100;t+;return t;int at()/自动变量int t=100;t+;return t;,3.6.1 存储类型,外部存储类型一个C+程序可以由多个源程序文件组成。多文件程序系统可以通过外部存储类型的变量和函数来共享某些数据和操作在一个程序文件中定义的全局变量和函数缺省为外部的，即，其作用域可以延伸到程序的其他文件中。其他文件如果要使用这个文件中定义的全局变量和函数，应该在使用前用“extern”作外部

30、声明。外部声明通常放在文件的开头（函数总是省略extern）,信息科学与工程学院,第3章 函数,61,3.6.1 存储类型,外部存储类型外部变量声明不同于全局变量定义，但两者在类型和名称上必须保持一致变量定义时编译器为其分配存储空间变量声明则表示该全局变量已在其他地方定义过，编译系统不再分配存储空间,信息科学与工程学院,第3章 函数,62,3.6.1 存储类型,外部存储类型静态的全局变量（即，全局静态变量）其作用域限制在本文件中，因此如果某些全局变量不希望被外部文件使用，可将其说明为静态的同理，静态的函数其作用域限制在本文件中，外部文件即使进行了外部声明也无法使用它,信息科学与工程学院,第3章

31、 函数,63,信息科学与工程学院,第3章 函数,64,【例3.11】外部存储类型的例子。假定程序包含两个源程序文件/*Ex3_11_1.cpp，由main()组成*/void fun2();/外部函数声明，等价于extern void fun2();int n;/全局变量定义int main()n=1;fun2();/fun2()定义在文件Ex3_11_2.cpp中coutn=nendl;return 0;,/*Ex3_11_2.cpp，由fun2()组成*/extern int n;/外部变量声明，n定义在文件Ex3_11_1.cpp中void fun2()/fun2()被文件Ex3_11_

32、1.cpp中的函数调用n=3;,3.6.2 生命期,静态全局数据区局部栈区动态自由存储区,信息科学与工程学院,第3章 函数,65,3.8 函数重载、内联及默认参数,3.8.1 函数重载3.8.2 默认参数3.8.3 内联函数,信息科学与工程学院,第3章 函数,66,3.8.1 函数重载,在C+中，如果需要定义几个功能相似，而参数类型不同的函数，那么这样的几个函数可以使用相同的函数名，这就是函数重载（overloading）在定义重载函数时必须保证参数类型不同，仅仅返回值类型不同是不行的函数重载的好处在于，可以用相同的函数名来定义一组功能相同或类似的函数，增强程序的可读性,信息科学与工程学院,第

33、3章 函数,67,3.8.1 函数重载,当某个函数中调用到重载函数时，编译器会根据实参的类型去对应地调用相应的函数。匹配过程按如下步骤进行如果有严格匹配的函数，就调用该函数参数内部转换后如果匹配，调用该函数通过用户定义的转换寻求匹配,信息科学与工程学院,第3章 函数,68,信息科学与工程学院,第3章 函数,69,【例3.16】重载函数的应用int sum(int a,int b)return a+b;double sum(double a,double b)return a+b;float sum(float a,float b,float c)return a+b+c;int main()/

34、调用sum(int,int)cout3+5=sum(3,5)endl;/调用double(double,double)cout2.2+5.6=sum(2.2,5.6)endl;/调用float sum(float,float,float)cout3.5+4+8=sum(3.5,4,8)endl;return 0;,3.8.2 默认（缺省）参数,缺省参数指在定义函数时为形参指定缺省值（默认值）这样的函数在调用时，对于缺省参数，可给出实参值（即，用实参赋值给形参），也可不给出参数值如果给出实参，将实参传递给形参进行调用，如果不给出实参，则按缺省值进行调用缺省参数并不一定是常量表达式，可以是任意表达

35、式，甚至可以通过函数调用给出int fun1(int a=rand();/函数声明,信息科学与工程学院,第3章 函数,70,3.8.2默认（缺省）参数,使用要点缺省参数可以有多个，但所有缺省参数必须放在参数表的右侧，即，先定义所有的非缺省参数，再定义缺省参数。这是因为在函数调用时，参数自左向右逐个匹配，当实参和形参个数不一致时只有这样才不会产生二义性,信息科学与工程学院,第3章 函数,71,3.8.2默认（缺省）参数,使用要点在同一个作用域中一个参数只能被指定一次缺省值，即，只能在函数声明或定义其中一处指定缺省值不可在声明和定义中同时指定缺省值，即使缺省值一样也不行习惯上，缺省参数在公共头文件

36、包含的函数声明中指定，否则缺省实参只能被包含该函数定义的文件中的函数调用,信息科学与工程学院,第3章 函数,72,3.8.3 内联函数,内联函数的引入当程序执行函数调用时，系统要建立栈空间，保护现场，传递参数以及控制程序执行的转移等等，这些工作需要系统时间和空间的开销,信息科学与工程学院,第3章 函数,73,3.8.3 内联函数,内联函数的引入当函数功能简单，使用频率很高，为了提高效率，可直接将函数的代码嵌入到程序中。但这个办法有缺点相同代码重复书写程序可读性往往没有使用函数的好为了协调好效率和可读性之间的矛盾，C+提供了另一种方法，即定义内联函数，方法是在定义函数时用修饰词inline,信息

37、科学与工程学院,第3章 函数,74,3.8.3 内联函数,关键字inline可同时用在函数声明和定义处，也可只用于一处，但必须在函数调用前给出（编译过程需要）inline int isNumber(char ch);/函数声明当函数体中包含复杂结构控制语句，即使定义其为“inline”，编译器不会将该函数作为内函数在多文件结构中，每个文件都必须重新定义该内联函数,信息科学与工程学院,第3章 函数,75,作业,P102：习题3.1.2、3.1.3、3.1.4和3.1.5。抄写P102：习题3.1.6和3.1.7的(1)P103：习题3.2.1和3.2.3P103：习题3.4阅读3.9节和3.10

38、节,信息科学与工程学院,第3章 函数,76,2013年11月21日实验内容,必作部分教材习题3.6、3.7和3.8教材习题3.11和3.13选作部分实验九：“函数的重载和变量的作用域”中的实验内容2和5教材习题3.14,信息科学与工程学院,第3章 函数,77,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,78,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,79,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,80,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,

39、第3章 函数,81,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,82,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,83,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,84,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,85,3.7 函数的递归调用,递归是一种描述问题的方法，或称算法。递归的思想可以简单地描述为“自己定义自己”（或自己调用自己），包括基本部分递归部分例如：用如下方法定义阶乘（factorial）基本部分：1!=1；0!=1递归

40、部分：n!=n(n-1)!,n=1,信息科学与工程学院,第3章 函数,86,3.7 函数的递归调用,信息科学与工程学院,第3章 函数,87,int fac(int n)coutn;int y;if(n=0|n=1)y=1;else y=n*fac(n-1);couty;return y;,coutfac(4);,cout4;y=4*fac(3);cout24;return 24;,cout3;y=3*fac(2);cout6;return 6;,cout2;y=2*fac(1);cout2;return 2;,cout1;y=1;cout1;return 1;,cout2;return 2;,

41、cout6;return 6;,cout24;return 24;,3.7 函数的递归调用,信息科学与工程学院,第3章 函数,88,coutfac(n);,coutn;y=n*fac(n-1);coutn!;return n!;,coutn-1;y=(n-1)*fac(n-2);cout(n-1)!;return(n-1)!;,cout2;y=2*fac(1);cout2;return 2;,cout1;y=1;cout1;return 1;,cout2;return 2;,cout(n-1)!;return(n-1)!;,coutn!;return n!;,3.7 函数的递归调用,递归函数必

42、须定义递归终止条件，即，到达基本部分，以避免无穷递归递归（反向）递推+终止+（正向）回归,信息科学与工程学院,第3章 函数,89,int fac(int n)coutn;int y;if(n=0|n=1)y=1;else y=n*fac(n-1);couty;return y;,3.7 函数的递归调用,递归调用分类直接递归：在函数A的定义中有调用函数A的语句，即，自己调用自己间接递归：函数A的定义中出现调用函数B的语句，而函数B的定义中也出现调用函数A的语句，即，相互调用,信息科学与工程学院,第3章 函数,90,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数

43、,91,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,92,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,93,3.7 函数的递归调用,汉诺（hanoi）塔问题,信息科学与工程学院,第3章 函数,94,信息科学与工程学院,第3章 函数,95,void move(char,char);void hanoi(int,char,char,char);int main()int n;coutn;hanoi(n,A,B,C);return 0;void hanoi(int n,char source,char temp,char

44、 target)if(n=1)move(source,target);else hanoi(n-1,source,target,temp);/将n-1个盘子搬到中间柱move(source,target);/将最后一个盘子搬到目标柱hanoi(n-1,temp,source,target);/将n-1个盘子搬到目标柱void move(char source,char target)static double count=0;count+;couttargetn;,static double count=0;count+;double sn=count;couttargetendl;,cout

45、exit No.snendl;,hanoi(n,L,M,R);,输入盘子数：2No.1 entering:2 A-B-CNo.2 entering:1 A-C-BNo.1 moving:A-Bexit No.2No.2 moving:A-CNo.3 entering:1 B-A-CNo.3 moving:B-Cexit No.3exit No.1,输入盘子数：3No.1 entering:3 A-B-CNo.2 entering:2 A-C-BNo.3 entering:1 A-B-CNo.1 moving:A-Cexit No.3No.2 moving:A-BNo.4 entering:1

46、C-A-BNo.3 moving:C-Bexit No.4exit No.2No.4 moving:A-CNo.5 entering:2 B-A-CNo.6 entering:1 B-C-ANo.5 moving:B-Aexit No.6No.6 moving:B-CNo.7 entering:1 A-B-CNo.7 moving:A-Cexit No.7exit No.5exit No.1,信息科学与工程学院,第3章 函数,96,void hanoi(int n,char source,char temp,char target)static double count=0;count+;do

47、uble sn=count;cout;cout;couttargetendl;if(n=1)move(source,target);else hanoi(n-1,source,target,temp);move(source,target);hanoi(n-1,temp,source,target);coutexit No.sn;coutendl;,输入盘子数：3No.1 entering:3 A-B-CNo.2 entering:2 A-C-BNo.3 entering:1 A-B-CNo.1 moving:A-Cexit No.3No.2 moving:A-BNo.4 entering:1

48、 C-A-BNo.3 moving:C-Bexit No.4exit No.4No.4 moving:A-CNo.5 entering:2 B-A-CNo.6 entering:1 B-C-ANo.5 moving:B-Aexit No.6No.6 moving:B-CNo.7 entering:1 A-B-CNo.7 moving:A-Cexit No.7exit No.7exit No.7,输入盘子数：3No.1 entering:3 A-B-CNo.2 entering:2 A-C-BNo.3 entering:1 A-B-CNo.1 moving:A-Cexit No.3No.2 mo

49、ving:A-BNo.4 entering:1 C-A-BNo.3 moving:C-Bexit No.4exit No.2No.4 moving:A-CNo.5 entering:2 B-A-CNo.6 entering:1 B-C-ANo.5 moving:B-Aexit No.6No.6 moving:B-CNo.7 entering:1 A-B-CNo.7 moving:A-Cexit No.7exit No.5exit No.1,3.7 函数的递归调用,递归调用同普通的函数调用一样，每当调用发生时在栈中分配单元保存返回地址以及参数和局部变量而与普通的函数调用不同的是由于递推的过程是一

50、个逐层调用的过程，因此存在一个逐层连续的参数入栈过程，直至遇到递归终止条件时，才开始回归，这时才逐层释放栈空间，返回到上一层，直至最后返回到主调函数,信息科学与工程学院,第3章 函数,97,3.7 函数的递归调用,信息科学与工程学院,第3章 函数,98,void hanoi(int n,char source,char temp,char target)if(n=1)move(source,target);else hanoi(n-1,source,target,temp);/将n-1个盘子搬到中间柱move(source,target);/将最后一个盘子搬到目标柱hanoi(n-1,temp