第3章 过程抽象——函数.ppt

SEI第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季2学习目标学习目标n掌握函数调用的方法，会使用函数原型；掌握函数调用的方法，会使用函数原型；n掌握函数定义的方法，理解函数返回值的意义；掌握函数定义的方法，理解函数返回值的意义；n熟练掌握函数调用的值传递规则。熟练掌握函数调用的值传递规则。n掌握递归函数掌握递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季3n 3.1 函数函数n3.1.1 函数概述函数概述n3.1.2 函数定义函数定义n3.1.3 函数调用函数调用n3.1.4 函数传递机制函数传递机制n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季4C函数的概念函数的概念n函数是函数是C提供的用于实现子模块的语言成分。提供的用于实现子模块的语言成分。n函数的概念源于数学，是一个集合到另一个集合函数的概念源于数学，是一个集合到另一个集合的映射。例如对于数学中的函数的映射。例如对于数学中的函数y=f(x)=x2:0140 1-12xyx2用用C函数表示就是：函数表示就是：int f(int x)return x*x;函数函数函数函数函数函数函数概述函数概述高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季5n在前面学习的在前面学习的C C程序中，都有一个名称为程序中，都有一个名称为mainmain的函的函数，每个完整的数，每个完整的C C程序从该函数开始运行。程序从该函数开始运行。n在前面编写的程序中，很多处理在前面编写的程序中，很多处理(运算运算)都是通过使都是通过使用库函数完成的。用库函数完成的。如数学函数如数学函数:fabsfabs()()、sqrtsqrt()()、powpow()()、sin().sin().C函数概述函数概述函数概述函数概述高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季6函数的基本要素函数的基本要素n一个函数由函数首部和函数体两部分构成一个函数由函数首部和函数体两部分构成函数首部包括函数首部包括：函数名、函数的返回值类型、函数的参数：函数名、函数的返回值类型、函数的参数函数体包括函数体包括：声明部分：声明部分(数据说明数据说明)、语句部分、语句部分(运算运算)intint main(void)main(void)intint inches,feet,fathoms;inches,feet,fathoms;printf(printf(inputinput fathoms:);fathoms:);scanfscanf (%d,&fathoms)(%d,&fathoms);feet=6*fathoms;feet=6*fathoms;inches=12*feet;inches=12*feet;return 0;return 0;声明部分：声明部分：三个整形变量三个整形变量语句部分：语句部分：输入一个英寻数，输入一个英寻数，进行单位换算进行单位换算函函数数体体函数首部函数首部函数概述函数概述高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季7函数定义和函数调用的概念函数定义和函数调用的概念n编写编写函数首部和函数体的内容就是进行函数首部和函数体的内容就是进行函数定义函数定义n按照函数定义时给定的函数名按照函数定义时给定的函数名使用使用函数称为函数称为函数调函数调用用n库函数库函数是已经编写好的函数，编写程序时可直接调是已经编写好的函数，编写程序时可直接调用用n在本章我们要学习自己编写函数，并了解更多的库在本章我们要学习自己编写函数，并了解更多的库函数的使用方法函数的使用方法函数概述函数概述高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季8n 3.1 函数函数n3.1.1 函数概述函数概述n3.1.2 函数定义函数定义n3.1.3 函数调用函数调用n3.1.4 函数传递机制函数传递机制n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季9函数定义函数定义n函数定义的一般形式是：返回值类型返回值类型 函数名函数名(形式参数表形式参数表)声明部分；声明部分；语句部分；语句部分；n例如，定义一个函数，将给定一个摄氏温度转换为例如，定义一个函数，将给定一个摄氏温度转换为华氏温度，并将华氏温度返回。华氏温度，并将华氏温度返回。void main(void)int x;double y;printf(Celsius to Fahrenheit table:n);for(x=0;x=100;x+=5)y=CelsToFahr(x);printf(%d%lfn,x,y);double CelsToFahr(int c)double t;t=9.0/5*c+32;return t;函数定义函数定义高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季10函数参数函数参数n形式参数和实际参数返回值类型返回值类型 函数名函数名(形式参数表形式参数表)声明部分；声明部分；语句部分；语句部分；double CelsToFahr(int c)double t;t=9.0/5*c+32;return t;调用函数时的参数是实际参数调用函数时的参数是实际参数x=35;x=35;y=CelsToFahr(x);y=CelsToFahr(50);函数定义中函数首部的参数称为形式参数函数定义中函数首部的参数称为形式参数形参形参说明的格式为：说明的格式为：函数定义函数定义高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季11函数的返回值和函数的返回值和returnreturn语句语句n函数的返回值由return语句带回，return语句使被调用函数的执行过程终止n定义一个函数，判断给定义一个函数，判断给定的一个十进制正整数定的一个十进制正整数是否为素数。是否为素数。/*判断正整数判断正整数d是否为素数，若是返回是否为素数，若是返回1，否则返回，否则返回0*/int isPrime(int d)int i;if(d 2)return 0;for(i=2;i y)z=x;else z=y;return(z);void main()int a,b,c;scanf(“%d%d”,&a,&b);c=max(a,b);printf(“最大值为：最大值为：%d”,c);函数定义函数定义高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季13函数定义小结函数定义小结n函数定义的一般形式：返回值类型返回值类型 函数名函数名(形式参数表形式参数表)声明部分；声明部分；语句部分；语句部分；n函数没有形式参数表时，可用函数没有形式参数表时，可用“void”void”表示，函数调用时无表示，函数调用时无须指定实际参数。须指定实际参数。n函数没有返回值时，返回值类型用函数没有返回值时，返回值类型用“void”void”表示，此时函数表示，此时函数中可不写中可不写returnreturn语句。语句。n函数的返回值由函数的返回值由returnreturn语句带回，在函数体中，语句带回，在函数体中，returnreturn语句语句可出现多次，但执行到某一条可出现多次，但执行到某一条returnreturn语句时，函数即结束。语句时，函数即结束。函数定义函数定义高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季14n 3.1 函数函数n3.1.1 函数概述函数概述n3.1.2 函数定义函数定义n3.1.3 函数调用函数调用n3.1.4 函数传递机制函数传递机制n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季15函数调用函数调用n函数调用的基本格式：函数调用的基本格式：函数名函数名(实际参数表实际参数表)n主调函数和被调用函数主调函数和被调用函数调用函数时，表达式调用函数时，表达式(语句语句)所在的函数称为主调函数所在的函数称为主调函数实际参数实际参数(实参实参)在主调函数中在主调函数中形式参数形式参数(形参形参)在被调用函数中在被调用函数中n实参实参由零个、一个或多个表达式表达式构成（逗号分割），其个数和类型应与相应函数的形参相同。个数和类型应与相应函数的形参相同。函数调用函数调用高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季16函数调用的执行过程函数调用的执行过程n当一个函数被调用时，执行以下步骤：当一个函数被调用时，执行以下步骤：1)1)计算每个实际参数的值；计算每个实际参数的值；2)2)将每个实参的值拷贝至对应的形参变量将每个实参的值拷贝至对应的形参变量3)3)执行被调用函数的语句，直到遇到一条执行被调用函数的语句，直到遇到一条returnreturn语语句或语句结束；句或语句结束；4)4)计算计算returnreturn语句中表达式的值语句中表达式的值5)5)返回主调函数，用返回的值替换函数调用，然后返回主调函数，用返回的值替换函数调用，然后继续执行主调函数的后续语句继续执行主调函数的后续语句函数调用函数调用高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季17函数调用的执行过程函数调用的执行过程n例：求两数之和例：求两数之和#includefloat add(float x,float y)float z;z=x+y;return(z);void main()float a,b,c;scanf(“%f%f”,&a,&b);c=add(a,b);printf(“sum is%fn”,c);程序的入口，执行程序的入口，执行main()调用调用add()函数，计算实参的函数，计算实参的值值a和和b将实参将实参a、b的值传给形参的值传给形参x、y执行函数体执行函数体调用点调用点执行完执行完return语句将结果返回到调语句将结果返回到调用点用点函数调用函数调用高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季18n程序要对被调用的函数进行声明。程序要对被调用的函数进行声明。n如果函数定义在本源文件调用点之前，则无需声明；如果函数定义在本源文件调用点之前，则无需声明；n如如果果函函数数定定义义在在本本源源文文件件调调用用点点之之后后，或或者者在在其其它它文文件件中定义，则在调用前需要对被调用的函数进行声明。中定义，则在调用前需要对被调用的函数进行声明。n函数声明的格式如下：函数声明的格式如下：n返回值类型 函数名();/函数原型n在函数声明中，在函数声明中，中可以只列出形参中可以只列出形参的类型而不写形参名。的类型而不写形参名。n函数原型即可以出现在函数原型即可以出现在main函数之前，也可以像函数之前，也可以像标准库一样将它们单独列在头文件中，并在源文件标准库一样将它们单独列在头文件中，并在源文件中包含该头文件。中包含该头文件。函数声明（函数原型）函数声明（函数原型）函数调用函数调用高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季19例：求两数之和例：求两数之和#includefloat add(float,float);/函数原型函数原型void main()float a,b,c;scanf(“%f%f”,&a,&b);c=add(a,b);printf(“sum is%fn”,c);float add(float x,float y)float z;z=x+y;return(z);函数调用函数调用高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季20举例举例n定义一个求定义一个求n n的阶乘的函数。函数返回的阶乘的函数。函数返回n n！void main()int i=1;for(i=1;i=10;i+)printf(“%d!=%dn”,i,fact(i);long fact(int n)long t=1,i=1;for(i=1;i=n;i+)t=t *i;return(t);n不同函数中的变量是互不干扰、相互独立的不同函数中的变量是互不干扰、相互独立的高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季21举例举例l书架上有书架上有n n本不同的书，从中本不同的书，从中任取任取k k本，有多少种取法？本，有多少种取法？long combinations(int n,int k)return(fact(n)/(fact(k)*fact(n-k);高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季22举例举例n定义一个函数，对于给定一个位数不超过定义一个函数，对于给定一个位数不超过5 5位的十进制位的十进制整数整数n n，求解并返回其从右边数第，求解并返回其从右边数第k k位上的数字位上的数字(0k5)(0k5)，若，若k k大于大于n n的位数，则返回的位数，则返回0 0。高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季23 被除数 除数 商 余数123451012345第第1位位高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季24 被除数 除数 商 余数1234123451012345101234第第2位位高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季25 被除数 除数 商 余数123412345101234510123412310123第第3位位高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季26 被除数 除数 商 余数123412345101234510123412310123121012第第4位位高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季27 被除数 除数 商 余数12341234510123451012341231012312101211001第第5位位高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季28 被除数 除数 商 余数123412345101234510123412310123121012110010高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季29举例举例n定义一个函数，对于给定一定义一个函数，对于给定一个位数不超过个位数不超过5 5位的十进制位的十进制整数整数n n，求解并返回其从右，求解并返回其从右边数第边数第k k位上的数字位上的数字(0k5)(0k 0&i k)t=d%10;d=d/10;i=i+1;if(i=k)return(t);return 0;高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季30n编制一个函数编制一个函数ucos，利用下式计算给定实数，利用下式计算给定实数x的近似余弦函的近似余弦函数值，直到最后一项的绝对值小于数值，直到最后一项的绝对值小于10-6.举例举例高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季31#include#include double ucos(double x)double ucos=0,ai=1;int i=0,sign=1;int k,fib;while(ai=1e-6)ucos+=sign*ai;i+;fib=1;for(k=1;k=2*i;k+)fib*=k;ai=pow(x,2*i)/fib;sign=-sign;return ucos;int main()double x;printf(请输入请输入x：n);scanf(%lf,&x);printf(ucos(%lf)=%lfn,x,ucos(x);return 0;高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季32n 3.1 函数函数n3.1.1 函数概述函数概述n3.1.2 函数定义函数定义n3.1.3 函数调用函数调用n3.1.4 函数传递机制函数传递机制n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季33形式参数和实际参数形式参数和实际参数n函数未被调用时，形式参数不占用存储空间函数未被调用时，形式参数不占用存储空间n参数较多时，实际参数值逐一赋给形参，它们必须参数较多时，实际参数值逐一赋给形参，它们必须保持数目、类型、顺序的一致保持数目、类型、顺序的一致n实参向形参传递值，形参不能向实参传递值实参向形参传递值，形参不能向实参传递值n实参可以是常量、变量或表达式实参可以是常量、变量或表达式函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季34nC函数的参数传递机制只有一种，即值传递。函数的参数传递机制只有一种，即值传递。n值传递值传递n是指在函数调用时，采用类似赋值操作的形式把实参值是指在函数调用时，采用类似赋值操作的形式把实参值复制给形参。复制给形参。n这种复制操作是单向的，不可逆的。这种复制操作是单向的，不可逆的。n形参变化，实参不变。形参变化，实参不变。函数的参数传递函数的参数传递函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季35n编写程序将用户输入的两个整数相加，要求尽可能使用函数将程编写程序将用户输入的两个整数相加，要求尽可能使用函数将程序中的操作独立出来序中的操作独立出来#include#include zylib.hvoid PrintWelcomeInfo();/在屏幕上输出欢迎信息在屏幕上输出欢迎信息int GetInteger(STRING prompt);/从键盘获取用户输入的整数从键盘获取用户输入的整数int Add(int x,int y);/将两个整数相加将两个整数相加int main()int a,b,sum;PrintWelcomeInfo();a=GetInteger(The first number:);b=GetInteger(The second number:);sum=Add(a,b);printf(The sum is%d.n,sum);return 0;函数调用示例函数调用示例函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季36void PrintWelcomeInfo()printf(The program gets two integers,and prints their sum.n);int GetInteger(STRING prompt)int t;printf(%s,prompt);t=GetIntegerFromKeyboard();return t;int Add(int x,int y)int t;t=x+y;return t;函数调用示例函数调用示例函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季37absummain调用函数前调用函数前函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季38mainPrintWelcomeInfo调用调用 PrintWelcomeInfo 函数函数函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季39mainThe first number:prompttGetInteger首次调用首次调用 GetInteger 函数，数据输入前函数，数据输入前函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季40mainThe first number:10prompttGetInteger首次调用首次调用 GetInteger 函数，数据输入后函数，数据输入后函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季4110absummain首次调用首次调用 GetInteger 函数结束函数结束函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季42mainThe second number:20prompttGetInteger再次调用再次调用 GetInteger 函数，数据输入后函数，数据输入后函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季431020absummain再次调用再次调用 GetInteger 函数结束函数结束函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季44调用调用 Add 函数函数main1030 xtAdd20y函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季45102030absummain调用调用 Add 函数结束，结果为函数结束，结果为 30函数调用栈框架函数调用栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季46l编写程序将用户输入的两个整数互换编写程序将用户输入的两个整数互换#include void Swap(int x,int y);int main()int a,b;/*/*输入部分输入部分*/PrintWelcomeInfo();scanf(%d,&a);scanf(%d ,&b);/*/*数据处理与输出部分数据处理与输出部分*/printf(In main():a:%d;b:%dn,a,b);Swap(a,b);printf(In main():a:%d;b:%dn,a,b);return 0;整数互换示例整数互换示例函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季47void Swap(int x,int y)int t;printf(In Swap():x:%d;y:%dn,x,y);t=x;x=y;y=t;printf(In Swap():x:%d;y:%dn,x,y);return;整数互换示例整数互换示例函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季481020abmain调用调用 Swap 函数前函数前整数互换程序栈框架整数互换程序栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季49调用调用 Swap 函数，数据互换前函数，数据互换前main10 xtSwap20y整数互换程序栈框架整数互换程序栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季50调用调用 Swap 函数，数据互换后函数，数据互换后main2010 xtSwap10y整数互换程序栈框架整数互换程序栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季511020abmain调用调用 Swap 函数后函数后整数互换程序栈框架整数互换程序栈框架函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季52l编写程序将用户输入的两个整数互换编写程序将用户输入的两个整数互换#include int a,b;/*/*全局数据对象声明，以保证所有函数都可以访问这两个数据对象全局数据对象声明，以保证所有函数都可以访问这两个数据对象*/void Swap();/*/*不再需要函数参数不再需要函数参数 */int main()/*/*输入部分输入部分*/PrintWelcomeInfo();scanf(%d,&a);scanf(%d ,&b);/*/*数据处理与输出部分数据处理与输出部分*/printf(In main():a:%d;b:%dn,a,b);Swap();printf(In main():a:%d;b:%dn,a,b);return 0;整数互换示例第二版整数互换示例第二版函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季53void Swap()int t;printf(In Swap():a:%d;b:%dn,a,b);t=a;a=b;b=t;printf(In Swap():a:%d;b:%dn,a,b);return;整数互换示例第二版整数互换示例第二版函数传递机制函数传递机制高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季54n 3.1 函数函数n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季55n函数平行定义，不能嵌套定义，但可以嵌套调用函数平行定义，不能嵌套定义，但可以嵌套调用函数嵌套调用函数嵌套调用递归函数递归函数n如果一个函数在其函数体中直接或间接地调用了自己，如果一个函数在其函数体中直接或间接地调用了自己，则该函数称为递归函数。则该函数称为递归函数。高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季56n直接递归直接递归void f().f().n间接递归间接递归extern void g();void f().g().void g().f().递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季57n在程序设计中经常需要实现重复性的操作。循环在程序设计中经常需要实现重复性的操作。循环为实现重复操作提供了一种途径。为实现重复操作提供了一种途径。n实现重复操作的另一个途径是采用递归函数。实现重复操作的另一个途径是采用递归函数。递归函数的作用递归函数的作用递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季58递归函数的作用递归函数的作用n“分而治之分而治之”（Divide and Conquer）设计方法）设计方法:n把一个问题分解成若干个子问题，而每个子问题的性质把一个问题分解成若干个子问题，而每个子问题的性质与原问题相同，只是在规模上比原问题要小。每个子问与原问题相同，只是在规模上比原问题要小。每个子问题的求解过程可以采用与原问题相同的方式来进行。题的求解过程可以采用与原问题相同的方式来进行。例：求第例：求第n个个fibonacci数数fib(n)=1 (n=1)1 (n=2)fib(n-2)+fib(n-1)(n3)递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季59/用递归函数求用递归函数求n!int f(int n)if(n=0)return 1;else return n*f(n-1);递归函数的执行过程递归函数的执行过程递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季60n递归算法必须满足的三个条件：递归算法必须满足的三个条件：n有明确的有明确的结束条件结束条件：比如：比如n=0，此条件下可以直接得出结，此条件下可以直接得出结果：果：1；n要解决的问题可以转化为相对简单的同类型的问题，即有要解决的问题可以转化为相对简单的同类型的问题，即有递归条件递归条件，比如：，比如：n！可转化为！可转化为n(n-1)!n随着问题的逐次转换，最终能达到结束条件：比如算法中随着问题的逐次转换，最终能达到结束条件：比如算法中的的n在递归过程中逐次减少，必然会到达在递归过程中逐次减少，必然会到达n=0的时刻。的时刻。递归条件和结束条件递归条件和结束条件递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季61 汉诺塔问题是：有汉诺塔问题是：有A A，B B，C C三个柱子，柱子三个柱子，柱子A A上穿有上穿有n n个个大小不同的圆盘，大盘在下，小盘在上。现要把柱子大小不同的圆盘，大盘在下，小盘在上。现要把柱子A A上的所上的所有圆盘移到柱子有圆盘移到柱子B B上，要求每次只能移动一个圆盘，且大盘不上，要求每次只能移动一个圆盘，且大盘不能放在小盘上，移动时可借助柱子能放在小盘上，移动时可借助柱子C C。编写一个编写一个C C函数函数给出移动步骤，如：给出移动步骤，如：n=3n=3时，移动步骤为：时，移动步骤为：A AB,AB,AC,BC,BC,AC,AB,CB,CA,CA,CB,AB,AB B。A B C汉诺塔问题汉诺塔问题递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季62n当当n=1时，只要把圆盘从时，只要把圆盘从A移至移至B就可以了（输出：就可以了（输出：AB）。而当。而当n大于大于1时，我们可以把该问题分时，我们可以把该问题分解成下面的三个子问题：解成下面的三个子问题：1.把把n-1个圆盘从柱子个圆盘从柱子A移到柱子移到柱子C。2.把第把第n个圆盘从柱子个圆盘从柱子A移到柱子移到柱子B。3.把把n-1个圆盘从柱子个圆盘从柱子C移到柱子移到柱子B。n上面的子问题上面的子问题1和和3与原问题相同，只是盘子的个与原问题相同，只是盘子的个数少了一个；子问题数少了一个；子问题2是移动一个盘子的简单问是移动一个盘子的简单问题。题。递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季63void hanoi(char x,char y,char z,int n)/把把n个圆盘从个圆盘从x表示的表示的 /柱子移至柱子移至y所表示的柱子。所表示的柱子。if(n=1)printf(1:%c-%cn,x,y);/把第把第1个个/盘子从盘子从x表示的柱子移至表示的柱子移至y所表示的柱子。所表示的柱子。elsehanoi(x,z,y,n-1);/把把n-1个圆盘从个圆盘从x表示的柱子移至表示的柱子移至 /z所表示的柱子。所表示的柱子。printf(%d:%c-%cn,n,x,y);/把第把第n个圆盘从个圆盘从x表示的柱子移至表示的柱子移至y所表示的柱子。所表示的柱子。hanoi(z,y,x,n-1);/把把n-1个圆盘从个圆盘从z表示的柱子移至表示的柱子移至 /y所表示的柱子。所表示的柱子。递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季64#include int main()int n;printf(请输入盘子数：请输入盘子数：n);scanf(%d,&n);printf(移动盘子步骤为：移动盘子步骤为：n);hanoi(A,B,C,n);return 0;高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季65使用循环（迭代）实现使用循环（迭代）实现unsigned int GetFactorial(unsigned int n)unsigned int result=1,i=0;while(+i=n)result*=i;return result;使用递归实现使用递归实现unsigned int GetFactorial(unsigned int n)unsigned int result;if(n=0)result=1;else result=n*GetFactorial(n-1);return result;阶乘函数阶乘函数递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季66使用循环（迭代）实现使用循环（迭代）实现unsigned int GetFibonacci(unsigned int n)unsigned int result,i,f1,f2;if(n=2|n=1)return 1;f2=1;f1=1;for(i=3;i=n;i+)result=f1+f2;f1=f2;f2=result;return result;使用递归实现使用递归实现unsigned int GetFibonacci(unsigned int n)if(n=2|n=1)return 1;else return GetFibonacci(n-1)+GetFibonacci(n-2);斐波那契数列函数斐波那契数列函数递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季67n对于一些递归定义的问题，用递归函数来解决会显得对于一些递归定义的问题，用递归函数来解决会显得比较自然和简洁，而用循环来解决这样的问题，有时比较自然和简洁，而用循环来解决这样的问题，有时会很复杂，不易设计和理解。会很复杂，不易设计和理解。n在实现数据的重复操作上，它们有一点不同：在实现数据的重复操作上，它们有一点不同：n循环是从特殊情况到一般情况的推导；循环是从特殊情况到一般情况的推导；n递归则从一般情况到特殊情况的嵌套。递归则从一般情况到特殊情况的嵌套。n由于递归表达的重复操作是通过函数调用来实现的，由于递归表达的重复操作是通过函数调用来实现的，而函数调用是需要开销的而函数调用是需要开销的 n递归算法有时会出现重复计算。递归算法有时会出现重复计算。递归与循环的选择递归与循环的选择递归函数递归函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季68n 3.1 函数函数n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季69n模块化与函数抽象模块化与函数抽象n模块化负责组织函数，进行任务划分，强调设计模块化负责组织函数，进行任务划分，强调设计n模块间通信使用接口，给出在本模块中定义的、提供给其它模模块间通信使用接口，给出在本模块中定义的、提供给其它模块使用的一些程序实体（如：函数、全局变量等）的声明块使用的一些程序实体（如：函数、全局变量等）的声明n结构化与函数抽象结构化与函数抽象n结构化负责实现函数，强调编码结构化负责实现函数，强调编码n抽象手段：函数抽象手段：函数程序的结构化与模块化程序的结构化与模块化高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季70n 3.1 函数函数n 3.2 递归函数递归函数n 3.3 程序的结构化与模块化程序的结构化与模块化n 3.4 程序测试与代码优化程序测试与代码优化第三章第三章 过程抽象函数过程抽象函数高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季71n程序测试原则程序测试原则n顺序结构：一般一次测试。顺序结构：一般一次测试。n分支结构：每条路径都需要测试分支结构：每条路径都需要测试n循环结构：一般测试第一次、最后一次与中间某次迭代循环结构：一般测试第一次、最后一次与中间某次迭代n代码优化代码优化n一般对循环进行优化，如考虑是否能降低循环次数等。一般对循环进行优化，如考虑是否能降低循环次数等。程序测试与代码优化程序测试与代码优化高级语言程序设计SEIC+C+C+C+程序设计基础 2009秋季72n结构化与模块化结构化与模块化n重要程序设计原则！重要程序设计原则！n函数的声明、调用与定义函数的声明、调用与定义n函数参数传递机制函数参数传递机制n值传递值传递n函数调用栈框架函数调用栈框架n递归函数递归函数n程序测试与代码优化程序测试与代码优化本