1 / 56
文档名称:

算法设计与分析—递归算法.ppt

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

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

分享

预览

算法设计与分析—递归算法.ppt

上传人:aluyuw1 2018/2/28 文件大小:1.55 MB

下载得到文件列表

算法设计与分析—递归算法.ppt

相关文档

文档介绍

文档介绍:第6章递归算法
1
递归的概念
递归算法的执行过程
递归算法的设计方法
递归过程和运行时栈
递归算法的效率分析
递归算法到非递归算法的转换
设计举例

一、在日常生活中,递归一词较常用于描述以自相似方法重复事物的过程。
例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。
2
德罗斯特效应(英语:Droste effect)是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片,进而小图片中还有更小的一幅她手持同一物体的图片,依此类推。
3
二、在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。
例:第5个人的年龄比第4个的年龄大2岁,有4个人的年龄比第3个的年龄大2岁,有3个人的年龄比第2个的年龄大2岁,有2个人的年龄比第1个的年龄大2岁,第1个的年龄10岁。
4
例:阶乘的定义。
5
6
在下面二种情况中存在算法调用自己的情况:
(1)问题的定义是递推的
阶乘函数的常见定义是:
7
也可定义为:
写成函数形式,则为:
这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数,称上式为阶乘函数的递推定义式。
8
(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
9

例6-1 给出按照阶乘函数的递推定义式计算阶乘函数的递归算法,并给出n = 3时递归算法的执行过程。
设计:按照阶乘函数的递推定义式计算阶乘函数的递归算法如下:
long int Fact(int n)
{ int x;
long int y;
if(n < 0) //n < 0时阶乘无定义
{ printf(“参数错!”);
return -1;
} 
if(n == 0) return 1;
else
{ y = Fact(n - 1); //递归调用
return n * y;
}
}
10
为说明该递归算法的执行过程,设计调用过程如下:
void main(void)
{
long int fn;
  fn = Fact(3);
}
上述代码用实参n = 3调用了递归算法Fact(3),而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示,其中,黑色实线箭头表示函数调用,绿色虚线箭头表示函数返回,此函数在返回时函数名将带回返回值。

最近更新

仿射跳扩散模型下期权定价的稳健Fourier-Cos方.. 9页

“中国科学院化学情报网计算机应用交流会”在.. 2页

Y zY H型钎头的试验与应用 2页

X射线对产品内部结构和装配质量的分析 2页

WE型聚乙烯蜡在LLDPE挤出吹塑中的应用 2页

TY-43A数字面板表性能及应用 2页

2025年幼儿园大班教育随笔三篇 7页

SP-1多功能外加剂的性能及应用 2页

SK-35型潜孔钻机在日铁矿业公司的应用 2页

SDA脱硫工艺在烧结烟气脱硫中的应用 2页

2025年幼儿园保育工作计划精选5篇 13页

第三章保险法的基本原则 44页

PVC膜四碘络铋离子选择电极在金属分析中的应用.. 2页

Pr—Fe—B烧结永磁材料的研究 2页

不确定结构的拓扑优化设计及分析 3页

2025年幼儿园中班4月份工作总结 12页

PDC钻头切削齿工作角的设计方法 2页

北师大版数学五年级下册:数学与购物估计费用.. 20页

ND 5型机车主机油泵泵体的扫膛故障及修复方法.. 2页

Mn-V双相钢变形特性的研究 2页

2025年年度工作总结报告个人范文 18页

校园交通安全责任合同 6页

LPG低温储存装置管道泄漏风险分析 2页

LDC-2型失磁保护误动的情况分析 2页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

煤矿春季预防性电气试验试措施样板 18页

2025届高考模拟作文“时间管理”升格导写 5页

佛教用超度牌位(打印版) 5页

《于宏杰-到底神要的是什么呢》 5页

土方工程施工方案与技术措施MicrosoftWord文档.. 64页