第8章第6节 §86函数的递归调用 概念 在函数调用过程中出现调用该函数本身。即:函数的自我调用。 如 int f(int x) int fl(int int f2 (intt) Rint y, z; Rint y, z; Rint a, c; f(y); Z2(y) fl(y return(z) return(z; return(c); 直接调用 间接调用 在实际应用中,函数的递归调用解决的主要问题 1己知:[前一项(-1)与后一项()的某种关系 边界条件(如:初始条件,始止条件等) 2.求:其中某一项的值
第8章第6节 §8.6 函数的递归调用 一.概念 在函数调用过程中,出现调用该函数本身。即：函数的自我调用。 如： int f(int x) {int y,z; ...... z=f(y); ...... return(z); } int f1(int x) {int y,z; ...... z=f2(y) ...... return(z); } int f2(int t) {int a,c; ...... z=f1(y) ...... return(c); } 直接调用 间接调用 在实际应用中,函数的递归调用解决的主要问题 1.己知: 前一项(n-1)与后一项(n)的某种关系 边界条件（如：初始条件，始止条件等） 2 . 求: 其中某一项的值
第8章第6节 例:有一组数,其中A5比A4大2,A4比AB3大2,……2比A1大2, A[=-10,求A5 解: 各项的关系:A5|=A4+2,A4=A3]+2,…A|2|=A+2 边界条件:A[1=10 递推公式A∫10 n A[n-1]+2 求解过程 两个阶段:1.“回推”2.“递推” A|5] A[5 A4+×A4 18 A[4 A|3+2 A|3 AB316 A[2l+2 14 回推 A[2] A[2 递推(回代) A[1]+2 12 A[I=10
第8章第6节 例： 有一组数，其中A[5]比A[4]大2， A[4]比A[3]大2，…... A[2]比A[1]大2， A[1]=10,求A[5]。 解： 各项的关系： A[5]=A[4]+2, A[4]=A[3]+2，…. A[2]=A[1]+2。 边界条件： A[1]=10 10 n=1 递推公式 A[n-1]+2 n>1 求解过程 两个阶段： 1. “回推” 2. “递推” A[4] A[3]+2 A[3] A[2]+2 A[5] A[4]+2 A[2] A[1]+2 A[1]=10 A[5] 18 A[3] 14 A[4] 16 A[2] 12 回推 递推(回代） A[n]=
第8章第6节 程序: int f(int n) fint c; if(n=1)c=10: 终止条件 else c=f(n-1)+2 函数自我调用 return c; inO fint f(int n) 函数声明(可省 printf(“ resulte Al!Sl=%d”,f(5); 略) 函数调用
第8章第6节 程序 ： int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } main() {int f(int n); printf(“ resulte A[5]=%d”,f(5)); } 函数自我调用 终止条件 函数调用 函数声明(可省 略)
maind 上一题的分析 int f(int n); printf(" resulte A[5=%d, f(5);3 18 第一次调用 int f(int n if n )c=10; 注意:函数调用的次序。函数 ls f(n-1)+2; 调用完毕后,回到上一步的调 第二次调用m;}4|16 用点处。 f(i if(n=1)c=10 else c=f(n-1)+2; return 第三次调用 c;}3↑14 int f(int n) ir(m=+1)c=10 else c=f(n-1)+2; 第四次调用 return c; 12 int f(int h) 第五次调用 int if(m=+1)c=10 int f(int f(n-1)+2; Int c; return c;}1↑10 if(m=1)c=10; 第五次调用 Ise c=f(n-1)+2 return c;
main() 上一题的分析 {int f(int n); printf(“ resulte A[5]=%d”,f(5));} int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } 4 int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } 3 2 int f(int n) {int c; if (n==1) c=10; else c=f(n-1)+2; return c; } 1 1 10 10 12 14 16 18 5 注意: 函数调用的次序。函数 调用完毕后，回到上一步的调 用点处。 第一次调用 第二次调用 第三次调用 第四次调用 第五次调用 第五次调用
第8章第6节 六函数递归调用应注意的两点 1.函数自我调用 大多数问题可按这两点直接套用 2.终止条件 例4P120610猴子吃桃子的问题 解 桃子:15347663821909446221041 规律:前一天的桃子数=(后一天的桃子数+1)×2 程序:法一:用循环直接计算 maine Rint i, num=l for(i=10; il; i--) num=(num+1)*2 print(“num=%dm”,num);
大多数问题可按这两点直接套用 ****函数递归调用应注意的两点**** 1. 函数自我调用 2. 终止条件 例4 P120 6.10 猴子吃桃子的问题 解： 桃子： 1534 766 382 190 94 46 22 10 4 1 规律： 前一天的桃子数=(后一天的桃子数+1）×2 程序: 法一：用循环直接计算 main() {int i,num=1; for(i=10;i>1;i--) num=(num+1)*2; printf(“num=%d\n”,num); } 第8章第6节
法二:用函数的递归调用求解 第8章第6节 前一天的桃子数=(后一天的桃子数+1)×2 (1)=(x(2)+1)*2 X(2)=(x(3)+1)2 当n=10 2*(x(n+1)+1) x(9)=(x(10)+1)*2 程序 int x(int n) if(n=10)c=1; else c=2*(x(n+1)+1); return(c): 1 main( Rint b int x(int); 函数声明(可省略) 函数调用 printf(“ resulte=%dn”,b);
法二：用函数的递归调用求解 前一天的桃子数=(后一天的桃子数+1）×2 x(1)=(x(2)+1)*2 x(2)=(x(3)+1)*2 ..... x(9)=(x(10)+1)*2 1 x(n) =1 =2*(x(n+1)+1) 当n=10 int x(int n) {int c; if(n==10) c=1; else c=2*(x(n+1)+1); return(c);} main() {int b; int x(int); b=x(1); printf(“resulte=%d\n”,b); } 第8章第6节 函数声明(可省略) 函数调用 程序
第8章第6节 例:有计算式Cn=Cm1+Cm1 当m=0时 当n<2m时,可用下式简化Cn=Cn"用函数递归调用计算:C int c(int m, int n) if(m==0)res=1 else if(n<2* m)res=c(n-m, n); else res=c(m, n-1)+c(m-1, n-1); return(res); 1 mainO fint m, n, resulte int c(int, int); 函数声明(可省略) printf((“ input m,n(m<=a)=”); scanf(“%d,%d”,&m,&n) resulte=c(a, b) 函数调用 printf(“ resulte=%dn”, resulte)
例：有计算式 1 1 1 − = − + − m n m n m Cn C C 当m=0时 = 1 m Cn n m n m Cn C − 当n<2m时，可用下式简化 = 用函数递归调用计算： m Cn int c(int m, int n) {int res; if(m==0) res=1; else if(n<2*m) res=c(n-m,n); else res=c(m,n-1)+c(m-1,n-1); return(res); } main() {int m,n,resulte; int c(int , int); printf(“input m,n(m<=a)=”); scanf(“%d,%d”,&m,&n); resulte=c(a,b); printf(“resulte=%d\n”,resulte); } 第8章第6节 函数调用 函数声明(可省略)
第8章第7节 §87数组作为函数的参数 数组元素作为参数的参数与变量作为函数的参数相似 被调用函数中:形参用变量 主调函数中:实参—用数组元素 例810 int large( x int fint flag y)比较x printf(“ input array b:Ⅶm”); for(i=0;i<=9;i++) if(xy) flag=1 如xy结果:1:scan“%d”,&b) else if (x<y)nag=10:xsy结果:1 else flag =0 x=y结果:0for(i=0;<=9;i++) rerurn(flag); fif( large(ail,b[i)==1)n++;(大于的次数 else if( large(a[i,bi)=0m++;(等于的次数 main else k++; 1 (小于的次数 fint large(int, int); m0计*m(mm下m时Pm 的次数 if(n<k) printf(“ array a< array bIn”); printf((“ input array a:n”); if(m-9) printf(array a is equal for(i=0;i<-9;i++) array b)n”); scanf(“%d”,&a[i)
§8.7 数组作为函数的参数 第8章第7节 一. 数组元素作为参数的参数 ——与变量作为函数的参数相似 被调用函数中：形参——用变量 主调函数中： 实参——用数组元素 例8.10 int large(int x, int y) {int flag; if(x>y) flag=1; else if (xk) printf(“ array a>array b\n”); if (ny 结果: 1 如:x<y 结果: -1 x=y 结果: 0 统计:大于、 小于、等于 的次数 (大于的次数) (等于的次数) (小于的次数)
第8章第7节 二.数组名作为参数的参数 被调用函数中:形参 数组名 主调函数中: 实参 数组名 传值内容:传整个数组。即将数组中的所有元素,从主调函数传给被调用函数。 例81修改 读求一个数组前n个元素的平均值。 float average( float al, int m) main fint i; loat average( float a[l, int m);+函数声明 float aver sum=0.0 float score 10, ave; int in for(i=0;i<=m-1;i++) printf(inputarray aⅦn sum= l; for(i=0;i-=9;i+) aver-sum/m printf(score %d=,i return (aver); scanf(“%r”,& rscore);} printf(“ linput=” scanf(“%d”,&n); ave=average(score, n) 函数调用 printf(“ average=%7.3fn”,ave);
二. 数组名作为参数的参数 第8章第7节 被调用函数中: 形参 —— 数组名 主调函数中: 实参 —— 数组名 传值内容：传整个数组。即将数组中的所有元素，从主调函数传给被调用函数。 例8.11修改 **求一个数组前n个元素的平均值。 float average( float a[], int m) {int i; float aver,sum=0.0; for(i=0;i<=m-1;i++) sum=sum+a[i]; aver=sum/m; return(aver); } main() {float average(float a[],int m); float score[10],ave; int i,n; printf(“input array a\n”); for(i=0;i<=9;i++) {printf(“score[%d]=”,i); scanf(“%f”,&score[i]);} printf(“\ninput n=”); scanf(“%d”,&n); ave=average(score,n); printf(“average=%7.3f\n”,ave); } 函数声明 函数调用
1).主调函数和被调用函数中均定义数组,类型一致; 第8章第7节 2)元素个数,可以相同或不一致。 几点注意 要求:实参数组元素个数≥形参数组元素个数 3)形参数组可以不指定元素个数,以增加通用性; 4)传数值的方式传递地址。 传递地址 内存单元地址 数组名是数组的首地址(第一个元素在 内存所占单元的编号) score[9 a 高地址 ∴用数组名作函数参数,相当于: 实参数组首地址/传 形参数组首地址core2l 故:实参数组各个元素 scor 共占相同的 形参数组各个元素 内存单元 score a01低 首地址 地址 影响 结论:形参数组元素值的改变一实参数组元素值
第8章第7节 几点注意 1). 主调函数和被调用函数中均定义数组, 类型一致; 2).元素个数, 可以相同或不一致。 要求: 实参数组元素个数≥形参数组元素个数 3). 形参数组可以不指定元素个数, 以增加通用性; 4).传数值的方式———传递地址。 传递地址 ∵数组名是数组的首地址（第一个元素在 内存所占单元的编号） ∴用数组名作函数参数，相当于： 实参数组首地址 形参数组首地址 故： 传 实参数组各个元素 形参数组各个元素 1000 1001 1002 1003 1004 1005 1006 1007 ....... score[0] score[1] score[2] score[9] a[0] a[1] a[2] a[9] 低 地 址 高 地 址 内存单元地址 首地址 共占相同的 内存单元 结论：形参数组元素值的改变 实参数组元素值 影响