1、第六章第六章 函数、递推与递归函数、递推与递归函数的概念、定义、调用和返回函数的概念、定义、调用和返回带自定义函数的程序设计带自定义函数的程序设计递推算法递推算法递归思想及算法实现递归思想及算法实现内内 容容 要要 点点 为什么需要函数？为什么需要函数？满足实际应用需求满足实际应用需求6.1 函数函数 函数是组成函数是组成 C/C+程序的基础程序的基础 C/C+库中已经为用户提供了许多标准库函数库中已经为用户提供了许多标准库函数 用户可以根据自己的需要选用合适的库函数用户可以根据自己的需要选用合适的库函数 如果没有所需函数，用户可自己定义和编写一些函数如果没有所需函数，用户可自己定义和编写一些
2、函数函数概述函数概述 函数是模块化的基本单位函数是模块化的基本单位 主调函数与被调函数主调函数与被调函数 程序、源文件与函数关系程序、源文件与函数关系 程序中各模块关系程序中各模块关系mainfun1fun2fun3fun4fun5file1.cppmain()fun1()fun2()file2.cppfun3()fun4()fun5()program函数体取代函数声明尾部的函数体取代函数声明尾部的分号分号 要使用要使用C+函数，必须函数，必须完成如下工作：完成如下工作：提供函数定义提供函数定义 提供函数声明（原型）提供函数声明（原型）调用函数调用函数函数定义：函数定义：有返回值的函数有返回值
3、的函数 没有返回值的函数（没有返回值的函数（void函数）函数）void functionName(parameterList)/没有返回值没有返回值 return;/可选可选typeName functionName(parameterList)/有返回值有返回值 return value;【任务任务6.1】素数判定素数判定思路：思路：设计一个函数设计一个函数 int checkprime(int a)，负责检查负责检查 a 是否为素数：是否为素数：n 如果是素数，该函数返回如果是素数，该函数返回 1；n 否则，该函数返回否则，该函数返回 0。#include#include using n
4、amespace std;int main()int a=0;cout a;if(checkprime(a)/函数函数调用调用cout a 是素数是素数 endl;elsecout a 不是素数不是素数 endl;return 0;int checkprime(int n);/函数声明函数声明int checkprime(int n)/函数函数定义，定义，n为形式参数为形式参数 int k=0;for(k=2;k y)t=1;else t=-1;return t;函数定义示例：Compare函数;多条多条 return 语句语句int Compare(int x,int y)if(x=y)re
5、turn 0;else if(x y)return 1;else return-1;编写函数编写函数 Swap，互换两个整型数据，互换两个整型数据 x、y 的值的值void Swap(int x,int y)int t;t=x;x=y;y=t;return;/没有返回值只需直接写没有返回值只需直接写return语句语句函数定义示例：Swap 函数int IsDigit(char c)if(c=0&c=48&c=a&c=z)/az的的ASCII值为值为61H7AH /AZ的的ASCII值为值为41H5AH return c a+A;else return c;函数定义示例：TransformIn
6、toUpperCase 函数 编写函数编写函数 IsLeapYear，判断某个给定年份是否，判断某个给定年份是否为闰年为闰年int IsLeapYear(int year)return year%4=0&year%100!=0|year%400=0;函数定义示例：IsLeapYear 函数int mysqrt(int x)int i=1,sum=0,count=0;while(sum=x)sum+=i;count+;i+=2;return count-1;思考：思考：参数的有效性、合法性判断参数的有效性、合法性判断应应 放在函数里放在函数里?放在主程序里放在主程序里?int mysqrt(in
7、t x)int i=0;while(i*i=x)i+;return i-1;函数定义示例：我的平方根函数我的平方根函数int main()int times;char ch;coutch;while(ch!=q)couttimes;n_chars(ch,times);coutThe value of times is timesendl;coutch;cout0)coutc;coutn;double cube(double x);int main()double p,q;p=1.2;q=cube(p);coutp=pendl;cout实参实参p的地址是的地址是&pendl;coutq=qend
8、l;return 0;double cube(double x)coutx=xendl;cout形参形参x的地址是的地址是&xendl;return(x*x*x);例：例：例：互换两个整数例：互换两个整数输入：输入：10 20输出：输出：10 20 10 20 20 10 10 20 xymain()x1020ymain()main()x1020Swap()tempymain()x2010Swap()10tempyx1020ymain()函数调用栈框架函数调用栈框架:值传递与数据互换问题值传递与数据互换问题 值传递：值传递：值复制操作值复制操作 将将实际参数实际参数值复制给值复制给形式参数形式
9、参数 此过程单向不可逆此过程单向不可逆 复制完成后，复制完成后，形参形参与与实参实参没有任何关联没有任何关联 如何解决数据值互换问题？如何解决数据值互换问题？使用使用全局变量全局变量作为函数通信的手段作为函数通信的手段 使用指针传递变量的地址使用指针传递变量的地址int a,b;/*全局变量，保证所有函数都可以访问到全局变量，保证所有函数都可以访问到*/void Swap();/*不再需要函数参数不再需要函数参数 */输出：输出：10 20 10 20 20 1020 10【任务6.2】给歌手打分 定义int Max(int a,int b)函数，返回a,b中的大者 定义int Min(int
10、 a,int b)函数，返回a,b中的小者 定义整型变量p，用以保存 N个数中的最大值 定义整型变量q，用以保存 N个数中的最小值 定义一个整型变量 sum 做累加用 最终得分：(sum-p-q)/(N-2)#include#includeusing namespace std;int Max(int,int);int Min(int,int);int main()int p=0;int q=100;int sum=0，x=0;int i=1;for(i=1;i=10;i=i+1)cout“请第请第”i “位裁判给分位裁判给分”x;p=Max(x,p);q=Min(x,q);sum=sum+x
11、;cout“选手得分选手得分”b)return a;else return b;int Min(int c,int d)if (c d)return c;else return d;#include#includeusing namespace std;void print(int,int);/void print(int*,int);int main()const int n=5;int an;coutEnter matrix a:n;for(int i=0;iai;coutYou have entered the matrix a:n;print(a,n);return 0;void pr
12、int(int array,int size)/void print(int*array,int size)for(int k=0;k=size-1;k+)coutsetw(10)arraykendl;问题：一维数组作为参数问题：一维数组作为参数void bubble(int,int);int main()int a10;bubble(a,10);return 0;void bubble(int array,int size)for(int j=1;jsize;j+)for(int i=0;isize-j;i+)if(arrayiarrayi+1)int p=arrayi;arrayi=arr
13、ayi+1;arrayi+1=p;冒泡排序：冒泡排序：#include#includeusing namespace std;void print(int4,int);int main()const int n=5;int an4;coutEnter matrix a:n;for(int i=0;in;i+)for(int j=0;jaij;coutYou have entered the matrix a:n;print(a,n);return 0;void print(int array4,int xsize)for(int i=0;i=xsize-1;i+)for(int j=0;j4;
14、j+)coutsetw(10)arrayij;cout=1);fish5=fish5+5;/.1 for(i=4;i=1;i-)/.2 fishi+1%4!=0 true false break;/退出 for 循环 fishi=fishi+1*5/4+1;【任务6.3】的程序框图 int main()int fish6=1,1,1,1,1,1;/记录每人醒来后看到的鱼数 int i=0;do fish5=fish5+5;/让让E看到的鱼数增看到的鱼数增5 for(i=4;i=1;i-)if(fishi+1%4!=0)break;/跳出跳出for循环循环else fishi=fishi+1*5
15、/4+1;/计算第计算第i人看到的鱼数人看到的鱼数 while(i=1);for(i=1;i=5;i+)cout fishi endl;return 0;int main()int n=100,i=0;int q101;q0=1;for(i=1;i=n;i=i+1)qi=qi-1+i;cout“切100刀后最多可得”qn块1n=1Dfact(n-1)En*fact(n-1)直接可解结点C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=61=1131Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE21例如：求 3!的与或图求 3!的递归调用与返回
16、 Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1调用调用调用调用 31 fact(3)真真 假假 调调用用 fact(2)计计算算 3*fact(2)fact(2)fact(1)21 真真 假假 调调用用 fact(1)计计算算 2*fact(1)11 真真 假假 fact(1)1 返返回回 返返回回 求 3!的程序框图1 fact(3)真真 假假 3=1 调调用用 fact(2)真真 假假 假假 真真 2
17、=1 1=1 fact(2)=2*fact(1)返返回回 fact(3)=3*fact(2)返返回回 调调用用 fact(1)fact(1)=1 返返回回 求 3!的程序框图2unsigned long fact(unsigned int);int main()int n=0;coutn;coutn的阶乘为fact(n)endl;return 0;unsigned long fact(unsigned int n)unsigned long result;if(n=1)result=1;elseresult=n*fact(n-1);return result;【任务任务6.5】求求n!3nma
18、inmain 函数栈框架函数栈框架函数调用栈框架函数调用栈框架mainfact第一次以第一次以 3 为参数调用为参数调用 fact，进入函数时，进入函数时3nresultmainfact第二次以第二次以 2 为参数调用为参数调用 fact，进入函数时，进入函数时fact2nresultmainfact第三次以第三次以 1 为参数调用为参数调用 fact，进入函数时，进入函数时factfact1nresultmainfact第三次以第三次以 1 为参数调用为参数调用 fact，退出函数前，退出函数前factfact11nresultmainfact第二次以第二次以 2 为参数调用为参数调用 fa
19、ct，退出函数前，退出函数前fact22nresultmainfact第一次以第一次以 3 为参数调用为参数调用 fact，退出函数前，退出函数前36nresult3nmain递归调用结束后的递归调用结束后的 main 函数栈框架函数栈框架递归与递推的比较（以求 n!为例）递推：递推：从已知的初始条件出发，逐次去求所需要的从已知的初始条件出发，逐次去求所需要的 阶乘值。阶乘值。fact(1)=1fact(2)=2*fact(1)=2fact(3)=3*fact(2)=6 递归：递归：出发点不在初始条件上，而在出发点不在初始条件上，而在求解目标求解目标上。上。从所求的未知项出发，从所求的未知项出
20、发，逐次调用自身逐次调用自身，直到，直到 递归的边界（初始条件）。递归的边界（初始条件）。递归算法比较符合人的思维方式，逻辑性强，递归算法比较符合人的思维方式，逻辑性强，易于理解。易于理解。递归递归与与递推的相似之处：递推的相似之处：都基于控制结构，均涉及循环都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 理论上，能用递归解决的问题也能用递推解决。计算计算 x n算法举例算法举例(1)求两个正整数的最大公约数求两
21、个正整数的最大公约数算法举例算法举例(2)unsigned int gcd(unsigned int x,unsigned int y)unsigned int t;t=x y?x:y;while(x%t!=0|y%t!=0)t-;return t;穷举法穷举法欧氏算法欧氏算法步骤 1：x 整除以 y，记余数为 r步骤 2：若 r 为 0，则最大公约数即为 y，算法结束步骤 3：否则将 y 作为新 x，将 r 作为新 y，重复上述步骤unsigned int gcd(unsigned int x,unsigned int y)unsigned int r;while(1)r=x%y;if(r=
22、0)return y;x=y;y=r;求两个正整数的最大公约数求两个正整数的最大公约数 unsigned int gcd(unsigned int x,unsigned int y)while(y!=0)unsigned int r=x%y;x=y;y=r;return x;unsigned int gcd(unsigned int x,unsigned int y)if(x%y=0)return y;return gcd(y,x%y);递归算法递归算法 求两个正整数的最大公约数求两个正整数的最大公约数1,1,2,3,5,8,13,21,fibonacci(1)=1 fibonacci(2)=
23、1 fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)求求Fibonacci数的递归程序具有指数复杂性。数的递归程序具有指数复杂性。求求Fibonacci数数算法举例算法举例(3)unsigned long GetFibonacci(unsigned int n)if(n=2|n=1)return 1;else return GetFibonacci(n-1)+GetFibonacci(n-2);unsigned long GetFibonacci(unsigned int n)unsigned long result,i,f1,f2;if(n=2|n=1)r
24、eturn 1;f2=1;f1=1;for(i=3;i=n;i+)result=f1+f2;f1=f2;f2=result;return result;非递归程序非递归程序几个问题的递归思想几个问题的递归思想：求数组求数组an中各元素的和中各元素的和求数组求数组an中各元素的最大中各元素的最大(最小最小)值值给数组给数组an 排序排序求一个自然数的各位数字之和求一个自然数的各位数字之和下楼问题下楼问题跳马问题跳马问题八皇后问题八皇后问题递归信任递归信任 理解递归问题的原则理解递归问题的原则 不分析复杂细节而仅考虑单一层次上的操作不分析复杂细节而仅考虑单一层次上的操作 不必跟踪递归调用的堆栈框架
25、不必跟踪递归调用的堆栈框架 基本递归假设基本递归假设 只要只要递归调用时的参数比原始参数在某种程度上更简单递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案则递归调用就一定能获得正确答案 递归心理学：这种简单递归调用一定正确工作的假设即为递归心理学：这种简单递归调用一定正确工作的假设即为递归信任递归信任 递归实现是否检查了最简单情形递归实现是否检查了最简单情形 在尝试将问题分解成子问题前，首先应检查问题是否已足够简单 在大多数情况下，递归函数以 if 开头 如果程序不是这样，仔细检查源程序 是否解决了最简单情形是否解决了最简单情形 大量递归错误是由没有正确解决最简单情形导致的 最简单情形不能调用递归 递归分解是否使问题更简单递归分解是否使问题更简单 只有分解出的子问题更简单，递归才能正确工作，否则将形成无限递归，算法无法终止 问题简化过程是否能够确实回归最简单情形，还问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况是遗漏了某些情况 子问题是否与原始问题完全一致子问题是否与原始问题完全一致 如果递归过程改变了问题实质，则整个过程肯定会得到错误结果 子问题的解是否正确组装为原始问题的解子问题的解是否正确组装为原始问题的解 将子问题的解正确组装以形成原始问题的解也是必不可少的步骤
