C函数递推递归课件.ppt

1、1HONEYWELL-CONFIDENTIALFile Number第六章第六章 函数和递推递归算法函数和递推递归算法2HONEYWELL-CONFIDENTIALFile Number第一节第一节 函数函数第二节第二节 递推算法递推算法第三节第三节 递归算法递归算法3HONEYWELL-CONFIDENTIALFile Number第一节第一节 函数函数 前面我们曾经学习了程序设计中的三种基本控制结构（顺序、分前面我们曾经学习了程序设计中的三种基本控制结构（顺序、分支、循环）。用它们可以组成任何程序。但在应用中，还经常用到子支、循环）。用它们可以组成任何程序。但在应用中，还经常用到子程序结构

2、。程序结构。通常，在程序设计中，我们会发现一些程序段在程序的不同地方通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。上其标识符即可。这样的程序段，我们称之为子程序。子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的编译时间，而且有利于结构化程

3、序设计。因为一个复杂的问题总可将编译时间，而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改，都会带来极大的好处。，都会带来极大的好处。在一个程序中可以只有主程序而没有子程序在一个程序中可以只有主程序而没有子程序(本章以前都是如此本章以前都

4、是如此)，但不能没有主程序，也就是说不能单独执行子程序。，但不能没有主程序，也就是说不能单独执行子程序。在此之前，我们曾经介绍并使用了在此之前，我们曾经介绍并使用了C+C+提供的各种标准函数，如提供的各种标准函数，如abs(),sqrt()abs(),sqrt()等等，这些系统提供的函数为我们编写程序提供了很大等等，这些系统提供的函数为我们编写程序提供了很大的方便。比如：求的方便。比如：求sin(1)+sin(2)+sin(1)+sin(2)+sin(100)+sin(100)的值。但这些函的值。但这些函数只是常用的基本函数，编程时经常需要自定义一些函数。数只是常用的基本函数，编程时经常需要自

5、定义一些函数。4HONEYWELL-CONFIDENTIALFile Number例例6.1 6.1 求：求：1!+2!+3!+101!+2!+3!+10！#include using namespace std;int main()int sum=0;for(int i=1;i=10;i+)sum+=js(i);coutsum=sumy?x:y;该函数返回值是整型，有两个整型的形参，用来接受实参传递该函数返回值是整型，有两个整型的形参，用来接受实参传递的两个数据，函数体内的语句是求两个数中的较大者并将其返回主的两个数据，函数体内的语句是求两个数中的较大者并将其返回主调函数。调函数。8HONE

6、YWELL-CONFIDENTIALFile Number3 3函数的形式函数的形式 函数的形式从结构上说可以分为三种：无参函数、有参函数和空函函数的形式从结构上说可以分为三种：无参函数、有参函数和空函数。它们的定义形式都相同。数。它们的定义形式都相同。（1 1）无参函数）无参函数无参函数顾名思义即为没有参数传递的函数，无参函数一般不需要带回无参函数顾名思义即为没有参数传递的函数，无参函数一般不需要带回函数值，所以函数类型说明为函数值，所以函数类型说明为void。（2 2）有参函数）有参函数有参函数即有参数传递的函数，一般需要带回函数值。例如有参函数即有参数传递的函数，一般需要带回函数值。例如

7、int max(int x,int y)函数。函数。（3 3）空函数）空函数空函数即函数体只有一对花括号，花括号内没有任何语句的函数。空函数即函数体只有一对花括号，花括号内没有任何语句的函数。例如，例如，函数名（）函数名（）空函数不完成什么工作，只占据一个位置。在大型程序设计中，空函数空函数不完成什么工作，只占据一个位置。在大型程序设计中，空函数用于扩充函数功能。用于扩充函数功能。9HONEYWELL-CONFIDENTIALFile Number编写一个阶乘的函数，我们给此函数取一个名字编写一个阶乘的函数，我们给此函数取一个名字jsjs。int js(int n)int s=1;for(in

8、t i=1;i=n;+i)s*=i;return s;在本例中，函数名叫在本例中，函数名叫jsjs，只有一个，只有一个intint型的自变量型的自变量n n，函数，函数jsjs属属intint型。在本函数中，要用到两个变量型。在本函数中，要用到两个变量i i，s s。在函数体中，是一个求。在函数体中，是一个求阶乘的语句，阶乘的语句，n n的阶乘的值在的阶乘的值在s s中，最后由中，最后由returnreturn语句将计算结果语句将计算结果s s值值带回，带回，js()js()函数执行结束，在主函数中函数执行结束，在主函数中js()js()值就是值就是s s的值。的值。在这里，函数的参数在这里，

9、函数的参数n n是一个接口参数，说得更明确点是入口参是一个接口参数，说得更明确点是入口参数。如果我们调用函数：数。如果我们调用函数：js(3)js(3)，那么在程序里所有有，那么在程序里所有有n n的地方，的地方，n n被被替代成替代成3 3来计算。在这里，来计算。在这里，3 3就被称为实参。又如：就被称为实参。又如：sqrt(4)sqrt(4)，ln(5)ln(5)，这里，这里4 4，5 5叫实参。而叫实参。而ln(x)ln(x)，sqrt(x)sqrt(x)中的中的x x，y y叫形参。叫形参。10HONEYWELL-CONFIDENTIALFile Number二、参数传递二、参数传递-

10、【函数函数】1.1.非引用参数非引用参数 普通的非引用类型的参数是通过复制对应的实参实现初始化。普通的非引用类型的参数是通过复制对应的实参实现初始化。当用参数副本初始化形参时，函数并没有访问调用所传递的实参本当用参数副本初始化形参时，函数并没有访问调用所传递的实参本身，因此不会修改实参的值。举个例子：身，因此不会修改实参的值。举个例子：#includeusing namespace std;void swap(int a,int b)int tmp=a;a=b;b=tmp;int main()int c=1,d=2;swap(c,d);coutc dendl;return 0;/程序输出为：程

11、序输出为：1 2 在此例中，虽然在在此例中，虽然在swapswap函数中交换了函数中交换了a,ba,b两数的值，但是在两数的值，但是在mainmain中却没有交换。因为中却没有交换。因为swapswap函数只是交换函数只是交换c,dc,d两变量副本的值。两变量副本的值。11HONEYWELL-CONFIDENTIALFile Number2.2.引用参数引用参数 引用参数直接关联到其所绑定的对象，而并非这些对象的副本。定引用参数直接关联到其所绑定的对象，而并非这些对象的副本。定义引用时，必须用与该引用绑定对象初始化该引用。引用形参完全以相义引用时，必须用与该引用绑定对象初始化该引用。引用形参完

12、全以相同的方式工作。每次调用函数，引用形参被创建并与相应实参关联。现同的方式工作。每次调用函数，引用形参被创建并与相应实参关联。现在用引用参数来实现在用引用参数来实现swapswap：#includeusing namespace std;void swap(int&a,int&b)int tmp=a;a=b;b=tmp;int main()int c=1,d=2;swap(c,d);/交换变量交换变量coutc dendl;return 0;/程序输出为：程序输出为：2 1 在此例中在此例中,因为因为swapswap函数的参数为引用参数，所以，在函数函数的参数为引用参数，所以，在函数swap

13、swap中中修改修改a,ba,b的值相当于在主函数的值相当于在主函数mainmain中修改中修改c,dc,d的值。的值。12HONEYWELL-CONFIDENTIALFile Number3.const3.const形参形参使用使用constconst修饰参数可避免在函数执行中修改参数。修饰参数可避免在函数执行中修改参数。举个例子：举个例子：void solve(const int&a)a=1;/该函数是错误的，因为该函数是错误的，因为a是是 const形参，所以在函数体中不能被修改。形参，所以在函数体中不能被修改。使用使用constconst修饰参数也可使函数接受常量作为引用参数。修饰参数

14、也可使函数接受常量作为引用参数。举个例子：举个例子：void fa(const int&a)void fb(int&a)int main()fa(2);/正确，因为正确，因为fa()使用了常量引用形参。使用了常量引用形参。fb(2);/错误，因为错误，因为fb()使用了非常量引用形参，不可以接受常量使用了非常量引用形参，不可以接受常量2。13HONEYWELL-CONFIDENTIALFile Number三、函数的声明和调用三、函数的声明和调用-【函数函数】1 1函数的声明函数的声明 调用函数之前先要声明函数原型。在主调函数中，或所有函数定义之调用函数之前先要声明函数原型。在主调函数中，或所

15、有函数定义之前，按如下形式声明：前，按如下形式声明：类型说明符类型说明符 被调函数名（含类型说明的形参表）；被调函数名（含类型说明的形参表）；如果是在所有函数定义之前声明了函数原型，那么该函数原型在本程如果是在所有函数定义之前声明了函数原型，那么该函数原型在本程序文件中任何地方都有效，也就是说在本程序文件中任何地方都可以依照序文件中任何地方都有效，也就是说在本程序文件中任何地方都可以依照该原型调用相应的函数。如果是在某个主调函数内部声明了被调用函数原该原型调用相应的函数。如果是在某个主调函数内部声明了被调用函数原型，那么该原型就只能在这个函数内部有效。型，那么该原型就只能在这个函数内部有效。函

16、数原型和函数定义在返回值类型、函数名和参数个数与类型必须完函数原型和函数定义在返回值类型、函数名和参数个数与类型必须完全一致，否则，就会发生编译错误。下面对全一致，否则，就会发生编译错误。下面对max()max()函数原型声明是合法的函数原型声明是合法的。int maxint max（int x,int yint x,int y）;也可以：也可以：int maxint max（int,int int,int）;可以看到函数原型声明与函数定义时的第一行类似，只多了一个分号可以看到函数原型声明与函数定义时的第一行类似，只多了一个分号，成为了一个声明语句而已。，成为了一个声明语句而已。14HONEY

17、WELL-CONFIDENTIALFile Numberl2 2函数的调用函数的调用声明了函数原型之后，便可以按如下形式调用函数：声明了函数原型之后，便可以按如下形式调用函数：函数名（实参列表）函数名（实参列表）实参列表中应给出与函数原型形参个数相同、类型相符的实参实参列表中应给出与函数原型形参个数相同、类型相符的实参。在主调函数中的参数称为实参，实参一般应具有确定的值。实参。在主调函数中的参数称为实参，实参一般应具有确定的值。实参可以是常量、表达式，也可以是已有确定值的变量，数组或指针名可以是常量、表达式，也可以是已有确定值的变量，数组或指针名。函数调用可以作为一条语句，这时函数可以没有返回

18、值。函数调。函数调用可以作为一条语句，这时函数可以没有返回值。函数调用也可以出现在表达式中，这时就必须有一个明确的返回值。用也可以出现在表达式中，这时就必须有一个明确的返回值。15HONEYWELL-CONFIDENTIALFile Number3 3函数的返回值函数的返回值 在组成函数体的各类语句中，值得注意的是返回语句在组成函数体的各类语句中，值得注意的是返回语句returnreturn。它的一般形式是：它的一般形式是：returnreturn（表达式）；（表达式）；其功能是把程序流程从被调函数转向主调函数并把表达式的值其功能是把程序流程从被调函数转向主调函数并把表达式的值带回主调函数，实

19、现函数的返回。所以，在圆括号表达式的值实际带回主调函数，实现函数的返回。所以，在圆括号表达式的值实际上就是该函数的返回值。其返回值的类型即为它所在函数的函数类上就是该函数的返回值。其返回值的类型即为它所在函数的函数类型。当一个函数没有返回值时，函数中可以没有型。当一个函数没有返回值时，函数中可以没有returnreturn语句（在语句（在TC+TC+和和VC+VC+，函数类型定义为，函数类型定义为voidvoid，可以没有，可以没有returnreturn语句；函数类语句；函数类型定义为型定义为intint，必须有返回值），直接利用函数体的右花括号，必须有返回值），直接利用函数体的右花括号“”

20、，作为没有返回值的函数的返回。也可以有作为没有返回值的函数的返回。也可以有returnreturn语句，但语句，但returnreturn后后没有表达式。返回语句的另一种形式是：没有表达式。返回语句的另一种形式是：returnreturn；这时函数没有返回值，而只把流程转向主调函数。这时函数没有返回值，而只把流程转向主调函数。16HONEYWELL-CONFIDENTIALFile Number四、函数的应用举例四、函数的应用举例-【函数函数】例例6.2 6.2 求求1!+2!+10!1!+2!+10!的值。的值。程序如下：程序如下：#includeusing namespace std;nt

21、 js(int);int main()int sum=0;for(int i=1;i=10;+i)sum+=js(i);coutsum=sumendl;return 0;int js(int n)int s=1;for(int i=1;i=n;+i)s*=i;return s;17HONEYWELL-CONFIDENTIALFile Number例例6.6.3 3 任意输入任意输入1010组三角形的三边，求其面积。组三角形的三边，求其面积。我们可以定义一个已知三角形三边求其面积的函数，设为我们可以定义一个已知三角形三边求其面积的函数，设为area(a,b,c)area(a,b,c)。程序如下：

22、程序如下：#include#include using namespace std;double area(double,double,double);int main()for(int i=1;i=10;+i)double a,b,c;coutinput a,b,cabc;if(a+b=c)|(a+c=b)|(b+c=a)coutdata error!endl;/判断三角形是否合法判断三角形是否合法 else couts=area(a,b,c)endl;return 0;double area(double a,double b,double c)/此函数为此函数为 海伦秦九韶海伦秦九韶公式

23、公式 double p=(a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c);在函数说明中，如果形参的个数不止在函数说明中，如果形参的个数不止一个，那么在程序中调用函数的实参个数一个，那么在程序中调用函数的实参个数一定要与形参的个数一致，第一个实参对一定要与形参的个数一致，第一个实参对应第一个形参，第二个实参对应第二个形应第一个形参，第二个实参对应第二个形参次序不能对调。参次序不能对调。18HONEYWELL-CONFIDENTIALFile Number例例6.6.4 4 定义一个函数定义一个函数check(n,d)check(n,d)，让它返回一个布尔值。如果

24、数字，让它返回一个布尔值。如果数字d d在正整数在正整数n n的某的某位中出现则送回位中出现则送回truetrue，否则送回，否则送回falsefalse。例如：例如：check(325719,3)=truecheck(325719,3)=true；check(77829,1)=falsecheck(77829,1)=false；#includeusing namespace std;bool check(int,int);int main()int a,b;coutinput n,dab;if(check(a,b)=true)couttrueendl;else coutfalseendl;r

25、eturn 0;bool check(int n,int d)while(n)/C+中中 非非0为真为真 int e=n%10;n/=10;if(e=d)return true;return false;19HONEYWELL-CONFIDENTIALFile Number例例6.5 计算如图多边形的面积。计算如图多边形的面积。从图中可以看出，五边形的面积是三个三角形面积之和。从图中可以看出，五边形的面积是三个三角形面积之和。程序如下：程序如下：#include#include /使用使用printf和和scanf语句，调用语句，调用cstdio库库#include using namespa

26、ce std;double area(double,double,double);int main()double b1,b2,b3,b4,b5,b6,b7,s;coutplease input b1,b2,b3,b4,b5,b6,b7:b1b2b3b4b5b6b7;s=area(b1,b5,b6)+area(b2,b6,b7)+area(b3,b4,b7);/调用三次函数调用三次函数area printf(s=%10.3lfn,s);return 0;double area(double a,double b,double c)double p=(a+b+c)/2;return sqrt(p

27、*(p-a)*(p-b)*(p-c);20HONEYWELL-CONFIDENTIALFile Number例例6.6.6 6 输出以下一个图形输出以下一个图形【分析】我们前面学习可用二重循环打印出上图形【分析】我们前面学习可用二重循环打印出上图形,现我们设置一个现我们设置一个函数打印出函数打印出n n个连续的个连续的*号。号。程序如下：程序如下：#includeusing namespace std;void draw_line(int);int main()for(int i=1;i=6;+i)draw_line(i);/调用函数调用函数,第第i行打印行打印i个连续星号个连续星号 retu

28、rn 0;void draw_line(int n)/该过程打印出连续该过程打印出连续n 个星号个星号,并换行并换行 for(int i=1;i=n;+i)cout*;coutendl;21HONEYWELL-CONFIDENTIALFile Number例例6.6.7 7 定义函数定义函数fafa求求n!n!。#include#includeusing namespace std;void fa(int);int t;/t定义为全程变量定义为全程变量int main()int x;cinx;fa(x);coutsetw(5)x;cout.width(8);/设置域宽，表示域宽为设置域宽，表示

29、域宽为8 couttendl;/以上两行为格式化输出，相当于以上两行为格式化输出，相当于printf(%8dn,t);return 0;void fa(int n)t=1;for(int i=2;i=n;+i)t*=i;这里通过全程变量这里通过全程变量t t，将过程中计算结果传递到，将过程中计算结果传递到t t变量中。变量中。fa(x)fa(x)仅仅仅仅作为程序中的一条命令被执行。作为程序中的一条命令被执行。22HONEYWELL-CONFIDENTIALFile Number例例6.8 6.8 用冒泡法对数组元素按由小到大排序（数组作为函数参数）用冒泡法对数组元素按由小到大排序（数组作为函数

30、参数）#includeusing namespace std;void bubble(int,int);/相当于相当于void bubble(int a,int n);int main()int array10=11,4,55,6,77,8,9,0,7,1;/大数组应开为全局变量大数组应开为全局变量 cout排序前排序前;for(int i=0;i10;+i)coutarrayi,;coutendl;bubble(array,10);return 0;void bubble(int a,int n)for(int i=1;in;+i)for(int j=0;jaj+1)/判断并交换变量判断并交换变量 int temp=aj;aj=aj+1;aj+1=temp;cout排序后排序后;for(int i=0;i10;+i)coutai,;coutendl;在前面我们已经知道数组名在前面我们已经知道数组名是该数组在内存的首地址。将数是该数组在内存的首地址。将数组名作为参数传给函数，实际上组名作为参数传给函数，实际上是把数组的地址传给函数。形参是把数组的地址传给函数。形参数组和实参数组的首地址重合，数组和实参数组的首地址重合，因此在被调用函数中对数组元素因此在被调用函数中对数组元素值进行改变，主调函数中实参数值进行改变，主调函数中实参数组的相应元素值也会改变。组的相应元素值也会改变。