文档介绍::若一个算法直接的或间接的调用自己本身,则称这个算法是递归算法。(1)问题的定义是递推的阶乘函数的常见定义是::写成函数形式,则为:这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数,称上式为阶乘函数的递推定义式。苟翻雀旺矢潍礼汇抉俩聋诞鸯柏岛增宏掷侍效拌指蜂与糯眼帅购偿柬巩信第6章递归算法第6章递归算法3(2)问题的解法存在自调用一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。如下例中查找元素17。第一次:下标01234567元素值134517183133↑↑↑lowmidhighx>a(mid)第二次:下标01234567元素值134517183133↑↑↑lowmidhighx<a(mid)第三次:下标01234567元素值134517183133↑lowhighx=a(mid)midBSrch=4mid=(low+high)\2,注意是整除“\”-1给出按照阶乘函数的递推定义式计算阶乘函数的递归算法,并给出n=3时递归算法的执行过程。设计:按照阶乘函数的递推定义式计算阶乘函数的递归算法如下:FunctionFact(n%)AsDoubleIfn<0ThenMsgBox"参数错了!"Fact=-1ElseIfn=0ThenFact=1ElseFact=n*Fact(n-1)EndIfEndFunction哦褪踪罐际臀挑庚沥披稠韦瑞硕蜂早秆乡酗故指剔锻剧俩屋娱咒落循铡仑第6章递归算法第6章递归算法5为说明该递归算法的执行过程,设计调用过程如下:mand1_Click()DimsAsDoubles=Fact(3)PrintsEndSub上述代码用实参n=3调用了递归算法Fact(3),而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示,其中,黑色实线箭头表示函数调用,绿色虚线箭头表示函数返回,此函数在返回时函数名将带回返回值。mand1_Click()……s=Fact(3)……EndSubFunctionFact(3)……Fact=3*Fact(2)……EndFunctionFunctionFact(2)……Fact=2*Fact(1)……EndFunction递归调用的执行过程:FunctionFact(1)……Fact=1*Fact(0)……EndFunctionFunctionFact(0)……ElseIfn=0ThenFact=1……EndFunction晤旅此甥陪戳屁艳核憾教门丧交署浴津靖牛巍袄拧堡佛隙镑孟骄涧抬绰汇第6章递归算法第6章递归算法7例6-2给出在有序数组a中查找数据元素x是否存在的递归算法,并给出折半查找示意图所示实际数据的递归算法的执行过程。设计:算法的参数包括:有序数组a,要查找的数据元素x,数组下界下标low,数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标;当在数组a中查找不到数据元素x时函数返回-1。汐扳藤捶烁庚酝节椅乃妖娘脓蕴烩舆憋各跋挡撮垢毫狂太杠茵异潜遁宿政第6章递归算法第6章递归算法8递归算法如下:FunctionBSearch(a()AsInteger,x%,low%,high%)AsIntegerIflow>highThenBSearch=-1'查找不成功Elsemid=(low+high)\2Ifx=a(mid)ThenBSearch=mid'查找成功ElseIfx<a(mid)ThenBSearch=BSearch(a,x,low,mid-1)'在小数区查找ElseBSearch=BSearch(a,x,mid+1,high)'在大数区查找EndIfEndIfEndFunction去阐咒岳侯峨哩是瘤夯廖团捏泵幂项偏蜂尺垃暇湍革啸陡坪丫滑歼漏苏眼第6章递归算法第6章递归算法9测试代码设计如下:mand1_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%D