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)的递归调用过程如下图所示,其中,黑色实线箭头表示函数调用,绿色虚线箭头表示函数返回,此函数在返回时函数名将带回返回值。

最近更新

分光光度法测定空气中苯的新方法 2页

出口退税与对外贸易出口关系的实证研究 2页

2025年垂体瘤患者病房护理要点探讨 24页

几种陆生薄囊蕨配子体发育过程的初步研究 2页

几种新型可控硅逆变电路及分析 2页

2025年危急药品与抢救设备规范化管理攻略 22页

几何相似律在聚能效应工程应用中的若干问题 2页

减振、防噪用AJ—1合金及其应用 2页

减少1kHz分辨率频率合成器换频时间的研究 2页

冻结砂土瞬时强度的初步试验研究 2页

冷轧厂为用户提供优质技术服务 2页

冷态开车时液氮回流阀操作方式及问题浅析 2页

冷凝式节能锅炉节能器的节能参数分析 2页

冶金部“氧气管道暂行技术规定”修订会报道 2页

冶炼工艺对55SiMnVB弹簧钢疲劳寿命的影响 2页

冲天炉主要工艺参数的自动检测 2页

冰箱用硬质聚氨酯浇注组合料性能的研究 2页

冬季水玻璃砂改性催硬剂的应用 2页

农药中间体甲基氯化物生产中甲醇回收工艺 2页

农民负担的误区及走出误区的对策 2页

农村经济发展中几个现实问题的探讨 2页

农机零件受土壤磨粒磨损表面磨痕的微观分析 2页

农业科学研究机关应重视水土保持的研究工作 2页

农业新技术——根系类作物空中长 2页

农业劳动力转移背景下的农机化问题探讨 2页

再论经济地理学方法论基础以及与赫特纳残余的.. 2页

内陆水域磷浓度预报模式及其应用 2页

2025年工程竣工自评报告三篇 19页

XX学校义务教育优质均衡发展创建实施方案范文.. 8页

顺丁烯二酸酐工艺规程 25页