程序设计综合实践　第三讲　递归与分治

1、程序设计综合实践03 递归与分治赵中堂内容递归函数课本74页分治法课本223页练习题1、递归函数递归：recursion函数：function1、递归（recursion）函数（1）什么是递归函数直接或者间接调用自身的函数称为递归函数。1、递归函数（2）具有明显递归性质的问题求n！=n*(n-1)*(n-2)*.*1f(n)=1 n=1n*f(n-1) n11、递归函数（2）具有明显递归性质的问题求n！=n*(n-1)*(n-2)*.*1int f(int n)if(n=1)return 1;elsereturn n*f(n-1);f(n)=1 n=1n*f(n-1) n11、递归函数（3）递

2、归方法的基本原理将复杂问题逐步化简，最终转化为一个最简单的问题最简单问题的解决，就意味着整个问题的解决 （4）递归调用应该能在有限次数内终止递归递归调用如果不加以限制，将无数次的循环调用必须在函数内部加控制语句，只有当满足一定条件时，递归终止1、递归函数（5）任何一个递归调用程序必须包括两部分递归调用结束部分递归循环继续部分2、分治法Divide and Conquer分而治之（1）、分治法的基本思想对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决；否则将其分解为k个规模较小的子问题（这些子问题互相独立且与原问题形式相同）递归地解这些子问题， 然后将各子问题的解合

3、并，得到原问题的解。这种算法设计策略叫做分治法(divide and conquer)。 分治法在每一层递归上由三个步骤组成： 1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 3) 合并(combine)： 将各子问题的解合并为原问题的解。 （2）分治法的一般步骤它的一般算法设计范型如下： DIVIDE&CONQUER (P) 1 if （|P|c）/问题P的规模小于c 2 return(DSOLVE(P) else 把问题 P 分成k个子问题： P1, P2

4、, , Pk4 for（i=1;i=k;i+) 5 si DIVIDE&CONQUER(Pi) SCOMBINE(s1, s2, , sk) return S （3）分治法的设计范型 从分治法的一般设计模式可以看出， 直接用它设计出的算法是一个递归算法。1）、在数组A中寻找最大值2）、二叉树遍历、二分查找算法、归并排序、快速排序等算法数据结构课程中讲解（4）、常见的分治算法int max(int *A,int start, int end)/在数组A的下标start和end之间寻找最大值算法描述：如果start=end, return Astart;取start和end的中间mid分别在sta

5、rt,mid和mid+1,end中寻找最大值假设start,mid之间的最大值为max1假设mid+1，end之间的最大值为max2max1、max2的最大值就是数组A的最大值1）、求数组中的最大值#include int max(int *A,int start, int end)if(start=end)return Astart;elseint max1,max2,mid;mid=(start+end)/2;max1=max(A,start,mid);max2=max(A,mid+1,end);if(max1max2)return max1;elsereturn max2;1）、求数组中

6、的最大值int main()int a=1,4,6,2,5,3;int max0,min0;int n;n=sizeof(a)/sizeof(int);max0=max(a,0,n-1);printf(max=%dn,max0);return 0;1）求数组中的最大值3、练习题（1）、设计递归函数，求菲波纳契数列的第n项的值fib(n)=1 n=1fib(n-1)+fib(n-2) n21 n=2参考答案：int fib(int n)if(n=1 | n=2)return 1;elsereturn fib(n-1)+fib(n-2);（2）设计递归函数，求m、n的最大公约数gcd(m,n)=n m%n=0gcd(