第六章函数、递推与递归第六章函数、递推与递归清华大学清华大学函数的概念、定义、调用和返回函数的概念、定义、调用和返回带自定义函数的程序设计带自定义函数的程序设计递推算法递推算法递归思想及算法实现递归思想及算法实现内内 容容 要要 点点 为什么需要函数？为什么需要函数？ 满足实际应用需求满足实际应用需求6.1 函数函数 函数是组成函数是组成 C/C+ 程序的基础程序的基础 C/C+ 库中已经为用户提供了许多标准库函数库中已经为用户提供了许多标准库函数 用户可以根据自己的需要选用合适的库函数用户可以根据自己的需要选用合适的库函数 如果没有所需函数，用户可自己定义和编写一些函数如果没有所需函数，用户可自己定义和编写一些函数函数概述函数概述函数是模块化的基本单位函数是模块化的基本单位主调函数与被调函数主调函数与被调函数程序、源文件与函数关系程序、源文件与函数关系程序中各模块关系程序中各模块关系file1.cppmain()fun1()fun2()file2.cppfun3()fun4()fun5()programint int mainmain() () int int a a, , b b, , sumsum; ; sumsum = = AddAdd( ( a a, , b b ); ); / / 函数调用函数调用函数调用函数调用 int int AddAdd( int ( int x x, int , int y y ) ) ; ; / / 函数声明函数声明函数声明函数声明int int AddAdd( int ( int x x, int , int y y ) ) / / 函数定义函数定义函数定义函数定义 / / 函数体取代函数声明尾部的函数体取代函数声明尾部的分号分号 要使用要使用C+函数，必须函数，必须完成如下工作：完成如下工作： 提供函数定义提供函数定义 提供函数声明（原型）提供函数声明（原型） 调用函数调用函数函数定义：函数定义：有返回值的函数有返回值的函数 没有返回值的函数（没有返回值的函数（void函数）函数）void functionName (parameterList) /没有返回值没有返回值 return; / 可选可选typeName functionName (parameterList) /有返回值有返回值 return value;【任务任务6.1】素数判定素数判定思路：思路：设计一个函数设计一个函数 int checkprime(int a) ， 负责检查负责检查 a 是否为素数：是否为素数：n 如果是素数，该函数返回如果是素数，该函数返回 1；n 否则，该函数返回否则，该函数返回 0。#include #include using namespace 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 = sqrt(n); k = k+1) if (n % k = 0) / 如果如果 n 能被能被k整除则返回整除则返回0 return 0; return 1; / n 不能被不能被k整除则返回整除则返回1有何问题？有何问题？函数原型函数原型 int checkprime(int n);n n提高算法效率提高算法效率n n只要在只要在只要在只要在 1 1 和和和和 n n 之间存在一个因子就可终止，并返回之间存在一个因子就可终止，并返回之间存在一个因子就可终止，并返回之间存在一个因子就可终止，并返回 n n 不不不不是素数是素数是素数是素数n n若若若若 n n 可被可被可被可被 2 2 整除，不需检验其它数，程序终止并返回整除，不需检验其它数，程序终止并返回整除，不需检验其它数，程序终止并返回整除，不需检验其它数，程序终止并返回 n n 不是素数；若否，则所有偶数都不是因子，程序只需检不是素数；若否，则所有偶数都不是因子，程序只需检不是素数；若否，则所有偶数都不是因子，程序只需检不是素数；若否，则所有偶数都不是因子，程序只需检验奇数验奇数验奇数验奇数n n程序不必检验因子一直到程序不必检验因子一直到程序不必检验因子一直到程序不必检验因子一直到 n n，只需到，只需到，只需到，只需到sqrtsqrt( (n n) )即可即可即可即可int int checkprime( int ( int n n ) ) int int i i; ; if( if( n n % 2% 2 = 0 )= 0 ) return 0; return 0; for( for( i i = 3; = 3; i i = = sqrtsqrt( (n n); ); i i += 2 )+= 2 ) if( if( n n % % i i = 0 )= 0 ) return 0; return 0; return 1; return 1; 问题问题问题问题1 1：本算法效率？：本算法效率？：本算法效率？：本算法效率？每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时问题问题问题问题2 2：本算法正确性？：本算法正确性？：本算法正确性？：本算法正确性？n n=1 =1 n n=2 =2 时结果错误时结果错误时结果错误时结果错误int int checkprime( int ( int n n ) ) int int limitlimit, , i i; ; limitlimit = = sqrtsqrt( (n n); ); if( if( n n % 2% 2 = 0 )= 0 ) return 0; return 0; for( for( i i = 3; = 3; i i = = limitlimit; ; i i += 2 )+= 2 ) if( if( n n % % i i = 0 )= 0 ) return 0; return 0; return 1; return 1; 问题：本算法正确性？问题：本算法正确性？问题：本算法正确性？问题：本算法正确性？ 浮点数的存储有误差，程序的正确性浮点数的存储有误差，程序的正确性浮点数的存储有误差，程序的正确性浮点数的存储有误差，程序的正确性依赖于机器的表示精度依赖于机器的表示精度依赖于机器的表示精度依赖于机器的表示精度int int checkprime( int ( int n n ) ) int int limitlimit, , i i; ; limitlimit = = sqrtsqrt( (n n) + 1;) + 1; if( if( n n % 2% 2 = 0 )= 0 ) return 0; return 0; for( for( i i = 3; = 3; i i = = limitlimit; ; i i += 2 )+= 2 ) if( if( n n % % i i = 0 )= 0 ) return 0; return 0; return 1; return 1; if( if( n =n y ) t = 1; else t = -1; return t;函数定义示例： Compare函数; 多条多条 return 语句语句int Compare( int x, int y ) if( x = y ) return 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;函数定义示例： TransformIntoUpperCase 函数编写函数编写函数 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(int 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=qendl; return 0;double cube(double x) coutx=xendl; cout形参形参x的地址是的地址是&xx; x; ciny; ciny; coutcoutx“ “yendl; (1)x“ “yendl; (1) SwapSwap( ( x x, , y y ); ); cout coutx“ “yendl; (4)x“ “yendl; (4) return 0; return 0; 例：互换两个整数例：互换两个整数void void SwapSwap( int ( int x x, int , int y y ) ) int int temptemp; ; cout coutx“ “yendl; (2)x“ “yendl; (2) temptemp = = x x; ; x x = = y y; ; y y = = temptemp; ; cout coutx“ “yendl; (3)x“ “ya; a; cinb; cinb; coutcouta a“ “ “b bendl; endl; SwapSwap();(); cout couta a“ “ “b bendl; endl; return 0; return 0; void void SwapSwap() () int int temptemp; ; cout couta a“ “ “b bendl; endl; temptemp = = a a; ; a a = = b b; ; b b = = temptemp; ; cout couta a“ “ “b bendl; endl; return; return; 输出：输出：10 20 10 20 20 1020 10【任务6.2】给歌手打分 定义int Max( int a,int b)函数，返回a,b中的大者 定义int Min( int 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 ; 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 print(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=arrayi+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;j+) coutsetw(10)arrayij;cout=1; i-) if ( fishi+1%4 != 0 ) break; / 跳出跳出for循环循环else fishi=fishi+1*5/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块endl; return 0;【任务任务6.4】王小二切饼王小二切饼 1 2 4 7 11切0刀 切1刀 切2刀 切3刀 切4刀 递推公式：递推公式： q(0) = 1 q(n) = q(n-1) + n5051 递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。6.3 递归及其实现递归及其实现递归的目的递归的目的简化复杂问题的手段： 将问题逐步化简（递简），在化简过程中保持原问题的性质不变保持原问题的性质不变，直到问题最简，可以轻易地获得答案；然后将简化问题的答案组装成原始问题的解（回归）递归示例递归示例n! = 1 2 3 n: n! = (n- -1)! n; 1! = 1xn = x x x x: xn = xn- -1 x; x0 = 1或结点或结点和和与结点：与结点：ABC条件 Z 条件 !ZABGZ1 Z2 ZnC条件为 Z1 , Z2 , , Zn A 取值为 B 或 C , 或 G或结点或结点 A 为与结点，A 的最终取值为C 结点的值，为了求得 C的值，先求出 B结点的值，C 是 B 的函数。ABCABDC与结点与结点 A 结点的值最终为 D 的值，为了求 D 需要先求 B 和 C。先求左边的点才能求最右边的点。例如：求 n ! 的与或图直接可解结点C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 6例如：求 3 ! 的与或图求 3! 的递归调用与返回 求 3! 的程序框图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!3nmainmain 函数栈框架函数栈框架函数调用栈框架函数调用栈框架mainfact第一次以第一次以 3 为参数调用为参数调用 fact，进入函数时，进入函数时3nresultmainfact第二次以第二次以 2 为参数调用为参数调用 fact，进入函数时，进入函数时fact2nresultmainfact第三次以第三次以 1 为参数调用为参数调用 fact，进入函数时，进入函数时factfact1nresultmainfact第三次以第三次以 1 为参数调用为参数调用 fact，退出函数前，退出函数前factfact11nresultmainfact第二次以第二次以 2 为参数调用为参数调用 fact，退出函数前，退出函数前fact22nresultmainfact第一次以第一次以 3 为参数调用为参数调用 fact，退出函数前，退出函数前36nresult3nmain递归调用结束后的递归调用结束后的 main 函数栈框架函数栈框架递归与递推的比较（以求 n! 为例）递推：递推：从已知的初始条件出发，逐次去求所需要的从已知的初始条件出发，逐次去求所需要的 阶乘值。阶乘值。 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6 递归：递归：出发点不在初始条件上，而在出发点不在初始条件上，而在求解目标求解目标上。上。 从所求的未知项出发，从所求的未知项出发，逐次调用自身逐次调用自身，直到，直到 递归的边界（初始条件）。递归的边界（初始条件）。 递归算法比较符合人的思维方式，逻辑性强，递归算法比较符合人的思维方式，逻辑性强， 易于理解。易于理解。递归递归与与递推的相似之处：递推的相似之处： 都基于控制结构，均涉及循环都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 理论上，能用递归解决的问题也能用递推解决。计算计算 x nlong double long double CalPower( long double x, int n )CalPower( long double x, int n ) long double result; long double result; if( n = 0 ) if( n = 0 ) result = 1; result = 1; else else result = x * result = x * CalPower( x, n 1 )CalPower( x, n 1 ) ; ; return result; return result; 算法举例算法举例(1)求两个正整数的最大公约数求两个正整数的最大公约数算法举例算法举例(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 = 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) = 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 ) return 1; f2 = 1; f1 = 1; for( i = 3; i = n; i+ ) result = f1 + f2;f1 = f2; f2 = result; return result; 非递归程序非递归程序几个问题的递归思想几个问题的递归思想：求数组求数组an中各元素的和中各元素的和求数组求数组an中各元素的最大中各元素的最大(最小最小)值值给数组给数组an 排序排序求一个自然数的各位数字之和求一个自然数的各位数字之和下楼问题下楼问题跳马问题跳马问题八皇后问题八皇后问题递归信任递归信任理解递归问题的原则理解递归问题的原则不分析复杂细节而仅考虑单一层次上的操作不分析复杂细节而仅考虑单一层次上的操作不必跟踪递归调用的堆栈框架不必跟踪递归调用的堆栈框架基本递归假设基本递归假设只要只要递归调用时的参数比原始参数在某种程度上更简单递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案则递归调用就一定能获得正确答案递归心理学：这种简单递归调用一定正确工作的假设即为递归心理学：这种简单递归调用一定正确工作的假设即为递归信任递归信任递归实现是否检查了最简单情形递归实现是否检查了最简单情形在尝试将问题分解成子问题前，首先应检查问题是否已足够简单在大多数情况下，递归函数以 if 开头如果程序不是这样，仔细检查源程序是否解决了最简单情形是否解决了最简单情形大量递归错误是由没有正确解决最简单情形导致的最简单情形不能调用递归递归分解是否使问题更简单递归分解是否使问题更简单只有分解出的子问题更简单，递归才能正确工作，否则将形成无限递归，算法无法终止问题简化过程是否能够确实回归最简单情形，还问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况是遗漏了某些情况子问题是否与原始问题完全一致子问题是否与原始问题完全一致如果递归过程改变了问题实质，则整个过程肯定会得到错误结果子问题的解是否正确组装为原始问题的解子问题的解是否正确组装为原始问题的解将子问题的解正确组装以形成原始问题的解也是必不可少的步骤