六、函数 教学目标： 函数的概念、定义、调用和返回 带自定义函数的程序设计 递推算法 递归思想及算法实现 函数的参数传递方式 C语言程序设计

六、函数 6.1 函数概论 任务6.1 从键盘输入一个正整数a,编一个程序判断a是否为素数。 可以设计一个函数int checkPrime(int n)， 让该函数负责检查n是否为素数，如果是，返回1，否则返回0. 参考程序：程序6_1.cpp C语言程序设计

6.1 函数概论 6.1.1 函数的说明 在全局上，自定义函数应该在主函数之前有一个说明，目的是告诉系统在程序中要用到一个自定义函数，被主函数直接或间接调用。 说明的时候就要写清楚这个函数的数据类型是什么，自变量有几个，都是什么数据类型。如任务6.1的函数 int ckeckPrim(int n); 说明自变量只有一个，是整型，函数的数值也是整型。函数的取值称为函数的返回值。这里用1表示真，0表示假。 C语言程序设计

6.1.2 函数的定义方法 类型标志符：表明函数返回值的类型。如果省略，系统则认为是int型的。 函数名：命名规则同变量名。用于调用该函数。 由类型标识符、函数名和形参列表组成的部分称为函数的首部。 类型标志符 函数名(形参列表) { 参数定义 语句组 } 形参列表：定义要传值的局部变量，保存调用该函数时的输入信息。形参多于一个时，用逗号分隔。没有形参时，括号不能省略。形参列表的方式如下： 类型标志符 参数名1，类型标志符 参数名2， …… 函数体：该函数功能具体的实现过程。通常包括若干变量的定义和若干语句。函数体由一对大括号和其中包括的语句组构成。参数定义指不传值的局部变量定义，大括号内可为空 C语言程序设计

6.1.2 函数的定义：例 形参列表：有2个形参，分别是int型变量x和int型变量y。它们用于保存调用该函数时传递进来的输入信息。 函数名：为MaxInt。以后就使用这个名字调用该函数。 形参列表：有2个形参，分别是int型变量x和int型变量y。它们用于保存调用该函数时传递进来的输入信息。 类型标志符：此处为int，表明该函数的返回值类型是int型的。 int MaxInt(int x, int y) { int z; z = x > y ? x : y; return(z); } 函数体：实现该函数的功能。对由调用者传递进来保存在形参中的数据进行有关处理后，将结果通过return语句返回给调用者。 C语言程序设计

6.1.3 函数的返回值 函数一般是由主函数调用（当然也可由别的函数或这个函数自已来调用），调用函数的目的是让它计算某一函数的值，这个值通过return语句返回给调用它的函数，格式为 return(表达式); 或 return 表达式; 如果不需返回数值，则用 return; 有调用就要有返回，函数中一定要有return出现，注意养成这个好习惯。 C语言程序设计

6.1.4 函数的调用 函数一经定义，以其名为标记的一片内存地址就被该函数所占有。在这片地址中存储着相关的一系列指令。因此在程序中出现该函数名，就意味着程序转到这一片内存地址，调用这个函数，执行了相关的一系列程序指令。 C语言程序设计

6.1.4 函数的调用 函数的调用方式 （1）对于有返回值的函数，可视其为表达式，可放在任何可放的地方。比如任务6.1中的checkPrime函数就放在if语句的表达式中。 （2）对于没有返回值的函数，一般在程序中作为独立一条语句出现，不以表达式形式出现。 如return(a); C语言程序设计

? 6.1.4 函数的调用 函数调用的一般形式为：函数名(实参列表); 如果是无参函数，则没有实参列表，但是括号不能省略； 如果实参多于一个，则用逗号分隔。 调用一个函数时，一定要保证实参和形参的一致，即在参数数量、类型和顺序上都要一致。 调用一个函数时，要发生由实参到形参的“单向值传递”的参数传递过程。 ? 为什么用函数名就可以调用一个函数 因为函数名中包含了该函数的入口地址信息，即函数名是一个指向函数入口地址的常量指针。 C语言程序设计

6.1.5 函数的参数 函数参数的作用 用于在调用某个函数时由调用者向该被调用函数传递信息。 对函数的进一步理解 可以把一个函数理解为一个“黑箱”，使用者使用该“黑箱”时，提供了加工的信息输入到“黑箱”中，该“黑箱”按照预先设计的功能对接收到的这些符合预定要求的输入信息进行加工，然后返回输出信息给使用者。 可见，要想形成一个函数，必须要设计好它可以接收什么样的输入信息，又输出什么样的信息，即必须设计好函数的接口。 函数 输入 信息 输出 信息 C语言程序设计

函数的形式参数 定义函数时出现在函数名后括号中的参数即是形式参数。 之所以称为形式参数，是因为在定义函数时这些参数并不具有具体的值，而只是代表某个数据类型的一个变量。 函数形参的作用 形参就是函数的输入接口：使用者在调用该函数时提供的输入信息被传递给相应的形式参数，然后函数按照预先设计的程序对形参进行处理，实际上就是对传递进来的数据进行处理。 在函数未被调用时，系统不对形参分配内存单元。在函数调用时，系统立刻给形参分配内存单元；调用结束后，再释放形式参数所占的内存单元。因此形式参数属于局部变量，其作用域限定在它所在的函数体内 编写一个函数时很重要一个工作就是要确定形参（数量、类型、意义、作用）。 C语言程序设计

函数的实际参数 调用函数时出现在函数名后括号中的参数即是实际参数。 之所以称为实际参数，是因为在调用函数时这些参数必须具有实际的值，才能用于去调用函数。实参可以使常量、变量或表达式。 实际参数是一个具有确定值的表达式。函数调用时，要将实际参数赋给形式参数。 调用函数时给出的实参必须和形参一致 实参必须和形参在数量、顺序、类型上一致才能正确调用。 C语言程序设计

函数的参数：例 int func(int x, int y, char op) { int z; switch(op) case '+' : z = x + y; break; case '-' : z = x - y; break; case '*' : z = x * y; break; case '/' : z = x / y; break; } return(z); 定义函数时的参数是形式参数。 调用函数时的参数是实际参数。 result = func(3, 5, '*'); C语言程序设计

6.1.6 函数的调用和返回 函数调用的内部过程是： 出现函数调用时，主调函数的执行过程暂时停止，在进行了 必要的“现场”保存工作后，转去执行被调用函数的代码，待 被调用函数执行完毕返回后，首先恢复刚才保存的“现场”， 然后继续主调函数的执行。 主调函数 被调函数 函数调用 被调函数开始 被调函数结束 (传递参数) (返回函数值) C语言程序设计

任务6.1的调用过程 C语言程序设计

函数原型声明的方法和位置 函数原型声明的方法 函数返回值类型 函数名 (形参列表) ; 形参列表可以只是形参类型列表，不指出形参的名字 函数返回值类型 函数名 (形参列表) ; 形参列表可以只是形参类型列表，不指出形参的名字 函数原型声明的位置： 放在所有函数外面，源程序文件开头的地方。 优点：凡是在该声明之后定义的函数，无需再进行函数原 型声明即可调用该函数。 C语言程序设计

函数原型声明：例 int func(int x, int y, char op) ; int main() 注意：有分号 { int a = 3, b = 5, result; …… result = func(a, b, '*' ); } 注意：有分号 在所有函数之外，源程序文件开头进行函数原型声明。 Int func(int x, int y, char op) { … … } 注意：没有分号 C语言程序设计

6.2 递推 递推是计算机数值计算中的一个重要算法。思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复计算的特点。 任务6.3 A,B,C,D,E合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边的树丛中找地方睡着了。日上三竿，A第一个醒来，他将鱼平分成5份，把多余的一条扔回湖中，拿自己的一份回家去了；B第二个醒来，也将鱼平分为5份，扔掉多余的一条，只拿走自己的一份；接着C,D,E依次醒来，也都按同样的办法分鱼。问5人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？ C语言程序设计

任务6.3 解题思路 假定A,B,C,D,E的编号为1,2,3,4,5，整数数组fish[k]表示第k个人所看到的鱼数。 显然： fisk[2]=(fish[1]-1)*4/5 fish[3]=(fish[2]-1)*4/5 fish[4]=(fish[3]-1)*4/5 fish[5]=(fish[4]-1)*4/5 即fish[i]=(fish[i-1]-1)*4/5,且fish[i-1]%5==1 或fish[i-1]=fish[i]*5/4+1,且fish[i]%4==0(i>1) C语言程序设计

任务6.3 解题思路(续) 按题意要求5人合伙捕鱼的最少鱼数，可以从小到大枚举。取fish[5]的值为6, 11, 16, 21，…依次计算fish[4], fish[3], fish[2], fish[1]的值，并比较其是否满足fish[i+1]%4==0(i=4,3,2,1)， 如果某次计算不能满足，则退出本次循环，继续从下一个fish[5]开始进行计算，如果所有的fish[i]均满足条件，则退出循环，得到结果。 程序：6_4.cpp C语言程序设计

任务6.3 的程序框图(NS图) C语言程序设计

6.2.1 递推数列的定义 一个数列从某一项起，它的任何一项都可以用它前面的若干项来确定，这样的数列称为递推数列，表示某项与其前面的若干项的关系就称为递推公式。 如1!,2!,3!,…,n!就是一个递推数列，其递推公式为:设fact(n)表示n! fact(n)=n*fact(n-1) （通项公式） fact(0)=1 （边界条件） C语言程序设计

6.2.2 递推算法的程序实现 有了通项公式和边界条件后，采用循环结构，从边界条件出发，利用通项公式通过若干步递推过程就可以求出解来。 例：编写一个程序int fact(int n)，用于计算n!的值。 int fact(int n) { int i, prod=1; //通过边界条件赋初值 for(i=1;i<=n;i++) prod = prod*i;//通项公式 return prod; } C语言程序设计

6.3 递归及其实现 递归算法在可计算性理论中占有重要地位，是算法设计的有力工具，对于拓展编程思路非常有用。 任务6.5 用递归算法求n!。 算法思路： 定义函数int fact(int n) fact(n)=n! fact(n-1)=(n-1)! 则有fact(n)=n*fact(n-1) 通项公式 已知fact(1)=1 边界条件 C语言程序设计

任务6.5 算法思路(续) (1)或结点 结点依不同的条件会有不同的取值。 C语言程序设计

任务6.5 算法思路(续) (2)与结点 A的最终取值为C的值，但为了求C的值，得先求出B的值，C是B的函数 C语言程序设计

任务6.5 C语言程序设计

任务6.5 C语言程序设计

任务6.5 求n!的递归函数 int fact(int n) { if(n>1) return n*fact(n-1); else } C语言程序设计

下面画出了调用和返回的递归示意图 C语言程序设计

C语言程序设计

任务6.5 C语言程序设计

任务6.5 使用递推求n! fact(1)=1 初始条件 fact(2)=2*fact(1)=2 fact(3)=3*fact(2)=6 int fact(int n) { int prod=1,i; for(i=1;i<=n;i++) prod=prod*i; return prod; } C语言程序设计

递推与递归的比较 递推的过程相当于从菜心推到外层，其出发点放在初始条件上。 递归的出发点放在求解的目标上，逐步调用本身，直到递归的边界条件为止。 当问题不能或不容易找到递推关系时，使用递归更符合人的思维方式，逻辑性强，函数的可读性好，易于理解。 C语言程序设计

6.3 递归及其实现 例6.1 汉诺塔问题：相传在古代印度的一座神庙中，有位僧人整天把3根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得摆在小盘上面，如下图。 C语言程序设计

汉诺塔问题 算法思路：从最简单的情况分析起 （1）在A柱上只有一只盘子，见下图，假定盘号为1，这时只需将该盘从A直接搬到C，一次完成，记为move 1 from A to C C语言程序设计

汉诺塔问题 算法思路（续） （2）在A柱上只有两只盘子时， 将1号盘从A移至B，这是为了让2号盘能移动，记为“将1从A移至B” 将2号盘从A移至C， “将2从A移至C” 将1号盘从B移至C， “将1从B移至C” C语言程序设计

汉诺塔问题 算法思路（续） （3）在A柱上有三只盘子时， 将盘1，2视为一个整体，移到B，记为move(2,A,C,B)，意思是将上面的两个盘子作为整体从A借助C移到B 将3号盘从A移至C，即“将3从A移至C” 将1，2作为一个整体，从B移到C，记为move(2,B,A,C)，意思是将上面的两个盘子作为整体，从B借助A移到C C语言程序设计

汉诺塔问题 C语言程序设计

汉诺塔问题 （4）在将1、2号盘从A移至B的过程中，move(2,A,C,B)可分为如下3步： 将1从A移至C 将2从A移至B move(2,B,A,C）可分为如下3步： 将1从B移至A 将2从B移至C C语言程序设计

汉诺塔问题 （5）将n次盘子从A移到C，可分为三步： 将1,2,3…n-1作为一个整体从A借助C移到B 将n从A移到C 将1,2,3…n-1作为一个整体从B借助A移到C 即 move(n,A,B,C)中需作如下操作： move(n-1,A,C,B) 将n从A移至C move(n-1,B,A,C) C语言程序设计

汉诺塔问题 （6）定义函数move(n,A,B,C)，用于将前n号盘子从A借助B移到C，由上面的分析知，搬移过程如下： C语言程序设计

汉诺塔问题 （7）3个盘子的递归与或图 这个图很象一颗倒置着的树，结点move(3, A, B, C)是树根，与结点是树的分枝，叶子都是直接可解结点。 C语言程序设计

汉诺塔问题 函数实现(程序6_6.cpp) C语言程序设计

汉诺塔问题 C语言程序设计

汉诺塔问题 下面来看看移动n只盘子的总移动次数 设S(n)为移动n只盘子所需的移动次数，则 S(n)=2*S(n-1)+1 S(1)=1 由归纳法可得： S(n)=2n-1。 如果n=64，则S(n)=2^64-1>1019 如果僧人一秒移动一只盘子，则需5800亿年。 C语言程序设计

6.4 指针与函数 指针与函数关系密切。在函数中可以使用指针作为函数的参数，也可以定义函数返回值是指针类型，即函数返回一个内存地址，还可以定义指针指向函数。总之，很灵活，很有用。 C语言程序设计

指针变量的用途为存储地址值，可以表示动态分配的构造型数据，处理字符串,等等，其中一个用途是做函数的参数。 6.4.1 指向变量的指针变量做函数参数 ? 为什么要引入指针变量？指针变量的用途到底是什么？ 指针变量的用途为存储地址值，可以表示动态分配的构造型数据，处理字符串,等等，其中一个用途是做函数的参数。 回忆一下： 以前的函数，都是用普通变量做形参和实参。由于函数调用时参数的传递过程是由“实参→形参”的“单向值传递”，函数接收到的只是实参的值（准确的说，是实参的拷贝），所以在函数中我们无法改变实参的值。 但是： 如果我们能把要修改的变量的地址传给函数，而函数又能接收到这个地址，那么在函数中，我们就可以改变这个地址所指向的单元，而这个单元实际上就是要修改的变量的单元，那么就达到了修改该变量的目的。 C语言程序设计

指针变量做函数参数：6_8.cpp #include <iostream> using namespace std; 用指针变量作形参 #include <iostream> using namespace std; void swap(int *p1, int *p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } int main( ) { int a, b; int *pa, *pb; a = 100; b = 200; pa = &a; pb = &b; cout<<"a="<<*pa<<", b="<<*pb<<endl; swap(pa, pb); cout<<"a="<<a<<", b="<<b<<endl; return 0; 交换两个形参指针变量所指向的内存单元的值 也可以直接用变量的地址作实参，即： Swap(&a, &b); 用指针变量作实参 C语言程序设计

指针变量做函数参数的执行过程 &a pa a 100 &b pb 200 b 200 100 &a p1 &b p2 &a pa a 200 调用函数之前： 200 100 &a p1 &b p2 调用函数开始： pa和pb分别单向值传递给p1和p2 然后交换p1和p2所指向的内存单元(实际上就是a和b)的值 调用函数返回： p1和p2释放单元，但a和b的值已交换 &a pa a 200 &b pb 100 b C语言程序设计

指针变量做函数参数：例 #include <iostream> using namespace std; void swap(int *, int *); int main( ) { int a, b; int *pa, *pb; a = 100; b = 200; pa = &a; pb = &b; cout<<"a="<<*pa<<", b=" <<*pb<<"\n"; swap(pa, pb); cout<<"a="<<a<<", b="<<b<<"\n"; return 0; } void swap(int *p1, int *p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; 可见，用指针变量作函数的参数可以达到在某个函数中改变其它函数中的变量值的目的。 实现方法就是：把要改变的变量的地址传递给该函数。 C语言程序设计

错误的Swap函数 用普通变量作实参 用普通变量作形参 交换两个形参变量的值 #include <iostream> using namespace std; void swap(int, int); int main( ) { int a =100, b = 200 cout<<"a="<<a<<", b="<<b<<endl; swap(a, b); return 0; } void swap(int p1, int p2) { int temp; temp = p1; p1 = p2; p2 = temp; 用普通变量作实参 用普通变量作形参 交换两个形参变量的值 C语言程序设计

错误的Swap函数的执行过程 100 a 200 b 100 p1 200 p2 200 100 a 100 200 b 调用函数之前： 调用函数开始： a和b分别单向值传递给p1和p2 200 100 然后交换两个形参变量p1和p2的值 调用函数返回： p1和p2释放单元，但a和b的值却没有变化，因为形参不会把值传回给实参。 a 100 200 b C语言程序设计

6.4.2 函数返回指针 例3：程序6_9.cpp 程序说明： （1）在函数名max前加*号，表明该函数的返回值为指针，该指针所指向的地址中的变量类型为double， （2）函数的形式参数p,q均为指向double型变量的指针 （3）在函数体中定义了一个指针变量r，也是指向double型的指针 C语言程序设计

6.4.2 函数返回指针 （4）在主函数中定义x,y为double型变量,还定义了一个指向double型的指针，用于存储函数的返回 （5）主函数中最关键的语句是 s=max(&x,&y) 它将x和y的地址赋给形式参数p和q 并将max返回的最大数的地址赋给s C语言程序设计

6.4.2 函数返回指针 （6）假如从键盘输入x=3.1416，y=2.7182，子函数max(*p,*q)被调用后，指向关系如下： C语言程序设计

6.4.2 函数返回指针 （7）子函数中的return r;是将指针r作为max函数的返回值，再赋给s （8）输出两数中的大数*s C语言程序设计

6.4.3 几种参数传递方式的比较 下面这部分内容是让同学自己练习读程序的。教学目标是能掌握参数传递方式有什么不同。 重点放在： （1）主函数用什么样的实参调用子函数 （2）子函数中的形参是什么 （3）子函数执行之后的结果能否影响主函数变量，为什么 C语言程序设计

1. 传地址，修改指针指向的值 void swap1(int *p,int *q) { int temp; temp = *p; *p = *q; *q = temp; cout<<"子函数中：*p="<<*p <<",*q="<<*q<<endl; } 调用语句：swap1(&a, &b); C语言程序设计

2. 传值 void swap2(int x,int y) { int temp; temp = x; x = y; y = temp; cout<<"子函数中：x="<<x <<",y="<<y<<endl; } 调用语句：swap2(a, b); C语言程序设计

3. 传地址，修改指针 void swap3(int *p,int *q) { int *temp; temp = p; p = q; q = temp; cout<<"子函数中：*p="<<*p <<",*q="<<*q<<endl; } 调用语句：swap3(&a, &b); C语言程序设计

6.5 程序举例 例5：用直接插入排序法对多个整数按从小到大的顺序排序。 此例我们在第四章中已经做过，现在我们用函数对直接排序算法进行封装，以方便使用。 本例，我们使用数组存储元素，以下标i处的数组元素存储第i个元素。 6_11.cpp C语言程序设计

6.6 小结 （1）使用函数可使程序模块化，每个函数完成一个确定的独立任务，使程序结构清晰、易读、易于修改和维护。 （2）主函数调用函数的目的，是让函数完成计算任务，或完成某种操作。如为前者，就需要返回值；如为后者，不需返回数据，但最好有所交待。有调用就要有返回，在函数末尾写一个return语句，是一个好习惯。 C语言程序设计

6.6 小结 （3）函数中的形式参数属于局部变量，作用域限定在函数体内。实际参数是具有确定值的表达式，在调用函数时，实际参数的值将被赋给形参变量。实际参数的个数和类型必须与形式参数一致，而且前后一一对应。 （4）递推算法的关键是用数学公式寻找一个递推公式，包括写成函数形式的通项公式和边界条件，之后用循环结构加以实现。 C语言程序设计

6.6 小结 （5）递归函数是可以直接调用自己或通过别的函数间接调用自己的函数。从思路上，递归函数将问题分解为两个概念性的部分A和B，其中A是能够直接处理的部分，B是暂时不能处理的部分，但与原问题相似，且规模较小。由于B部分与原问题相似，就形成了“你中有我，我中有你”的特殊局面，一次次地调用，规模缩小，直至降到达到递归的边界，可直接求解为止，从而得到解答。 C语言程序设计