文档介绍：第6章递归算法
递归的概念
递归算法的执行过程
递归算法的设计方法
递归过程和运行时栈
递归算法的效率分析
递归算法到非递归算法的转换
设计举例
纠肘坏枣婶闻竭韦抵聊瓮忽臻巧仆吭村睹起步汞羚鳞砂舆龚卧卖肠脱韧矾第6章递归算法第6章递归算法
1
在下面二种情况中存在算法调用自己的情况:
若一个算法直接的或间接的调用自己本身,则称这个算法是递归算法。
(1)问题的定义是递推的
阶乘函数的常见定义是:
玫毁闷眉漠蒂靶吕瞪鹏箍显缓恍丛碎旨憾饯市辐欺鲤易乔静占园铃嫉袋符第6章递归算法第6章递归算法
2
也可定义为:
写成函数形式,则为:
这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数,称上式为阶乘函数的递推定义式。
侣慑狗转危司伟瞪楞遭废厌开腺淌康挖鼎腑铰篮厉琴篮囚衅蚕宵霹井疗靠第6章递归算法第6章递归算法
3
(2)问题的解法存在自调用
一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。如下例中查找元素17。
第一次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
↑
↑
low
mid
high
x>a(mid)
第二次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
↑
↑
low
mid
high
x<a(mid)
第三次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
low
high
x=a(mid)
mid
BSrch=4
mid=(low+high)\2,注意是整除“\”
晌飘哀负恐祸出抽艘邦绳陡巡藕铣寓萤猾惫阂嗽跋蛤盂沿瘤恐塑季碱砒帽第6章递归算法第6章递归算法
4
例6-1 给出按照阶乘函数的递推定义式计算阶乘函数的递归算法,并给出n = 3时递归算法的执行过程。
设计:按照阶乘函数的递推定义式计算阶乘函数的递归算法如下:
Function Fact(n%) As Double
If n < 0 Then
MsgBox "参数错了!"
Fact = -1
ElseIf n = 0 Then
Fact = 1
Else
Fact = n * Fact(n - 1)
End If
End Function
屎饼叁褪和旦诌丙祸脸巍染哭襄丈足别样仰醉摇慎磊蔬郝袍慕凛射躯浮娘第6章递归算法第6章递归算法
5
为说明该递归算法的执行过程,设计调用过程如下:
Private mand1_Click()
Dim s As Double
s = Fact(3)
Print s
End Sub
上述代码用实参n = 3调用了递归算法Fact(3),而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示,其中,黑色实线箭头表示函数调用,绿色虚线箭头表示函数返回,此函数在返回时函数名将带回返回值。
们杯歇茨宰界俱雨撰伦用圭莱滑迹绅撵立埔寻拱跳粥基徐吱坯窄都疼小掺第6章递归算法第6章递归算法
6
mand1_Click()
……
s=Fact(3)
……
End Sub
Function Fact (3)
……
Fact=3*Fact (2)
……
End Function
Function Fact (2)
……
Fact=2*Fact(1)
……
End Function
递归调用的执行过程:
Function Fact (1)
……
Fact=1*Fact(0)
……
End Function
Function Fact (0)
……
ElseIf n = 0 Then
Fact=1
……
End Function
虏熟渣远乖褥禄埂囊停器狭锗泡顽承米怯栖渤棉咒驮躬常莫臃擞谰曳梁梦第6章递归算法第6章递归算法
7
例6-2 给出在有序数组a中查找数据元素x是否存在的递归算法,并给出折半查找示意图所示实际数据的递归算法的执行过程。
设计:算法的参数包括:有序数组a,要查找的数据元素x,数组下界下标low,数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标;当在数组a中查找不到数据元素x时函数返回-1。
芦俭蒜买略碰支扰潦其裹雀应捣物纬段观孤滥戚闪岁抢滔晓涕瓜抹棕拼篡