高级语言程序设计课件参考1第4章函数

第四章函数(三)4.1程序的模块化设计4.2函数定义与调用4.3形参与实参4.4变量作用域、生存期：局部与全局、静态变量4.5内部函数、外部函数4.6递归：N！、逆序输出、汉诺塔4.7预处理程序4.8编程指导4.6递归函数设计C函数既可以嵌套调用也可递归调用。递归调用分类：直接递归调用和间接递归调用。直接递归调用是函数自己调用自己间接递归调用是函数间接调用自己图4-19直接和间接递归调用4.6递归的二个条件条件1：必须有一个终止条件或计算准则条件2：每一次调用自已时必须更接近于解3。求n!4.6递归例子4.6递归例子4.6递归函数调用过程函数递归调用实质：是运行栈的管理，基本操作是以不同参数值逐层调用自己时，数据进栈；由被调用处逐层返回时，数据出栈。递归调用rfact（）计算3!如下图：

问题递归定义的数学函数n!1（n=0,n=1）递归结束条件n(n-1)!（n>1）递归定义sum=1+2+3+4+...+n0（n=0） 递归结束条件n+sum(n-1)（n>1） 递归定义最大公约数gcd(m,n)m（n=0）递归结束递归条件gcd(n,m%n)（n>0） 递归定义Fibonacci数列fib(n)0（n=0）递归结束条件1（n=1）递归结束条件fib(n-1)+fib(n-2)（n>1）递归定义递归方法定义的数学函数4.6递归请参看5.14递归应用举例：Fibonacci数列并上机完成该示例。4.6递归数据处理【例】用户输入一行thetarpat，然后使用递归函数逆序显示.reverse（），并略微扩展其功能，使它能够逆序输入行。#include<stdio.h>voidreverse(); /*reverse()原型说明*/intmain(void){ printf("inputaline:"); reverse(); printf("\n\n"); return0;}voidreverse(){ charc; if((c=getchar())!='\n') reverse(); putchar(c); //递归结束条件：读入换行符后开始显示}4.6递归---汉诺塔（haniotower）问题汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。123将n个盘分成两个子集(1至n-1和n)，从而产生下列三个子问题，

1.将1至n-1号盘从1轴移动至2轴（中间轴）move(n-1,1,2,3);

2.将n号盘从1轴移动至3轴（目标轴）；move(1,1,3,2); 3.将1至n-1号盘从2轴移动至3轴；move(n-1,2,3,1)移动时递归函数为：move(n个盘子，初始轴，目标轴，中间轴）4.6递归递归算法的一般形式：voidp(参数表）｛if(递归结束条件）

可直接求解步骤：－－－基本项

else p(较小的参数）：－－－归纳项｝4.6递归与迭代的比较递归和迭代都是建立在控制结构基础上的。迭代使用的是循环结构，递归使用的是选择结构。迭代和递归都用到了循环。迭代明确地使用循环结构。而递归是通过反复调用函数实现循环的。迭代和递归都用到了终止条件测试。迭代和递归都用到了终止条件测试。迭代是在继续循环的条件为假时结束，递归是在到达基本实例时终止的。递归和用计数器控制的迭代循环都是渐进到达终止条件的。迭代不断地修改计数器的值直到例继续循环的条件为假，递归不断简化原始问题直到实现基本实例为止。递归会占用处理器很多时间和大量内存，而迭代不需要反复调函数和占用额外的内存。递归能够更自然地反映解决问题的过程，并且易于理解和调试程序。通常优先选用递归。对程序性能要求比较高时应避免使用递归。

4.7C预处理程序预处理命令是C语言的一个重要功能，由“#”号开头，单独占一行，行尾不用分号结束。C语言提供包含类型：文件包含、宏定义和条件编译预处理意义：改进程序设计环境，提高编程效率，提高程序的可读性、可维护性和可移植性。4.7C预处理程序—文件包含文件包含是指一个源文件可以将另一个源文件的全部内容包含进来。文件包含的一般语法形式如下格式1：#include<包含文件名>格式2：#include“包含文件名”编写#include预处理命令时应注意以下几点：预处理时，预处理程序将查找指定的被包含文件，并将其复制到#include命令所在的位置。被包含文件必须是源文件。当被包含文件的内容改变后，包含该文件的所有源文件应重新编译。用在文件头部的被包含文件，称为“头文件”，以“h”作为文件名后缀，如#include“stdio.h”、#include“calc.h”等。一条包含命令，只能指定一个被包含文件。包含文件可以嵌套，即被包含文件中可以包含另一个文件。4.7C预处理程序—宏定义宏定义，即#define预处理命语法形式为：#define名字替换文本说明：宏定义使得程序中出现的各个名字被替换文本所替代。其中，名字为合法的C标识符；替换文本是任意字符串。宏定义名字的作用域从其定义开始到被编译的源文件结束。通常宏定义放在程序的开头。4.7C预处理程序—宏定义#define的一些说明如下:宏定义名字一般用大写，适当命名可以增强程序的可读性。如：

#defineEOF-1/*文件尾*/ #defineNULL0/*空指针*/#defineMIN1/*最小值*/#defineMAX31/*最大值*/#defineSTEP2/*步长*/宏定义可以使用前面已定义的宏，如：

#definePI3.1415926#defineRADIUS2#defineCIRCLE2*PI*RADIUS

4.7C预处理程序宏定义可以带形参，称为有参宏。如

#defineMAX(A,B)((A)>(B)?(A):(B))

说明：定义一个宏MAX，对MAX的使用很像函数调用。有参宏也是直接将替换文本插入到代码中。如：X=MAX(p+q,r+s);被替换为X=((p+q)>(r+s)?(p+q):(r+s))

有时，通过附加圆括号以保证有参宏的正确使用。宏定义：#defineSQUARE(x)x*x/*不正确的使用方式*/在形参为z+1时，宏SQUARE(z+1)将被替换为z+1*z+1

正确定义：为#defineSQUARE(x)(x)*(x)

一般而言简单表达式用有参宏来实现，其他情况建议使用有参函数实现。4.7C预处理程序—条件编译一般情况下，源程序所有的行都参加编译，但有时希望选择源程序的某些行进行编译，即对源程序指定编译条件。条件编译可提高程序的移植性，为一个程序提供不同的版本。#if-#else-#endif命令，其一般语法形式

#if常量表达式程序代码段1[#else

程序代码段2]#endif4.6递归---程序设计示例一迷宫寻路：递归算法求解对于以下１０＊１０的迷宫，输出从（１，１）到（１０，１０）的一条路径，如果不存在任何路径，打印出提示信息。用一个二维数组（１２＊１２）表示迷宫状态，1表示墙（迷宫四周都为墙），0表示通路。２表示路径经过。用一个flag标志位表示是否已经找到出口。寻路的基本过程：通过每次探寻四个方向，如按照向右－－》向下－－》向左－－》向上的次序依次探寻是否是通路，当四周均无法通过时，回退到上一步探索下一方向的出路。inta[12][12]={

{1,1,1,1,1,1,1,1,1,1,1,1},

{1,0,0,0,0,0,0,0,0,0,0,1},{1,0,1,1,1,1,1,1,1,0,1,1},{1,0,1,0,0,0,0,0,0,0,1,1},{1,0,1,0,1,0,1,0,1,0,1,1},{1,0,1,0,1,0,1,0,1,0,0,1},{1,0,1,0,1,0,1,0,1,0,0,1},{1,0,1,0,1,0,1,0,1,1,1,1},{1,0,1,0,1,0,1,0,1,1,0,1},{1,0,1,0,1,0,1,1,1,1,0,1},{1,0,0,0,1,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1,1}};迷宫寻路的递归算法如下：go(intx,inty){将（x,y)点设置为２if

(找到出口)

设置标志（表示已经找到出口）return找到的标志elseif(未找到出口并且右方为通路）go(x,y+1)if(未找到出口并且下方为通路）go(x+1,y) if(未找到出口并且左方为通路）go(x,y-1) if(未找到出口并且上方为通路）go(x-1,y) 四个方向都已经不通时，回溯到上一步return未找到的标志}4.8编程指导—良好的编程习惯把大的问题分解多个用函数实现的子问题，，也是一种良好的编程习惯。一个函数的代码不宜过长，一般来说不超过一页较为合适。否则影响整个程序的可读性和可维护性。函数功能应该专注、单一。也就是说，一个函数只作一件事情，以表现高度的内聚性。一个函数通过形参与外界交换数据。形参的设计应满足充分且必要的原则。形参信息不足，函数无法完成工作。形参信息冗余，增加了调用函数的难度，增加了函数间的耦合度，影响了模块的独立性。设计高内聚、低耦合的函数，是一种良好的编程习惯。一个函数有且仅有一条return语句是一种良好的编程习惯。单一入口、单一出口的函数维护了模块的独立性。函数名应尽量采用动词加名词的形式，如标准库函数getchar（）、putchar（）isdigit（）等。标准库函数的命名同标准库函数的设计一样，是大家学习的典范。启用同名的形参与实参有助于程序的可读性。实参和形参分属于不同的函数，是两组不同的局部变量，但在程序中所起的作用或意义相同。在函数前说明函数功能的简短注释，可成为读程序的人理解代码的台阶。在文件中定义函数的次序没有统一严格的规定，可以先写main（）、后写其它函数；或先写其它函数、后写main（）。但函数原型放在要引入的头文件中，或放在文件的顶部，使程序的组成模块清楚、可见。全局长名+注释，局部短名+注释，按常规方式使用的局部变量可以采用极短的名字。例如i、j用作循环变量，p、q为指