资源描述：
《普及讲座1-递归与分治(C++版)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、江苏省大丰高级中学陈鹏PengChenJiangSuDaFengSeniorHighSchool递归与分治Recursion&Partition[一]递归[二]分治29七月20212[一]递归[引例]观察下面的函数：intfac1(intx){intfac2(intx){inti,p;if(x==1)return1;p=1;elsereturnfac2(x-1)*x;for(i=1;i<=x;++i)p=p*i;}returnp;}29七月20213函数自己调用自己[一]递归[定义]如果在一个函数、过程等定义内部又直接或间接地出现有对自身的引用，则称它们是递
2、归的或者是递归定义的。通俗的讲，就是函数或过程自己直接或间接调用自己！29七月20214[一]递归[举例]在数学上，所有偶数的集合可递归地定义为：①0是一个偶数；②一个偶数和2的和是一个偶数。阶乘函数可递归地定义为：29七月20215n!=1n=0n(n-1)!n>0[一]递归[例1]：阶乘函数阶乘函数可以递归地定义为：边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。29七月20216n!=1n=0n(n-1)!n>0边界条件递归方程[一]递归[递归过程分析]29七月20217[一]递归[观察与思考]intf
3、ac2(intx){if(x==1)return1;elsereturnfac2(x-1)*x;}递归定义里的参数是如何变化?边界条件若没有，会如何？29七月20218[一]递归[观察与思考]描述递归定义的函数或求解递归问题的过程称为递归算法。两个条件：1.递归式（递归关系）；使问题向边界条件转化的规则，递归定义必须能使问题的规模越来越简单。2.递归终止条件（边界条件）。所描述问题的最简单情况，它本身不再使用递归的定义。递归表达式是解题的关键！29七月20219[一]递归[例2]：求和：sum(n)=1+2+3+…+n-1+n[例3]：菲波拉契数列：1,1,
4、2,3,5,8…递归关系式——如何求？运用函数的前驱值来计算函数当前值的关系式29七月202110[一]递归[例3]：用递归法求两个正整数m和n的最大公约数。[算法分析]辗转相除法。求m与n的最大公约数等价于求（mmodn）的值与n的最大公约数，此时的n可以当作新的m，而（mmodn）的值当作新的n，所以原问题的求解又变成求新的m与n的最大公约数问题，继续下去，直至(mmodn)为0，最大公约数就是最终存放在n中的值。29七月202111[一]递归[算法分析]递归公式：29七月202112gcd(m,n)=nmmodn=0gcd(n,mmodn)mmodn<
5、>0[一]递归[参考程序片断]intgcd(intm,intn){if((m%n)==0)returnn;elsereturngcd(n,m%n);}当一个问题可以不断的通过一种有规律的增加或递减转化为一个新问题，而解决新问题的方法和原问题相同时，可以考虑过程的递归调用，注意这种“不断的增加或递减”是有尽头的。29七月202113[一]递归[例4]：汉诺塔（towerofHanoi）问题有n个大小不等的中空圆盘，按照从小到大的顺序迭套在立柱A上，另有两根立柱B和C。现要求把全部圆盘从A柱移到C柱的过程，移动过程中可借助B柱（中间柱）。移动时有如下的要求：①一
6、次只移动一个盘；②不允许把大盘放在小盘上边；③可使用任意一根立柱暂存圆盘。29七月202114[一]递归先以三个盘的移动为例，看一下移动过程。29七月202115[一]递归29七月202116ACB1:(n-1,A,B,C)2:A→C3:(n-1,B,C,A)(n,A,C,B)缩小数据规模/递归直接求解[一]递归29七月202117[算法分析]（1）当n=1时，只需要移动一次A---C；（2）当n=2时，需要移动三次；A---1---B；A---2---C；B---1---C；（3）当n>=3时，先将前n-1个盘子以C为中介移到B柱子；再将第n个盘子移到C柱
7、子；最后将n-1个盘子以A为中介从B柱移到C柱。[一]递归29七月202118[参考程序片断]move(total，‘A’，‘B’，‘C’);voidmove(intn,charz1,charz2,charz3){if(n==1)printf("%c->%c",z1,z3);else{move(n-1,z1,z3,z2);printf("%c->%c",z1,z3);move(n-1,z2,z1,z3);}}[一]递归29七月202119例5：数字排列[问题描述]由m个A，n个B组成若干个排列。从某个排列的位置1开始数，数到任意位置时都能保证A的个数
8、不少于B的个数，则称该排列为合理排列。例如：当m=2
