第6章递归算法ppt课件.ppt

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

1、第6章递归算法6.1递归的概念6.2递归算法的执行过程6.3递归算法的设计方法6.4递归过程和运行时栈6.5递归算法的效率分析6.6递归算法到非递归算法的转换6.7设计举例1在下面二种情况中存在算法调用自己的情况：若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。（1）问题的定义是递推的阶乘函数的常见定义是：6.1递归的概念2也可定义为：写成函数形式，则为：这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称上式为阶乘函数的递推定义式。3（2）问题的解法存在自调用一个典型的例子是在有序数组中查

2、找一个数据元素是否存在的折半查找算法。如下例中查找元素17。第一次:下标01234567元素值134517183133↑↑↑lowmidhighx>a(mid)第二次:下标01234567元素值134517183133↑↑↑lowmidhighx

3、=3时递归算法的执行过程。设计：按照阶乘函数的递推定义式计算阶乘函数的递归算法如下：FunctionFact(n%)AsDoubleIfn<0ThenMsgBox"参数错了！"Fact=-1ElseIfn=0ThenFact=1ElseFact=n*Fact(n-1)EndIfEndFunction5为说明该递归算法的执行过程，设计调用过程如下：PrivateSubCommand1_Click()DimsAsDoubles=Fact(3)PrintsEndSub上述代码用实参n=3调用了递归算法Fact(3)

4、，而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示，其中，黑色实线箭头表示函数调用，绿色虚线箭头表示函数返回，此函数在返回时函数名将带回返回值。6SubCommand1_Click()……s=Fact(3)……EndSubFunctionFact(3)……Fact=3*Fact(2)……EndFunctionFunctionFact(2)……Fact=2*Fact(1)……EndFun

5、ction递归调用的执行过程：FunctionFact(1)……Fact=1*Fact(0)……EndFunctionFunctionFact(0)……ElseIfn=0ThenFact=1……EndFunction7例6-2给出在有序数组a中查找数据元素x是否存在的递归算法，并给出折半查找示意图所示实际数据的递归算法的执行过程。设计：算法的参数包括：有序数组a，要查找的数据元素x，数组下界下标low，数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标；当在数组a中查找不到数据元素x时函

6、数返回-1。8递归算法如下：FunctionBSearch(a()AsInteger,x%,low%,high%)AsIntegerIflow>highThenBSearch=-1'查找不成功Elsemid=(low+high)2Ifx=a(mid)ThenBSearch=mid'查找成功ElseIfx

7、unction9测试代码设计如下：PrivateSubCommand1_Click()Dima(8)AsIntegera(0)=1:a(1)=3:a(2)=4:a(3)=5a(4)=17:a(5)=18:a(6)=31:a(7)=33Dimy%DimbnPrint"数组a为："Fori=0To7Printa(i);Nexty=InputBox("请输入你要找的元素！")Printbn=BSearch(a,y,0,7)Ifbn=-1ThenPrint"你要找的元素"&y&"不在数组a中！"ElsePrint"你

8、要找的元素"&y&"在数组a中的下标为"&bn&"."EndIfEndSub10BSearch(a,x,0,7)的递归调用过程如下图所示，其中，实箭头表示过程调用，虚箭头表示过程的返回值。BSearch(a,y,0,7)…mid=3…BSearch=BSearch(a,y,4,7)SubCommand1_Click()…x=17…bn=BSearch(a,y,0,7)EndSubBSearch(a,