c语言递归算法ppt课件.ppt

,而递归程序设计是C++语言程序设计中的一种重要的方法,它使许多复杂的问题变得简单,容易解决了。递归特点是:函数或过程调用它自己本身。其中直接调用自己称为直接递归,而将A调用B,B以调用A的递归叫做间接递归。2.【例1】给定n(n>=1),用递归的方法计算1+2+3+4+...+(n-1)+n。【算法分析】本题可以用递归方法求解,其原因在于它符合递归的三个条件:    (1)本题是累加问题:当前和=前一次和+当前项,而前一次和的计算方法与其相同,只是数据不同s(n)=s(n-1)+n;     (2)给定n,所以是有限次的递归调用;     (3)结束条件是当n=1,则s=1。【参考程序】#include<iostream>usingnamespacestd;intfac(int);//递归函数intmain(){ intt; cin>>t;//输入t的值 cout<<"s="<<fac(t)<<endl;//计算1到t的累加和,输出结果}intfac(intn){ if(n==1)return1; return(fac(n-1)+n);//调用下一层递归},当T=5时,输出结果:S=15,其递归调用执行过程是:(设T=3)递归调用过程,实质上是不断调用过程或函数的过程,由于递归调用一次,所有子程序的变量(局部变量、变参等)、地址在计算机内部都有用特殊的管理方法——栈(先进后出)来管理,一旦递归调用结束,计算机便开始根据栈中存储的地址返回各子程序变量的值,并进行相应操作。4.【例2】设有N个数已经按从大到小的顺序排列,现在输入X,判断它是否在这N个数中,如果存在则输出:“YES”否则输出“NO”。【算法分析】该问题属于数据的查找问题,数据查找有多种方法,通常方法是:顺序查找和二分查找,当N个数排好序时,用二分查找方法速度大大加快。二分查找算法:  (1)设有N个数,存放在A数组中,待查找数为X,用L指向数据的高端,用R指向数据的低端,MID指向中间:  (2)若X=A[MID]输出“YES”;  (3)若X<A[MID]则到数据后半段查找:R不变,L=MID+1,计算新的MID值,并进行新的一段查找;  (4)若X>A[MID]则到数据前半段查找:L不变,R=MID-1,计算新的MID值,并进行新的一段查找;   (5)若L>R都没有查找到,则输出“NO”。   该算法符合递归程序设计的基本规律,可以用递归方法设计。5.【参考程序】#include<iostream> #include<cstdlib> usingnamespacestd; inta[11]; voidsearch(int,int,int); intmain()//主程序{ intk,x,L=1,R=10; cout<<"输入10个从大到小顺序的数:"<<endl; for(k=1;k<=10;k++) cin>>a[k]; cin>>x; search(x,L,R); system("pause"); } voidsearch(intx,inttop,intbot)//二分查找递归过程{ intmid; if(top<=bot) { mid=(top+bot)/2;//(x==a[mid])cout<<"YES"<<endl;//找到就输出 else if(x<a[mid])search(x,mid+1,bot);//判断在前半段还是后半段查找 elsesearch(x,top,mid-1); } elsecout<<"NO"<<endl; }7.【例3】Hanoi汉诺塔问题有N个圆盘,依半径大小(半径都不同),自下而上套在A柱上,每次只允许移动最上面一个盘子到另外的柱子上去(除A柱外,还有B柱和C柱,开始时这两个柱子上无盘子),但绝不允许发生柱子上出现大盘子在上,小盘子在下的情况,现要求设计将A柱子上N个盘子搬移到C柱去的方法。【算法分析】本题是典型的递归程序设计题。  (1)当N=1时,只有一个盘子,只需要移动一次:A—>C;   (2)当N=2时,则需要移动三次:     A------ 1------>B,     A------ 2------>C,     B------ 1------>C. (3)如果N=3,则具体移动步骤为:,第4步,第7步抽出来就相当于N=2的情况(把上面2片捆在一起,视为一片):10.