函数二省公共课一等奖全国赛课获奖课件.pptx

大连理工大学软件学院大连理工大学软件学院第七章第七章第1页本章关键点大连理工大学软件学院大连理工大学软件学院第2页main()调用调用fa()fa()调用调用fb()fb()void fb()void fa()fb();void main()fa();返回返回fa()返回返回main()7.函数嵌套调用定义定义 申明申明 调用？调用？大连理工大学软件学院大连理工大学软件学院第3页例1：输入4个整数，找出其中最大数。用函数嵌套调用来处理。（递推）7.函数嵌套调用#include void main()int max_4(int a,int b,int c,int d);/max_4函数申明函数申明 int a,b,c,d,max;printf(Please enter 4 interger numbers:);scanf(%d%d%d%d,&a,&b,&c,&d);max=max_4(a,b,c,d);/*调用调用max_4函数函数*/printf(max=%d n,max);大连理工大学软件学院大连理工大学软件学院第4页int max_4(int a,int b,int c,int d）int max_2(int,int);int m;m=max_2(a,b);m=max_2(m,c);m=max_2(m,d);return(m);int max_2(int a,int b)if(ab)return a;else return b;运行情况以下：运行情况以下：Please enter 4 interger numbers:11 45 54 0Please enter 4 interger numbers:11 45 54 0max=45max=45大连理工大学软件学院大连理工大学软件学院第5页例2：定义一个求 bin(n,k)函数。分析：分析：定义函数定义函数 fact(m)=m!bin(n,k)=fact(n)/(fact(k)*fact(n-k)由主函数输入数据由主函数输入数据 a、b，求，求 bin(a,b)7.函数嵌套调用大连理工大学软件学院大连理工大学软件学院第6页#includelong fact(int m)int i;long sum=1;for (i=1;i=m;i+)sum*=i;return sum;long bin(int n,int k)return long(fact(n)/(fact(k)*fact(n-k);void main()int a,b;long f1,f2;scanf(“%d%d”,&a,&b);f1=fact(a)/(fact(b)*fact(a-b);f2=bin(a,b);大连理工大学软件学院大连理工大学软件学院第7页/函数嵌套调用示例求组合函数嵌套调用示例求组合#includelong fact(int m)int i;long sum=1;for (i=1;i）例例4:4:递归求年纪递归求年纪大连理工大学软件学院大连理工大学软件学院第24页#include int age(int n)int c;if(n=1)c=10;elsec=age(n-1)+2;return c;void main()printf(%dn,age(5);运行结果以下：运行结果以下：18 递归形式递归形式递归终止条件递归终止条件基本情况基本情况修改递归条件修改递归条件递推法实现：递推法实现：void main()int i,sum=10;for(i=1;i=4;i+)sum=sum+2;printf(%dn,sum);大连理工大学软件学院大连理工大学软件学院第25页int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);递归形式递归形式递归终止条件递归终止条件基本情况基本情况修改递归条件修改递归条件 7.6 函数递归调用 例例5:5:递归求递归求n n阶乘阶乘大连理工大学软件学院大连理工大学软件学院第26页int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);k3F(k)Output 3!=?Output 3!=?n3F(3)3*F(2)3*F(2)n n2 2F(2)F(2)2*2*F(1)F(1)n1F(0)1计算计算 Factorial(3)=3!F(1)F(1)n01*1*F(0)F(0)7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第27页k3F(3)Output 3!=?Output 3!=?n3F(3)3*F(2)3*F(2)n n2 2F(2)F(2)2*2*F(1)F(1)n1F(0)1F(1)F(1)n01*1*F(0)F(0)1计算计算 Factorial(3)=3!int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第28页k3F(3)Output 3!=?Output 3!=?n3F(3)3*F(2)3*F(2)n n2 2F(2)F(2)2*2*F(1)F(1)n1F(1)F(1)计算计算 Factorial(3)=3!F(1)=1F(1)=11int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第29页k3F(3)Output 3!=?Output 3!=?n3F(3)3*F(2)3*F(2)n n2 2F(2)F(2)F(2)=2F(2)=22计算计算 Factorial(3)=3!int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第30页k3F(3)Output 3!=?Output 3!=?n3F(3)F(3)=6F(3)=6计算计算 Factorial(3)=3!int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第31页k3F(3)Output 3!=6Output 3!=63!=6计算计算 Factorial(3)=3!int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第32页k3F(3)k3F(3)n3F(3)3*F(2)3*F(2)n n2 2F(2)F(2)2*2*F(1)F(1)n1F(0)1F(1)F(1)n01*1*F(0)F(0)F(1)=1F(1)=1F(2)=2F(2)=2F(3)=6F(3)=6Output 3!=6Output 3!=6计算计算 Factorial(3)=3!int Factorial(int n)if (n=0)return 1;else return n*Factorial(n-1);7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第33页int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);7.6 函数递归调用 例例6:6:递归求斐波那契数列递归求斐波那契数列递归形式递归形式递归终止条件递归终止条件基本情况基本情况修改递归条件修改递归条件递归形式递归形式修改递归条件修改递归条件大连理工大学软件学院大连理工大学软件学院第34页int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);Fibonacci(5)Fibonacci(4)Fibonacci(3)Fibonacci(3)Fibonacci(2)Fibonacci(2)Fibonacci(1)大连理工大学软件学院大连理工大学软件学院第35页Fibonacci(5)Fibonacci(4)Fibonacci(3)Fibonacci(3)Fibonacci(2)Fibonacci(2)Fibonacci(1)11+2int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);大连理工大学软件学院大连理工大学软件学院第36页Fibonacci(5)Fibonacci(4)Fibonacci(3)2Fibonacci(3)Fibonacci(2)13int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);大连理工大学软件学院大连理工大学软件学院第37页Fibonacci(5)Fibonacci(3)3Fibonacci(3)Fibonacci(1)Fibonacci(2)112int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);大连理工大学软件学院大连理工大学软件学院第38页Fibonacci(5)Fibonacci(4)Fibonacci(3)Fibonacci(3)Fibonacci(2)Fibonacci(1)Fibonacci(2)Fibonacci(2)Fibonacci(1)532211111int Fibonacci(int n)if(n=2)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);大连理工大学软件学院大连理工大学软件学院第39页 7.6 函数递归调用 递推递推：知道第一个，推出下一个，直到抵达目标。：知道第一个，推出下一个，直到抵达目标。递归递归：要知道第一个，需要先知道下一个，直到一个已知：要知道第一个，需要先知道下一个，直到一个已知 ，再反回来，得到上一个，直到第一个。，再反回来，得到上一个，直到第一个。递推递推：从已知到未知，从简单到复杂。：从已知到未知，从简单到复杂。递归递归：从未知到已知，从复杂到简单。：从未知到已知，从复杂到简单。递推递推：直接自下向顶运算，由：直接自下向顶运算，由f(1)算到算到f(n)。递归递归：自顶向下逐步拓展需求，最终自下向顶运算。即由：自顶向下逐步拓展需求，最终自下向顶运算。即由f(n)拓展到拓展到f(1)，再由，再由f(1)逐步算回逐步算回f(n)。递归递归：在函数内调用函数本身。：在函数内调用函数本身。递推递推：往往经过循环迭代求值。：往往经过循环迭代求值。递归与递推（迭代）比较递归与递推（迭代）比较大连理工大学软件学院大连理工大学软件学院第40页递归与非递归比较递归与非递归比较递归目标是简化程序设计，使程序易读；递归目标是简化程序设计，使程序易读；递归增加了系统开销，延长了递归增加了系统开销，延长了CPUCPU执行时间，多占用了内存执行时间，多占用了内存栈空间；栈空间；非递归效率高，不过程序可读性差；非递归效率高，不过程序可读性差；递归与非递归选择递归与非递归选择大多数递归函数都能用非递归函数来代替。大多数递归函数都能用非递归函数来代替。能用递推就用递推能用递推就用递推,普通情况比递归快普通情况比递归快,除非有问题不用递除非有问题不用递归做不出来。归做不出来。7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第41页递归法/n!recursive functionint Factorial(int n)if (n=0)return 1;return n*Factorial(n-1);long fact(int m)int i;long sum=1;for (i=1;i n n时时，m m 与与 n n 最最大大条条约约数数等等于于 n n 和和 m%n m%n 最最大大条条约数；约数；当当 nn=0=0时，时，m m 和和 n n 最大条约数等于最大条约数等于 mm。求最大条约数求最大条约数 7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第43页/迭代法迭代法long g2(int a,int b)int t;while(b!=0)t=a%b;a=b;b=t;return a;/递归法递归法long g1(int a,int b)if(a%b=0)return b;return g1(b,a%b);求最大条约数求最大条约数 7.6 函数递归调用 大连理工大学软件学院大连理工大学软件学院第44页7.7 数组作为函数参数v 数组元素和数组名都能够作为参数传递给函数数组元素和数组名都能够作为参数传递给函数数组元素数组元素作参数，按值传递方式传递给函数；作参数，按值传递方式传递给函数；数组名数组名作参数，常按地址方式传递给函数。作参数，常按地址方式传递给函数。数组名用于传递地址（即数组第一个元素地数组名用于传递地址（即数组第一个元素地址）；址）；把数组名作为参数传递到函数中，实参和形把数组名作为参数传递到函数中，实参和形参共用同一段内存空间，可经过改变形参而改参共用同一段内存空间，可经过改变形参而改变实参。变实参。大连理工大学软件学院大连理工大学软件学院第45页一、数组元素作参数一、数组元素作参数（性质与简单变量相同，值传递）（性质与简单变量相同，值传递）#includevoid fun(int,int,int);void main()int i,a3=1,2,3 ;fun(a0,a1,a2);for(i=0;i 3;i+)printf(“%5d”,a i );void fun(int a,int b,int c)a+;b+;c+;printf(“%5d%5d%5d n”,a,b,c);修改局部量修改局部量传值参数传值参数7.7 数组作为函数参数大连理工大学软件学院大连理工大学软件学院第46页a 0 x0065FDD012345678910 pan0065FDD00i0m10二、数组名作参数二、数组名作参数（传递地址）（传递地址）#include int sum(int pa ,int n)int m=0,i;for(i=0;i n;i+)m+=pa i;return m;void main()int a 10 =1,2,3,4,5,6,7,8,9,10 ;printf(sum=%dn“,sum(a,10);7.7 数组作为函数参数大连理工大学软件学院大连理工大学软件学院第47页a 0 x0065FDD012345678910 pan0065FDD00i0m10#include int sum(int pa ,int n)int m=0,i;for(i=0;i n;i+)m+=pa i;return m;void main()int a 10 =1,2,3,4,5,6,7,8,9,10 ;printf(sum=%dn“,sum(a,10);pa0 x0065FDF810557.7 数组作为函数参数形参为数组形参为数组pa使用数组元素值使用数组元素值实参为数组实参为数组a一维数组名作参数，能够不指定数组长度一维数组名作参数，能够不指定数组长度二维数组名作参数，能够省略第一维大小，第二维不可省略二维数组名作参数，能够省略第一维大小，第二维不可省略大连理工大学软件学院大连理工大学软件学院第48页课堂练习：课堂练习：编写一个递归函数编写一个递归函数power(base,exponent)power(base,exponent)比如：比如：power(3,4)=3*3*3*3.power(3,4)=3*3*3*3.假设假设exponentexponent是大于等于是大于等于1 1整数。整数。大连理工大学软件学院大连理工大学软件学院第49页作业作业v作业内容：作业内容：电子课件第电子课件第7章全部选择题章全部选择题书后：第书后：第4题题 到到 第第12题（共题（共9题）题）v作业检验时间：作业检验时间：本周六（本周六（12月月5日），不用上交手写版日），不用上交手写版大连理工大学软件学院大连理工大学软件学院第50页