ch6 数据结构 递归算法ppt课件.ppt

第6章串第6章递归算法主要内容:递归的概念递归算法的执行过程递归算法的设计方法递归过程和运行时栈递归算法的效率分析递归算法到非递归算法的转换2递归算法直接或间接调用自身的算法称为递归算法1、问题的定义是递归的例:、问题的解法存在自调用例:在有序数组a中查找是否存在元素x。二分查找思想:在a[low]~a[hight](low为寻找区域中开始处下标,high则为结束处的下标)寻找是否存在元素x;若low>high,则不存在x,返回-1;否则,求出中间元素下标mid=(low+high)/2;若a[mid]==x,则查找成功返回mid的值;若a[mid]>x则在a[low]~a[mid-1]间继续寻找;若a[mid]<x则在a[mid+1]~a[high]间继续寻找;:0123456789100513192137566474808892lowhighmid第一次比较:low=0,high=10,mid=5;a[mid]>21;则high=mid-1=4,并在a[low]~a[high]中继续查找;第二次比较:low=0,high=4,mid=2;a[mid]<21;则low=mid+1=3,并在a[low]~a[high]中继续查找;第三次比较:low=3,high=4,mid=3;a[mid]=21;则返回mid的值;5在有序表中查找20:0123456789100513192137566474808892lowhighmid第一次比较:low=0,high=10,mid=5;a[mid]>20;则high=mid-1=4,并在a[low]~a[high]中继续查找;第二次比较:low=0,high=4,mid=2;a[mid]<20;则low=mid+1=3,并在a[low]~a[high]中继续查找;第三次比较:low=3,high=4,mid=3;a[mid]>20;则high=mid-1=2,并在a[low]~a[high]中继续查找;第四次比较:low>high,20不存在数组中,返回-1;6//算法实现intbin_search(noder[],intlow,inthigh,ElemTypek){intmid;if(low<high)return–1;//查找失败mid=(low+hig)/2;//取区间中点if(r[mid].key==k)returnmid;//查找成功elseif(r[mid].key>k)returnbin_search(r,low,mid-1,k);//左elsereturnbin_search(r,mid-1,high,k);//右}//求阶乘的递归程序intfact(intn){intx,y;if(n<0){cout<<“error!”<<endl;return-1;}if(n==0)return1;else{x=n-1;y=fact(x);returnn*y;}}voidmain(){intfn;fn=fact(3);cout<<fn<<endl;}8n=:1)当前指令地址在转到被调用函数前,保存当前主调函数执行的指令地址;当被调用函数执行完毕后,按照栈顶中所保存的指令地址,转至该指令处继续往下执行。2)本函数的局部变量值。在转到被调用函数前,保存当前主调函数的局部标量;当函数调用返回时,根据栈中队局部变量的值恢复主调函数的局部变量。