1 / 49
文档名称:

第6章递归算法.ppt

格式:ppt   大小:489KB   页数:49页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第6章递归算法.ppt

上传人:szh187166 2018/10/8 文件大小:489 KB

下载得到文件列表

第6章递归算法.ppt

相关文档

文档介绍

文档介绍:第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。
芦俭蒜买略碰支扰潦其裹雀应捣物纬段观孤滥戚闪岁抢滔晓涕瓜抹棕拼篡

最近更新

云南省2018年保育员五级业务能力考试试题试题.. 11页

2025年度奶茶店员工劳动合同(含员工调岗规定.. 8页

2025年度夫妻财产分割与子女就业援助协议书 9页

2025年度夫妻婚内财产分配及子女抚养费协议 8页

2025年度夫妻共买别墅产权约定协议 8页

2025年度天猫跨境电商代理销售合同 9页

2025年度大货车挂靠公司车辆租赁及维修服务合.. 9页

2025年度大数据中心用地国有土地使用权出让合.. 9页

2025年度大学生实习劳动合同电子版(含实习期.. 8页

2025年度大型活动会务策划与执行服务合同 9页

2025年度大型商场专业保洁员劳动合同 7页

2025年度夜场领队赛事运营管理合同 9页

2025年度多人共同创业项目借款合同 8页

2025年度外墙施工安全应急物资储备与调配合同.. 9页

2025年度外墙保温及真石漆涂料施工工程监理及.. 9页

2025年度外包工安全责任与事故预防措施合同 8页

2025年度墓园墓地销售代理合同 9页

2025年度基础设施项目年挖土方合同简易版 9页

2025年度培训机构图书资料管理员聘用合同 7页

2025年度城市轨道交通建设项目合同示范文本 8页

2025年度城市综合体幕墙施工与售后保养合同 9页

2025年度城市商业街店铺租赁合同书 8页

2025年度城市住宅租赁合同(含租赁押金退还).. 7页

2025年度地基基础加固工程施工与监理合同 8页

2025年度在线教育平台教师服务合同 9页

2025年度土建施工安全风险评估与管理协议 8页

人教版三年级下册数学期中测试卷(名师推荐).. 4页

图书管理系统调研报告 12页

2023年贵州省中考物理试卷【含答案】 9页

完美修改版《矿山井巷工程施工及验收规范》GB.. 80页