资源描述：
《数据结构与算法第06章 递归算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章递归算法§6.1递归概念§6.2执行过程§6.3设计方法§6.4栈的变化§6.5效率分析§6.6转非递归1)问题递归定义n!=1,当n=0时n·(n-1)·…·1,当n>0时非递归定义n!=1,当n=0时n·(n-1)!,当n>0时递归定义f(n)=1,当n=0时n·f(n-1),当n>0时自己直接(或间接)调用自己。2)问题解法存在自调用例如:一个问题经过加工变为一个或n个规模变小的子问题,子问题的性质相同,仅规模不同。二分查找算法:a1a2a3a4a5a6a7a8从小到大有序,找x,规
2、模8a1a2a3a4a5a6a7a8中点x=a4,则找到,否则xa4,则a5a6a7a8中找x,规模4…定义若一个算法直接或间接地调用自身,则称该算法是递归算法。算法设计的有效方法。[例1]计算n!的递归算法及n=3时的计算过程。intFact(intn){if(n<=0)return1;return(n*Fact(n-1));}voidmain(){intn;n=Fact(3);}执行过程:6n=Fact(3)return(3*Fact(2))retur
3、n(2*Fact(1))return(1*Fact(0))return1结果n=6;112[例2]从小到大有序数组a,查找元素x,找到则返回下标,否则返回-1。a0a1…ai…aj…an-1设计一个一般函数,完成:找xintBSearch(inta[],intx,inti,intj){intmid;if(i>j)return-1;//未找到,返回-1mid=(i+j)/2;//中点下标if(x==a[mid])returnmid;//找到,返回下标midif(x4、arch(a,x,i,mid–1);//在mid前面继续找if(x>a[mid])returnBSearch(a,x,mid+1,j);//在mid后面继续找}…ai…amid-1amidamid+1…aj…思想:小大找xvoidmain(){intA[]={1,3,4,5,17,18,31,33};intidx=BSearch(A,17,0,7);if(idx==-1){printf(“未找到”);}else{printf(“%d”,idx);}}请用VC跟踪程序执行过程,并考察进程的栈的变化
5、。递归算法有效的分析问题的方法有效的算法设计的方法有效但不实用思想:一个较复杂问题,分解为若干个相对简单的同类子问题;(如问题规模大)(规模变小)重复这一过程;最后子问题变成能直接求解。设计:原问题、子问题求解都适用的函数(接口);设计递归出口(直接求解)。[例3]Hanoi塔问题。ABCn个盘子,3根柱子。初始:最后:ABC操作:每次只能拿一个盘子从一个柱子放到另一个柱子上;且大盘不能压小盘;输出步骤问题抽象:A上n个盘子借助于B放到C上。voidHanoi(intn,charA,charB,
6、charC){if(n==0){return;}else{Hanoi(n-1,A,C,B);//上面n-1张盘从A借助于C放到B中printf(“%c->%c”,A,C);//A上面一张盘放到C上Hanoi(n-1,B,A,C);//上面n-1张盘从B借助于A放到C中}}voidmain(){intn;n=Hanoi(4,‘A’,‘B’,‘C’);}运行结果:步数o(n!)[例4]设计一个输出如下形式数值的递归算法:nnnn333221……………voidDisplay(intn){print
7、f(“”);for(inti=1;i<=n;++i)printf(“%d”,n);if(n>1)Display(n-1);}[例5]求2个正整数n和m最大公约数的递推定义式为:gcd(n,m)=gcd(m,n),当n0时voidgcd(intn,intm){if(n<0
8、
9、m<0)return0;if(m==0)returnn;elseif(m>n)returngcd(m,n);elsereturngcd(m,n%m);}(本节完)C语言中函数
10、调用过程(包括递归调用)是用栈实现的。intFact(intn){intx,y;if(n<=0){return1;}else{x=n;y=Fact(x-1);return(x*y);}}voidmain(){intn;n=Fact(3);}我们对例1另写为:00111122236n注意:这里只写出调用参数和局部变量;实际情况可跟踪程序执行。nxynxynynxy进栈退栈main()Fact(3);Fact(2);Fact(1);Fact(0);x效率时间空间(栈)效果不好,但算法易理解。[例]F
