C程序语言课件：第7章 函数

《C程序语言课件：第7章 函数》由会员分享，可在线阅读，更多相关《C程序语言课件：第7章 函数（71页珍藏版）》请在金锄头文库上搜索。

1、第第第第7 7 7 7章章章章 函数函数函数函数2024/8/12/78本章学习内容本章学习内容本章学习内容本章学习内容 函数定义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数传递与返回值传递与返回值传递与返回值传递与返回值 递归函数和函数的递归调用递归函数和函数的递归调用递归函数和函数的递归调用递归函数和函数的递归调用 函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，程序的健壮

2、性程序的健壮性程序的健壮性程序的健壮性 变量的作用域与存储类型，全局变量、自动变变量的作用域与存储类型，全局变量、自动变变量的作用域与存储类型，全局变量、自动变变量的作用域与存储类型，全局变量、自动变量、静态变量、寄存器变量量、静态变量、寄存器变量量、静态变量、寄存器变量量、静态变量、寄存器变量2024/8/13/78数学中的函数数学中的函数数学中的函数数学中的函数自变量自变量因变量因变量函数名函数名程序设计中的函数程序设计中的函数程序设计中的函数程序设计中的函数 程序设计中的函数不局限于计算程序设计中的函数不局限于计算计算类，如打印阶乘表的程序计算类，如打印阶乘表的程序计算类，如打印阶乘表的

3、程序计算类，如打印阶乘表的程序判断推理类，如排序、查找判断推理类，如排序、查找判断推理类，如排序、查找判断推理类，如排序、查找2024/8/14/78问题的提出问题的提出 读多少行的程序能让你不头疼？读多少行的程序能让你不头疼？读多少行的程序能让你不头疼？读多少行的程序能让你不头疼？ 假如系统提供的函数假如系统提供的函数假如系统提供的函数假如系统提供的函数printf()printf()由由由由1010行代码替行代码替行代码替行代码替换，那么你编过的程序会成什么样子？换，那么你编过的程序会成什么样子？换，那么你编过的程序会成什么样子？换，那么你编过的程序会成什么样子？实际上一个实际上一个实际上

4、一个实际上一个printf()printf()有上千行代码有上千行代码有上千行代码有上千行代码 main()main()中能放多少行代码？中能放多少行代码？中能放多少行代码？中能放多少行代码？ 如果所有代码都在如果所有代码都在如果所有代码都在如果所有代码都在main()main()中，怎么团队合作中，怎么团队合作中，怎么团队合作中，怎么团队合作？ 如果代码都在一个文件中，怎么团队合作？如果代码都在一个文件中，怎么团队合作？如果代码都在一个文件中，怎么团队合作？如果代码都在一个文件中，怎么团队合作？2024/8/15/787.17.1分而治之与信息隐藏分而治之与信息隐藏分而治之与信息隐藏分而治之

5、与信息隐藏 分而治之（分而治之（ Divide and Conquer,Wirth, 1971 ）函数把较大的任务分解成若干个较小的任务，并函数把较大的任务分解成若干个较小的任务，并函数把较大的任务分解成若干个较小的任务，并函数把较大的任务分解成若干个较小的任务，并提炼出公用任务提炼出公用任务提炼出公用任务提炼出公用任务 信息隐藏（信息隐藏（Information Hiding, Parnas, 1972）设计得当的函数可把具体操作细节对外界隐藏起设计得当的函数可把具体操作细节对外界隐藏起设计得当的函数可把具体操作细节对外界隐藏起设计得当的函数可把具体操作细节对外界隐藏起来，从而使整个程序结构

6、清楚来，从而使整个程序结构清楚来，从而使整个程序结构清楚来，从而使整个程序结构清楚使用函数时，不用知道函数内部是如何运作的，使用函数时，不用知道函数内部是如何运作的，使用函数时，不用知道函数内部是如何运作的，使用函数时，不用知道函数内部是如何运作的，只按照我们的需要和它的参数形式调用它即可只按照我们的需要和它的参数形式调用它即可只按照我们的需要和它的参数形式调用它即可只按照我们的需要和它的参数形式调用它即可2024/8/16/78 函数是函数是C语言中模块化编程的最小单位语言中模块化编程的最小单位可以把每个函数看作一个模块（可以把每个函数看作一个模块（可以把每个函数看作一个模块（可以把每个函数

7、看作一个模块（ Module Module ） 如把编程比做制造一台机器，函数就好比其如把编程比做制造一台机器，函数就好比其零部件零部件可将这些可将这些可将这些可将这些“零部件零部件零部件零部件”单独设计、调试、测试好，单独设计、调试、测试好，单独设计、调试、测试好，单独设计、调试、测试好，用时拿出来装配，再总体调试。用时拿出来装配，再总体调试。用时拿出来装配，再总体调试。用时拿出来装配，再总体调试。这些这些这些这些“零部件零部件零部件零部件”可以是自己设计制造可以是自己设计制造可以是自己设计制造可以是自己设计制造/ / / /别人设计别人设计别人设计别人设计制造制造制造制造/ / / /现成

8、的标准产品现成的标准产品现成的标准产品现成的标准产品7.2 7.2 函数（函数（函数（函数（FunctionFunction）的定义）的定义）的定义）的定义MoeCurlyLarry2024/8/17/787.2 函数（函数（Function）的定义）的定义 若干相关的函数可以合并成一个若干相关的函数可以合并成一个若干相关的函数可以合并成一个若干相关的函数可以合并成一个“模块模块模块模块” 一个一个一个一个C C C C程序程序程序程序由一个或多个源程序文件组成由一个或多个源程序文件组成由一个或多个源程序文件组成由一个或多个源程序文件组成 一个源程序文件一个源程序文件一个源程序文件一个源程序文

9、件由一个或多个函数组成由一个或多个函数组成由一个或多个函数组成由一个或多个函数组成2024/8/18/787.2.1函数的分类函数的分类 函数生来都是平等的，互相独立的，没有函数生来都是平等的，互相独立的，没有高低贵贱和从属之分高低贵贱和从属之分main()main()稍微特殊一点点稍微特殊一点点稍微特殊一点点稍微特殊一点点C C程序的执行程序的执行程序的执行程序的执行从从从从mainmain函数开始函数开始函数开始函数开始调用其他函数后流程回到调用其他函数后流程回到调用其他函数后流程回到调用其他函数后流程回到mainmain函数函数函数函数在在在在mainmain函数中结束整个程序运行函数中

10、结束整个程序运行函数中结束整个程序运行函数中结束整个程序运行2024/8/19/787.2.1函数的分类函数的分类 标准库函数标准库函数ANSI/ISO CANSI/ISO C定义的标准库函数定义的标准库函数定义的标准库函数定义的标准库函数 符合标准的符合标准的符合标准的符合标准的C C语言编译器必须提供这些函数语言编译器必须提供这些函数语言编译器必须提供这些函数语言编译器必须提供这些函数 函数的行为也要符合函数的行为也要符合函数的行为也要符合函数的行为也要符合ANSI/ISO CANSI/ISO C的定义的定义的定义的定义第三方库函数第三方库函数第三方库函数第三方库函数 由其他厂商自行开发的

11、由其他厂商自行开发的由其他厂商自行开发的由其他厂商自行开发的C C语言函数库语言函数库语言函数库语言函数库 不在标准范围内，能扩充不在标准范围内，能扩充不在标准范围内，能扩充不在标准范围内，能扩充C C语言的功能（图形、网络、数据语言的功能（图形、网络、数据语言的功能（图形、网络、数据语言的功能（图形、网络、数据库等）库等）库等）库等） 自定义函数自定义函数自己定义的函数自己定义的函数自己定义的函数自己定义的函数 包装后，也可成为函数库，供别人使用包装后，也可成为函数库，供别人使用包装后，也可成为函数库，供别人使用包装后，也可成为函数库，供别人使用2024/8/110/787.2.2函数的定义

12、函数的定义（Function Definition）类型类型 函数名函数名( (类型类型 参数参数1, 1, 类型类型 参数参数2, 2, ) ) ) ) 声明语句序列声明语句序列声明语句序列声明语句序列 可执行语句序列可执行语句序列可执行语句序列可执行语句序列 returnreturn 表达式表达式表达式表达式; ; ; ; 返回值返回值类型类型函数名函数名标识符，标识符，说明运算规则说明运算规则参数表参数表相当于相当于运算的操作数运算的操作数返回返回运算的结果运算的结果函数出口函数出口2024/8/111/78类型类型 函数名函数名( (类型类型 参数参数1, 1, 类型类型 参数参数2,

13、 2, ) ) ) ) 声明语句序列声明语句序列声明语句序列声明语句序列 可执行语句序列可执行语句序列可执行语句序列可执行语句序列 returnreturn 表达式表达式表达式表达式; ; 函数体的定界符函数体的定界符参数表里的变量（叫形式参数，参数表里的变量（叫形式参数，Formal Parameter）也是内部变量）也是内部变量函数体函数体7.2.27.2.2函数的定义函数的定义函数的定义函数的定义（Function DefinitionFunction Definition）2024/8/112/78void 函数名函数名(void) 声明语句序列声明语句序列声明语句序列声明语句序列 可

14、执行语句可执行语句可执行语句可执行语句序列序列序列序列 returnreturn; ; 函数无返回值，用函数无返回值，用void定义返回值类型定义返回值类型用用void定义参数，定义参数，表示没有参数表示没有参数return语句后无语句后无需任何表达式需任何表达式7.2.27.2.2函数的定义函数的定义函数的定义函数的定义（Function DefinitionFunction Definition）2024/8/113/78【例例7.1a】 计算整数计算整数n的阶乘的阶乘n！ /* /* 函数功能：函数功能：函数功能：函数功能： 用迭代法用迭代法用迭代法用迭代法计计算算算算n!n! 函数入口

15、参数：函数入口参数：函数入口参数：函数入口参数： 整型整型整型整型变变量量量量n n表示表示表示表示阶阶乘的乘的乘的乘的阶阶数数数数 函数返回函数返回函数返回函数返回值值： 返回返回返回返回n!n!的的的的值值* */ /long Fact(int n) /* long Fact(int n) /* 函数定函数定函数定函数定义义 * */ / int i; int i; long result = 1; long result = 1; for (i=2; i=n; i+) for (i=2; i=n; i+) result *= i; result *= i; return result;

16、return result; 返回值类型返回值类型函数名说明函数名说明函数的功能函数的功能返回值作为函数返回值作为函数调用表达式的值调用表达式的值形参表，函形参表，函数入口数入口函数内部可以定义函数内部可以定义只能自己使用的变只能自己使用的变量，称内部变量量，称内部变量2024/8/114/78 函数名函数名( (表达式表达式1, 1, 表达式表达式2, 2, );); 实际参数实际参数实际参数实际参数(Actual Argument )(Actual Argument )(Actual Argument )(Actual Argument )函数调用函数调用函数调用函数调用(Founctio

17、n Call)(Founction Call)(Founction Call)(Founction Call)时提供的表达式时提供的表达式时提供的表达式时提供的表达式 有返回值时有返回值时有返回值时有返回值时放到一个数值表达式中放到一个数值表达式中放到一个数值表达式中放到一个数值表达式中 c = max(a,b);c = max(a,b);作为另一个函数调用的参数作为另一个函数调用的参数作为另一个函数调用的参数作为另一个函数调用的参数 c = max(max(a,b),c);c = max(max(a,b),c); printf( printf( %dn%dn , max(a,b);, max

18、(a,b); 无返回值时无返回值时无返回值时无返回值时函数调用表达式函数调用表达式函数调用表达式函数调用表达式 display(a,b); display(a,b); 返回值返回值返回值返回值 = = = = 函数名函数名函数名函数名( ( ( (实参表列实参表列实参表列实参表列);););); 函数名函数名函数名函数名( ( ( (实参表列实参表列实参表列实参表列););););7.37.3向函数传递值和从函数返回值向函数传递值和从函数返回值向函数传递值和从函数返回值向函数传递值和从函数返回值2024/8/115/78函数的参数传递函数的参数传递 实参和形参必须匹配实参和形参必须匹配实参和形

19、参必须匹配实参和形参必须匹配数目一致，类型一一对应（否则会发生自动类型转换）数目一致，类型一一对应（否则会发生自动类型转换）数目一致，类型一一对应（否则会发生自动类型转换）数目一致，类型一一对应（否则会发生自动类型转换）【例例7.1】 2024/8/116/787.3.2函数原型函数原型（Function Prototype） 在调用函数前先声明其返回值类型、函数名和参数在调用函数前先声明其返回值类型、函数名和参数在调用函数前先声明其返回值类型、函数名和参数在调用函数前先声明其返回值类型、函数名和参数 函数原型有助于编译器对函数参数类型的匹配检查函数原型有助于编译器对函数参数类型的匹配检查函数

20、原型有助于编译器对函数参数类型的匹配检查函数原型有助于编译器对函数参数类型的匹配检查 末尾有一个分号，末尾有一个分号，声明时不要省略形声明时不要省略形参和返回值的类型参和返回值的类型【例例7.1】 2024/8/117/78函数定义与函数声明的区别函数定义与函数声明的区别 函数定义函数定义指函数功能的确立指函数功能的确立指函数功能的确立指函数功能的确立指定函数名、函数类型、形参及类型、函数体等指定函数名、函数类型、形参及类型、函数体等指定函数名、函数类型、形参及类型、函数体等指定函数名、函数类型、形参及类型、函数体等是完整独立的单位是完整独立的单位是完整独立的单位是完整独立的单位 函数声明函数

21、声明是对函数名、返回值类型、形参类型的说明是对函数名、返回值类型、形参类型的说明是对函数名、返回值类型、形参类型的说明是对函数名、返回值类型、形参类型的说明不包括函数体不包括函数体不包括函数体不包括函数体是一条语句，以分号结束，只起一个声明作用是一条语句，以分号结束，只起一个声明作用是一条语句，以分号结束，只起一个声明作用是一条语句，以分号结束，只起一个声明作用2024/8/118/787.3.3函数封装函数封装与防御性程序设计与防御性程序设计 函数封装函数封装函数封装函数封装（EncapsulationEncapsulation）使得外界对函数的影使得外界对函数的影使得外界对函数的影使得外界

22、对函数的影响仅限于入口参数，而函数对外界的影响仅限于一响仅限于入口参数，而函数对外界的影响仅限于一响仅限于入口参数，而函数对外界的影响仅限于一响仅限于入口参数，而函数对外界的影响仅限于一个返回值和数组、指针类型的参数个返回值和数组、指针类型的参数个返回值和数组、指针类型的参数个返回值和数组、指针类型的参数 【例例7.1】 Why?传入负数实参传入负数实参会怎样？会怎样？2024/8/119/78防御性程序设计防御性程序设计（Defensive Programming） 如何使函数具有遇到不正确使用或非法数据输入时如何使函数具有遇到不正确使用或非法数据输入时如何使函数具有遇到不正确使用或非法数据

23、输入时如何使函数具有遇到不正确使用或非法数据输入时避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？ 在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性 【例例例例7.27.27.27.2】 计算整数计算整数计算整数计算整数n n的阶乘的阶乘的阶乘的阶乘n n！ 2024/8/120/78 如何使函数具有遇到不正确使用或非法数据输入时如何使函数具有遇到不正确使用或非法数据输入时如何使函数具有遇到不正确使用或非法数据输

24、入时如何使函数具有遇到不正确使用或非法数据输入时避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？避免出错的能力，增强程序的健壮性？ 在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性在函数的入口处，检查输入参数的合法性 防御性程序设计防御性程序设计（Defensive Programming） 【例例例例7.27.27.27.2】计算整数计算整数计算整数计算整数n n的阶乘的阶乘的阶乘的阶乘n n！ 2024/8/121/78 主函数如何修改？主函数如何修改？增加对函数返回值的检验增

25、加对函数返回值的检验增加对函数返回值的检验增加对函数返回值的检验 防御性程序设计防御性程序设计（Defensive Programming） 【例例例例7.37.37.37.3】计算整数计算整数计算整数计算整数n n的阶乘的阶乘的阶乘的阶乘n n！ 2024/8/122/78 传入负数的实参时传入负数的实参时Fact()会返回会返回-1吗？吗？存在死代码的原因何在？存在死代码的原因何在？存在死代码的原因何在？存在死代码的原因何在？防御性程序设计防御性程序设计（Defensive Programming） 【例例例例7.37.37.37.3】计算整数计算整数计算整数计算整数n n的阶乘的阶乘的阶

26、乘的阶乘n n！ 2024/8/123/78 如何修改程序去除冗余代码？如何修改程序去除冗余代码？ 如何保证不会传入负数实参？如何保证不会传入负数实参？防御性程序设计防御性程序设计（Defensive Programming） 【例例例例7.27.27.27.2】计算整数计算整数计算整数计算整数n n的阶乘的阶乘的阶乘的阶乘n n！ 2024/8/124/78【例例7.4】编写计算组合数的程序编写计算组合数的程序函数复用函数复用2024/8/125/78void assert（int expression）expression为真，什么都不作真，什么都不作否否则，提示出，提示出错，并，并终止程

27、序。止程序。如：如： #include #include main() int x,y,b,a; scanf(%d%d%d,&x,&y,&a); b=x-y*2; assert(b!=0); printf(a/b=%dn,a/b); Assert()查错查错使用断言（使用断言（assert）防止某些参数获得非法值，在程序调试）防止某些参数获得非法值，在程序调试和测试时发现错误和测试时发现错误.2024/8/126/78【例例7.2】 计算整数计算整数n的阶乘的阶乘n！ 2024/8/127/781、删除除assert()语句句2、#define NDEBUG /不跟踪不跟踪调试 #includ

28、e 因因为assert()是一个宏，其定是一个宏，其定义：#ifdef NDEBUG #define assert(x) (void)0) #else #define assert(e) (e)?(void)0:_assert(#e,_FILE_,_LINE_)#endifAssert()只用于调试程序时，调试结束使其只用于调试程序时，调试结束使其不起作用的方法：不起作用的方法：2024/8/128/787.3.4函数设计的基本原则函数设计的基本原则 信息隐藏信息隐藏1函数规模函数规模要小要小2函数功能函数功能要单一要单一3函数接口函数接口定义定义要要清楚清楚入口参数有效性检查入口参数有效性检

29、查敏感操作前的检查敏感操作前的检查调用成功与否的检查调用成功与否的检查2024/8/129/78函数的嵌套调用函数的嵌套调用函数的嵌套调用函数的嵌套调用 嵌套调用嵌套调用嵌套调用嵌套调用在调用一个函数的过程中，又调用另一个函数在调用一个函数的过程中，又调用另一个函数在调用一个函数的过程中，又调用另一个函数在调用一个函数的过程中，又调用另一个函数 C C语言规定函数不能嵌套定义，但可以嵌套调用语言规定函数不能嵌套定义，但可以嵌套调用语言规定函数不能嵌套定义，但可以嵌套调用语言规定函数不能嵌套定义，但可以嵌套调用函数是相互平行的函数是相互平行的函数是相互平行的函数是相互平行的 main()a();

30、a 函数函数b();return;b函数函数return;2024/8/130/787.4 递归函数递归函数（Recursive Function）7.4.17.4.1递归问题的提出递归问题的提出 经典的汉诺塔（经典的汉诺塔（Hanoi）问题）问题理解理解理解理解递归递归递归递归的概念的概念的概念的概念有人曾计算过，当有人曾计算过，当有人曾计算过，当有人曾计算过，当n n=64=64时，所需移动的次数时，所需移动的次数时，所需移动的次数时，所需移动的次数为为为为1844674407370955161518446744073709551615，即，即，即，即18441844亿亿次亿亿次亿亿次亿亿

31、次若按每次耗时若按每次耗时若按每次耗时若按每次耗时1 1微秒计算，则完成微秒计算，则完成微秒计算，则完成微秒计算，则完成6464个圆盘的个圆盘的个圆盘的个圆盘的移动将需要移动将需要移动将需要移动将需要6060万年万年万年万年 它来自印度神话它来自印度神话.相传上帝创造世界时造相传上帝创造世界时造了了3根金刚石柱子根金刚石柱子,在第一根柱子上从下往上在第一根柱子上从下往上按大小顺序摞着按大小顺序摞着64片黄金圆盘片黄金圆盘,上帝命令婆罗上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放到门把圆盘从下面开始按大小顺序重新摆放到第二根柱子上第二根柱子上,并且规定并且规定,每次只能移动一个每次只能移动一

32、个圆盘圆盘,在小圆盘上不能放大圆盘在小圆盘上不能放大圆盘.有人预言有人预言,这这件事情完成时宇宙会在一瞬间闪电式地毁灭件事情完成时宇宙会在一瞬间闪电式地毁灭.也有人相信婆罗门至今仍在一刻不停地移动也有人相信婆罗门至今仍在一刻不停地移动着圆盘着圆盘.2024/8/131/78汉诺塔汉诺塔（Hanoi）问题问题 ABAB，ACAC，BCBC，ABAB，CACA，CBCB，ABABA AB BC Cn n=3=32024/8/132/78汉诺塔汉诺塔（Hanoi）问题问题A AB BC C ABAB，ACAC，BCBC，ABAB，CACA，CBCB，ABABn n=3=32024/8/133/78汉

33、诺塔汉诺塔（Hanoi）问题问题A AB BC C ABAB，ACAC，BCBC，ABAB，CACA，CBCB，ABABn n=3=32024/8/134/78汉诺塔汉诺塔（Hanoi）问题问题A AB BC C ABAB，ACAC，BCBC，ABAB，CACA，CBCB，ABABn n=3=32024/8/135/78汉诺塔汉诺塔（Hanoi）问题问题A AB BC Cn更大些更大些怎么办？怎么办？ ABAB，ACAC，BCBC，ABAB，CACA，CBCB，ABABn n=3=32024/8/136/78汉诺塔汉诺塔（Hanoi）问题问题 第第第第1 1 1 1步：将问题简化步：将问题简化

34、步：将问题简化步：将问题简化假假假假设设A A杆上只有杆上只有杆上只有杆上只有2 2个个个个圆盘圆盘，即，即，即，即汉诺汉诺塔有塔有塔有塔有2 2层层，n n2 2将将将将1 1号号号号圆盘圆盘从从从从A A移到移到移到移到C C将将将将2 2号号号号圆盘圆盘从从从从A A移到移到移到移到B B将将将将1 1号号号号圆盘圆盘从从从从C C移到移到移到移到B B A AB BC C2024/8/137/78汉诺塔汉诺塔（Hanoi）问题问题 第第第第2 2步：对于一个有步：对于一个有步：对于一个有步：对于一个有 n n（n n11）个圆盘的汉诺塔，）个圆盘的汉诺塔，）个圆盘的汉诺塔，）个圆盘的汉

35、诺塔，将将将将n n个圆盘分为两部分：上面个圆盘分为两部分：上面个圆盘分为两部分：上面个圆盘分为两部分：上面 n n- -1 1 个圆盘和最下面个圆盘和最下面个圆盘和最下面个圆盘和最下面的的的的n n号圆盘。将号圆盘。将号圆盘。将号圆盘。将“ “上面上面上面上面n n- -1 1个圆盘个圆盘个圆盘个圆盘” ”看成一个整体看成一个整体看成一个整体看成一个整体将将将将n n- -1 1个个个个圆盘圆盘从从从从A A移到移到移到移到C C将将将将n n号号号号圆盘圆盘从从从从A A移到移到移到移到B B将将将将n n- -1 1个个个个圆盘圆盘从从从从C C移到移到移到移到B BAC CB2024/

36、8/138/78汉诺塔汉诺塔（Hanoi）问题问题 设计设计设计设计2 2 2 2个函数：个函数：个函数：个函数：将将将将n n个圆盘借助个圆盘借助个圆盘借助个圆盘借助C C从从从从A A移到移到移到移到B B 将一个圆盘从将一个圆盘从将一个圆盘从将一个圆盘从A A移到移到移到移到B B AC CB将将将将n n- -1 1个圆盘从个圆盘从个圆盘从个圆盘从A A移到移到移到移到C C将将将将n n号圆盘从号圆盘从号圆盘从号圆盘从A A移到移到移到移到B B将将将将n n- -1 1个圆盘从个圆盘从个圆盘从个圆盘从C C移到移到移到移到B B2024/8/139/78汉诺塔汉诺塔汉诺塔汉诺塔（H

37、anoiHanoi）问题问题问题问题 递归方法的基本原理递归方法的基本原理将复杂问题逐步化简，最终转化为一个最简单将复杂问题逐步化简，最终转化为一个最简单将复杂问题逐步化简，最终转化为一个最简单将复杂问题逐步化简，最终转化为一个最简单的问题的问题的问题的问题最简单问题的解决就意味着整个问题的解决最简单问题的解决就意味着整个问题的解决最简单问题的解决就意味着整个问题的解决最简单问题的解决就意味着整个问题的解决 2024/8/140/78汉诺塔汉诺塔汉诺塔汉诺塔（HanoiHanoi）问题问题问题问题2024/8/141/787.4.27.4.2递归函数递归函数递归函数递归函数longlong f

38、actfact( (intint n) n) ifif (n 0) (n 0) returnreturn -1; -1; else ifelse if (n = 0 | n = 1) (n = 0 | n = 1) returnreturn 1; 1; elseelse returnreturn n * n * factfact(n-1);(n-1); 【例例7.67.6】计算计算n！= n *(n-1)*(n-2)*1 函数直接或间接调用函数直接或间接调用自己，称为递归调用自己，称为递归调用（Recursive Call）2024/8/142/787.4.27.4.2递归函数递归函数递归函数

39、递归函数unsignedunsigned longlong factfact( (unsignedunsigned intint n) n) ifif (n = 0 | n = 1) (n = 0 | n = 1) returnreturn 1; 1;elseelse returnreturn n * n * factfact(n-1);(n-1); 基线情况基线情况(base case)一般情况一般情况(general case)无需考虑无需考虑n0了了【例例7.67.6】计算计算n！= n *(n-1)*(n-2)*1 2024/8/143/787.4.27.4.2递归函数递归函数递归函数

40、递归函数 递归调用应该能够在有限次数内终止递归递归调用应该能够在有限次数内终止递归递归调用若不加以限制，将无限循环调用递归调用若不加以限制，将无限循环调用递归调用若不加以限制，将无限循环调用递归调用若不加以限制，将无限循环调用必须在函数内部加控制语句，仅当满足一定条必须在函数内部加控制语句，仅当满足一定条必须在函数内部加控制语句，仅当满足一定条必须在函数内部加控制语句，仅当满足一定条件时，递归终止，称为件时，递归终止，称为件时，递归终止，称为件时，递归终止，称为条件递归条件递归条件递归条件递归 任何一个递归调用程序必须包括两部分任何一个递归调用程序必须包括两部分递归循环递归循环递归循环递归循环

41、继续继续继续继续的过程的过程的过程的过程递归调用递归调用递归调用递归调用结束结束结束结束的过程的过程的过程的过程 if (if (递归终止条件成立递归终止条件成立递归终止条件成立递归终止条件成立) ) return return 递归公式的初值递归公式的初值递归公式的初值递归公式的初值; ; elseelse return return 递归函数调用返回的结果值递归函数调用返回的结果值递归函数调用返回的结果值递归函数调用返回的结果值; ; 2024/8/144/78n!=n(n-1)! (n-1)!=(n-1)(n-2)! (n-2)! . (n-3)! 5! : 4!=43! 3!=32!

42、2!=21! 1!=1回推过程回推过程递推过程递推过程每个递归函数必须至每个递归函数必须至每个递归函数必须至每个递归函数必须至少有一个少有一个少有一个少有一个基线条件基线条件基线条件基线条件一般情况一般情况一般情况一般情况必须最终能必须最终能必须最终能必须最终能简化为基线条件简化为基线条件简化为基线条件简化为基线条件 递归层数太多易递归层数太多易递归层数太多易递归层数太多易导致栈空间溢出导致栈空间溢出导致栈空间溢出导致栈空间溢出后果很严重，程后果很严重，程后果很严重，程后果很严重，程序被异常中止序被异常中止序被异常中止序被异常中止 fact(5)=5*fact(4)= 120 fact(4)=

43、 4*fact(3)= 24 fact(3)= 3*fact(2)= 6 fact(2)= 2*fact(1)=2 fact(1)=1mainmainfact(5)fact(5)fact(4)fact(4)fact(3)fact(3)fact(2)fact(2)fact(1)fact(1)2024/8/145/78递归与迭代递归与迭代递归与迭代递归与迭代 用用用用迭代迭代迭代迭代（即循环即循环即循环即循环）方法编写的阶乘函数方法编写的阶乘函数方法编写的阶乘函数方法编写的阶乘函数unsigned longunsigned long Fact( Fact(unsignedunsigned inti

44、nt n) n) unsigned longunsigned long result = 1; result = 1; unsigned intunsigned int i; i; forfor (i = 1; i = n; i+) (i = 1; i = n; i+) result *= i; result *= i; returnreturn result; result; 递归程序遵循了数学中对阶乘的定义递归程序遵循了数学中对阶乘的定义递归程序遵循了数学中对阶乘的定义递归程序遵循了数学中对阶乘的定义 因此递归方法编写程序具有因此递归方法编写程序具有因此递归方法编写程序具有因此递归方法编写

45、程序具有更清晰、可读性更好更清晰、可读性更好更清晰、可读性更好更清晰、可读性更好的优点的优点的优点的优点 2024/8/146/78递归与迭代递归与迭代递归与迭代递归与迭代1 1，1 1，2 2，3 3，5 5，8 8，.longlong Fib( Fib(intint n) n) longlong f; f;ifif (n = 0) f = 0; (n = 0) f = 0;else ifelse if (n = 1) f = 1; (n = 1) f = 1;else else f = Fib(n-1) + Fib(n-2);f = Fib(n-1) + Fib(n-2);returnre

46、turn f; f; 1 15 54 43 32 23 32 22 21 11 10 01 10 01 10 0计算计算计算计算fib(5)fib(5)共需共需共需共需1515次次次次fibfib调用调用调用调用【例例例例7.77.77.77.7】计算计算计算计算FibonacciFibonacci数列数列数列数列 2024/8/147/78递归与迭代递归与迭代递归与迭代递归与迭代 优点：优点：从编程角度来看，比较直观、精炼，逻辑清楚从编程角度来看，比较直观、精炼，逻辑清楚从编程角度来看，比较直观、精炼，逻辑清楚从编程角度来看，比较直观、精炼，逻辑清楚符合人的思维习惯，逼近数学公式的表示符合人

47、的思维习惯，逼近数学公式的表示符合人的思维习惯，逼近数学公式的表示符合人的思维习惯，逼近数学公式的表示尤其适合非数值计算领域尤其适合非数值计算领域尤其适合非数值计算领域尤其适合非数值计算领域 hanoihanoi塔塔塔塔，骑士游历、八皇后问题（回溯法），骑士游历、八皇后问题（回溯法），骑士游历、八皇后问题（回溯法），骑士游历、八皇后问题（回溯法） 缺点：缺点：增加了函数调用的开销，增加了函数调用的开销，增加了函数调用的开销，增加了函数调用的开销，每次调用都需要进行每次调用都需要进行每次调用都需要进行每次调用都需要进行参数传递、现场保护等参数传递、现场保护等参数传递、现场保护等参数传递、现场保护

48、等耗费更多的时间和栈空间耗费更多的时间和栈空间耗费更多的时间和栈空间耗费更多的时间和栈空间应尽量用迭代形式替代递归形式应尽量用迭代形式替代递归形式应尽量用迭代形式替代递归形式应尽量用迭代形式替代递归形式2024/8/148/787.57.5变量的作用域和存储类型变量的作用域和存储类型变量的作用域和存储类型变量的作用域和存储类型7.5.17.5.1变量的作用域变量的作用域 （ Scope ） 指在源程序中定义变量的位置及其能被读指在源程序中定义变量的位置及其能被读写访问的范围写访问的范围 分为分为局部变量（局部变量（局部变量（局部变量（Local VariableLocal Variable）

49、全局变量（全局变量（全局变量（全局变量（Global Variable )Global Variable )2024/8/149/78局部变量（局部变量（局部变量（局部变量（ Local VariableLocal Variable ） 在语句块内定义的变量在语句块内定义的变量形参也是局部变量形参也是局部变量形参也是局部变量形参也是局部变量 特点特点生存期是该语句块，进入语句块时获得内存，生存期是该语句块，进入语句块时获得内存，生存期是该语句块，进入语句块时获得内存，生存期是该语句块，进入语句块时获得内存，仅能由语句块内语句访问，退出语句块时释放仅能由语句块内语句访问，退出语句块时释放仅能由语

50、句块内语句访问，退出语句块时释放仅能由语句块内语句访问，退出语句块时释放内存，不再有效内存，不再有效内存，不再有效内存，不再有效定义时不会自动初始化，除非程序员指定初值定义时不会自动初始化，除非程序员指定初值定义时不会自动初始化，除非程序员指定初值定义时不会自动初始化，除非程序员指定初值并列语句块各自定义的同名变量互不干扰并列语句块各自定义的同名变量互不干扰并列语句块各自定义的同名变量互不干扰并列语句块各自定义的同名变量互不干扰 形参和实参可以同名形参和实参可以同名形参和实参可以同名形参和实参可以同名2024/8/150/78全局变量（全局变量（全局变量（全局变量（ Global Variab

51、le Global Variable ） 在所有函数之外定义的变量在所有函数之外定义的变量生存期是整个程序，从程序运行起占据内存，程生存期是整个程序，从程序运行起占据内存，程生存期是整个程序，从程序运行起占据内存，程生存期是整个程序，从程序运行起占据内存，程序运行过程中可随时访问，程序退出时释放内存序运行过程中可随时访问，程序退出时释放内存序运行过程中可随时访问，程序退出时释放内存序运行过程中可随时访问，程序退出时释放内存有效范围是从定义变量的位置开始到本程序结束有效范围是从定义变量的位置开始到本程序结束有效范围是从定义变量的位置开始到本程序结束有效范围是从定义变量的位置开始到本程序结束202

52、4/8/151/78全局变量（全局变量（ Global Variable ） 【例例例例7.87.87.87.8】打印计打印计打印计打印计算算算算FibonacciFibonacci数列每数列每数列每数列每一项时所需的递归一项时所需的递归一项时所需的递归一项时所需的递归调用次数调用次数调用次数调用次数 全局变量使函数间的数据交换更容易，更高效，全局变量使函数间的数据交换更容易，更高效，但建议尽量少用，因为谁都可改写它，所以很难但建议尽量少用，因为谁都可改写它，所以很难确定是谁改写了它确定是谁改写了它全局变量全局变量2024/8/152/787.5.27.5.2变量的存储类型（变量的存储类型（变

53、量的存储类型（变量的存储类型（ Storage ClassStorage Class） 指数据在内存中存储的方式指数据在内存中存储的方式即编译器为变量分配内存的方式，它决定变量的即编译器为变量分配内存的方式，它决定变量的即编译器为变量分配内存的方式，它决定变量的即编译器为变量分配内存的方式，它决定变量的生存期生存期生存期生存期 存储类型存储类型存储类型存储类型 数据类型数据类型数据类型数据类型 变量名变量名变量名变量名; ; ; ; C C C C程序的存储类别程序的存储类别程序的存储类别程序的存储类别autoauto型（自动变量）型（自动变量）型（自动变量）型（自动变量）staticstat

54、ic型（静态变量）型（静态变量）型（静态变量）型（静态变量）externextern型（外部变量）型（外部变量）型（外部变量）型（外部变量）registerregister型（寄存器变量）型（寄存器变量）型（寄存器变量）型（寄存器变量）2024/8/153/78静态存储区中的变量：静态存储区中的变量：与程序与程序“共存亡共存亡” 动态存储区中的变量：动态存储区中的变量：与程序块与程序块“共存亡共存亡” 寄存器中的变量：寄存器中的变量： 同动态存储区同动态存储区变量的生存期（变量的生存期（Lifetime ）决定何时决定何时决定何时决定何时“生生生生”，何时，何时，何时，何时“灭灭灭灭”7.5.

55、27.5.2变量的存储类型（变量的存储类型（变量的存储类型（变量的存储类型（ Storage ClassStorage Class）2024/8/154/78 auto auto 数据类型数据类型数据类型数据类型 变量名变量名变量名变量名; ; autoauto体现在体现在体现在体现在进入语句块时自动申请内存，退出时自动释放内存进入语句块时自动申请内存，退出时自动释放内存进入语句块时自动申请内存，退出时自动释放内存进入语句块时自动申请内存，退出时自动释放内存动态局部变量，缺省的存储类型动态局部变量，缺省的存储类型动态局部变量，缺省的存储类型动态局部变量，缺省的存储类型 静态变量静态变量静态变量

56、静态变量 static static 数据类型数据类型数据类型数据类型 变量名变量名变量名变量名; ;staticstatic storage class for storage class for locallocal variables (declared variables (declared insideinside a a block or function) - the lifetime of the entire programblock or function) - the lifetime of the entire program生存期为整个程序运行期间生存期为整个程序运行

57、期间生存期为整个程序运行期间生存期为整个程序运行期间自动变量和静态变量自动变量和静态变量2024/8/155/78【例例例例7.117.117.117.11】利用利用利用利用静态静态静态静态变量计算整数变量计算整数变量计算整数变量计算整数n n的阶乘的阶乘的阶乘的阶乘n n！ 自动变量和静态变量自动变量和静态变量静态变量仅初始静态变量仅初始化一次，变量的化一次，变量的值可保存到下次值可保存到下次进入函数，使函进入函数，使函数具有记忆功能数具有记忆功能2024/8/156/78自动变量和静态变量自动变量和静态变量【例例例例7.117.117.117.11】如果如果如果如果静态静态静态静态变量换成

58、自动变量，结果如何？变量换成自动变量，结果如何？变量换成自动变量，结果如何？变量换成自动变量，结果如何？ 静态局部变量和静态局部变量和全局变量自动初全局变量自动初始化为始化为0 0值。自动值。自动变量不初始化时，变量不初始化时，值是随机值值是随机值2024/8/157/78寄存器变量寄存器变量寄存器变量寄存器变量 寄存器寄存器CPUCPU内部容量有限、但速度极快的存储器内部容量有限、但速度极快的存储器内部容量有限、但速度极快的存储器内部容量有限、但速度极快的存储器 registerregister 类型名类型名类型名类型名 变量名变量名变量名变量名; ; 使用频率比较高的变量声明为使用频率比较

59、高的变量声明为使用频率比较高的变量声明为使用频率比较高的变量声明为registerregister ，可使，可使，可使，可使程序更小、执行速度更快程序更小、执行速度更快程序更小、执行速度更快程序更小、执行速度更快现代编译器有能力自动把普通变量优化为寄存器变量，现代编译器有能力自动把普通变量优化为寄存器变量，现代编译器有能力自动把普通变量优化为寄存器变量，现代编译器有能力自动把普通变量优化为寄存器变量，并且可以忽略用户的指定并且可以忽略用户的指定并且可以忽略用户的指定并且可以忽略用户的指定所以一般无需特别声明变量为所以一般无需特别声明变量为所以一般无需特别声明变量为所以一般无需特别声明变量为re

60、gisterregister 2024/8/158/78全局变量全局变量静态外部变量静态外部变量 （只限本文件使用）（只限本文件使用）外部变量外部变量 （非静态外部变量允许其他文件引用（非静态外部变量允许其他文件引用）局部变量局部变量 自动变量自动变量，（离开函数，值就消失），（离开函数，值就消失）寄存器变量寄存器变量（离开函数，值就消失）（离开函数，值就消失）定义点之前定义点之前使用，需用使用，需用extern声明声明静态局部变量静态局部变量 （离开函数，值仍保留）（离开函数，值仍保留）动态局部变量动态局部变量7.57.5变量的作用域和存储类型变量的作用域和存储类型变量的作用域和存储类型变量

61、的作用域和存储类型2024/8/159/78程序版式程序版式程序版式程序版式 缩进缩进缩进缩进( ( ( (IndentIndent) ) ) )保证代码整洁、层次清晰的主要手段保证代码整洁、层次清晰的主要手段保证代码整洁、层次清晰的主要手段保证代码整洁、层次清晰的主要手段 良好风格的程序应严格采用梯形层次对应好各层次良好风格的程序应严格采用梯形层次对应好各层次良好风格的程序应严格采用梯形层次对应好各层次良好风格的程序应严格采用梯形层次对应好各层次intint IsPrime( IsPrime(intint n) n) intint k, i; k, i; k = sqrt( k = sqrt

62、(doubledouble)n);)n); forfor (i=2; i=k; i+) (i=2; i=k; i+) ifif (n % i = 0) (n % i = 0) returnreturn 0; 0; returnreturn 1; 1; # #includeinclude main()main() intint i; i; forfor (i=2; i100; i+) (i=2; i100; i+) ifif (IsPrime(i) (IsPrime(i) printf(%dt,i); printf(%dt,i); 2024/8/160/78程序版式程序版式程序版式程序版式 现在

63、的许多开发环境、编辑软件都支持自动缩进现在的许多开发环境、编辑软件都支持自动缩进现在的许多开发环境、编辑软件都支持自动缩进现在的许多开发环境、编辑软件都支持自动缩进根据用户代码的输入，智能判断应该缩进还是反缩进，根据用户代码的输入，智能判断应该缩进还是反缩进，根据用户代码的输入，智能判断应该缩进还是反缩进，根据用户代码的输入，智能判断应该缩进还是反缩进，替用户完成调整缩进的工作替用户完成调整缩进的工作替用户完成调整缩进的工作替用户完成调整缩进的工作 VCVC中有自动整理格式功能中有自动整理格式功能中有自动整理格式功能中有自动整理格式功能只要选取需要的代码，按只要选取需要的代码，按只要选取需要的

64、代码，按只要选取需要的代码，按ALT+F8ALT+F8就能自动整理成微就能自动整理成微就能自动整理成微就能自动整理成微软的软的软的软的cppcpp文件格式文件格式文件格式文件格式2024/8/161/78命名规则命名规则命名规则命名规则 在在在在Linux/UNIXLinux/UNIX平台平台平台平台习惯用习惯用习惯用习惯用function_namefunction_name 本书采用本书采用本书采用本书采用WindowsWindows风格函数名命名风格函数名命名风格函数名命名风格函数名命名用大写字母开头、大小写混排的单词组合而成用大写字母开头、大小写混排的单词组合而成用大写字母开头、大小写混

65、排的单词组合而成用大写字母开头、大小写混排的单词组合而成 FunctionNameFunctionName 变量名形式变量名形式变量名形式变量名形式“名词名词名词名词”或者或者或者或者“形容词形容词形容词形容词+ + + +名词名词名词名词”如如如如oldValueoldValue与与与与newValuenewValue等等等等 函数名形式函数名形式函数名形式函数名形式“动词动词动词动词”或者或者或者或者“动词动词动词动词+ + + +名词名词名词名词”（动宾词组）（动宾词组）（动宾词组）（动宾词组）如如如如GetMax()GetMax()等等等等 2024/8/162/78对函数接口进行注释

66、说明对函数接口进行注释说明对函数接口进行注释说明对函数接口进行注释说明 /* /* 函数功能：函数功能：函数功能：函数功能：实现实现实现实现功能功能功能功能 函数参数：函数参数：函数参数：函数参数：参数参数参数参数1 1，表示，表示，表示，表示 参数参数参数参数2 2，表示，表示，表示，表示 函数返回值：函数返回值：函数返回值：函数返回值： * */ /返回值类型返回值类型返回值类型返回值类型 函数名函数名函数名函数名( ( ( (形参表形参表形参表形参表) ) ) ) returnreturn 表达式表达式表达式表达式; ; ; ; 2024/8/163/78本章学习内容本章学习内容 函数定

67、义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数函数定义、函数调用、函数原型、函数的参数传递与返回值传递与返回值传递与返回值传递与返回值 递归函数和函数的递归调用递归函数和函数的递归调用递归函数和函数的递归调用递归函数和函数的递归调用 函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，函数封装，函数复用，函数设计的基本原则，程序的健壮性程序的健壮性程序的健壮性程序的健壮性 变量的作用域与存储类型，全局变量、自动变变量的作用域与存储类型，全局变量、自动变变量的作

68、用域与存储类型，全局变量、自动变变量的作用域与存储类型，全局变量、自动变量、静态变量、寄存器变量量、静态变量、寄存器变量量、静态变量、寄存器变量量、静态变量、寄存器变量2024/8/164/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏 猜多个数，猜多个数，猜多个数，猜多个数，10101010次猜不对就猜下一个数次猜不对就猜下一个数次猜不对就猜下一个数次猜不对就猜下一个数 模块分解过程模块分解过程模块分解过程模块分解过程 开始开始开始开始结束结束结束结束初始化初始化初始化初始化退出处理退出处理退出处理退出处理主功能主功能主功能主功能为程序运行为程序运行所做的准备所做的准备工作工作在退

69、出前要做的在退出前要做的事情，如打印结事情，如打印结果、资源释放等果、资源释放等自底向上自底向上自顶向下的模块化程序设计自顶向下的模块化程序设计2024/8/165/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏开始开始开始开始结束结束结束结束生成数字生成数字生成数字生成数字猜数字猜数字猜数字猜数字2024/8/166/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏开始开始开始开始结束结束结束结束生成数字生成数字生成数字生成数字猜数字猜数字猜数字猜数字是否继续？是否继续？是否继续？是否继续？N NY Y2024/8/167/78【例例7.12】用函数完成猜数游戏用函数完成猜

70、数游戏开始开始开始开始结束结束结束结束猜得对吗？猜得对吗？猜得对吗？猜得对吗？N NY Y提示大小提示大小提示大小提示大小次数次数次数次数1010？输入数字输入数字输入数字输入数字N NY Y处理用户输入，判断是否有输入错误，处理用户输入，判断是否有输入错误，是否在合法的数值范围内是否在合法的数值范围内 2024/8/168/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏2024/8/169/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏2024/8/170/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏2024/8/171/78【例例7.12】用函数完成猜数游戏用函数完成猜数游戏