ch6 递归算法(梁)ppt课件.ppt

《ch6 递归算法(梁)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章　递归算法主讲：梁宝兰第6章递归算法主要内容：递归的概念递归算法的执行过程递归算法的设计方法递归过程和运行时栈递归算法的效率分析递归算法到非递归算法的转换2递归算法直接或间接调用自身的算法称为递归算法1、问题的定义是递归的例：阶乘函数定义6.1递归的概念32、问题的解法存在自调用例：在有序数组a中查找是否存在元素x。二分查找思想：在a[low]~a[hight](low为寻找区域中开始处下标，high则为结束处的下标)寻找是否存在元素x；若low>high,则不存在x，返回-1；否则，求出中间元素下标mid=(low+high

2、)/2；若a[mid]==x，则查找成功返回mid的值；若a[mid]>x则在a[low]~a[mid-1]间继续寻找；若a[mid]21;则high=mid-1=4，并在a[low]~a[high]中继续查找；第二次比较：low=0，high=4，mid=2；a[mid]<21;则low=m

3、id+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]中继续查找

4、；第三次比较：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(lowk)ret

5、urnbin_search(r,low,mid-1,k);//左elsereturnbin_search(r,mid-1,high,k);//右}6.1递归的概念76.2递归算法的执行过程//求阶乘的递归程序intfact(intn){intx,y;if(n<0){cout<<“error!”<

6、行过程保护现场保护现场保护现场保护现场恢复现场恢复现场恢复现场恢复现场6.2递归算法的执行过程9函数调用的现场保护与现场恢复：1)当前指令地址在转到被调用函数前，保存当前主调函数执行的指令地址；当被调用函数执行完毕后，按照栈顶中所保存的指令地址，转至该指令处继续往下执行。2)本函数的局部变量值。在转到被调用函数前，保存当前主调函数的局部标量；当函数调用返回时，根据栈中队局部变量的值恢复主调函数的局部变量。6.2递归算法的执行过程10main()现场返回地址保护fn=fact(3)现场返回地址保护y=x=2n=3fact(2)现场返回

7、地址保护y=x=1n=2fact(1)现场返回地址保护y=x=0n=111fn=y=x=2n=3y=x=1n=2y=x=0n=1根据栈中内容，恢复fact(1)现场根据栈中内容，恢复fact(2)现场根据栈中内容，恢复fact(3)现场根据栈中内容，恢复main()现场返回地址1返回地址1返回地址26返回地址126.3递归算法的设计方法用递归算法求解问题的充分必要条件:1.问题具有某种可借用的类同自身的子问题描述的性质2.某一有限步的子问题有直接的解存在设计递归算法的方法:1.把对原问题的求解设计成对子问题求解的形式2.设计递归的出

8、口13田字表中路径数如下图所示，田字表由m*n个1*1的方格所组成，在田字表右下角原点处（0,0）处有一小人，该小人需要可以沿着表中框线向上或向右前进。则小人从原点出发，到达（m，n）定点可以有多少中走法。(0,0)(m,n)14(0