1 / 53
文档名称:

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

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

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

分享

预览

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

上传人:相惜 2022/2/24 文件大小:1.29 MB

下载得到文件列表

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

文档介绍

文档介绍:主讲教师 王佳
信息学院
界限与递归
floor和ceiling
一、界限
和式的估计与界限
1. 线性和
2. 级数
3. 和的界限
直接求和的界限
二、递归与递归式
。——效率差!
递推:递推是一种从下往上的“合并求解“过程,即从解决小问题出发,记录小问题的答案,并根据已有的小问题的答案,把问题往大里扩展,“滚雪球”,直到达到大问题的规模为止。并通常用迭代(循环)的方式实现,而不是递归调用,一般认为效率上比递归好。
.
递归和递推的联系:都存在重复计算,是解决较大规模问题的有效方法;
递归和递推的区别:求解思路不同,实现技术上也不一样
.
递归算法设计的思想
Recursive_SOLVE (P) //P是当前问题
if P的规模足够小 then 直接求解
else
将P转换为规模较小问题P'
Recursive_SOLVE(P') //递归调用
将P'还原成为原问题P,结果合并
endif
END Recursive_SOLVE
.
递推算法设计的思想
Recurrence_SOLVE(P) //P是当前问题
定义数组ans[P] //定义一个与问题规模P相适应的数组,用于存放答案
for i from 边界问题P0 to P do //从小问题求解做起
if i 是边界值 then 直接求解,将结果保存在ans中
else
将i转换为规模较小问题i'
ans[i] ←build answer by ans[i']
//用已得到的答案构造i的解ans[i]
endif
repeat
END Recurrence_SOLVE
.
化递归为递推的基本策略:
调用递归函数与调用其它函数没有本质的区别,就是调用一个函数而已,只不过这个函数的名称是自己。
理解程序中调用函数的原理。
用用户自定义栈、断点、基于标号的程序转向实现程序的重复执行、断点返回、返回函数值等——实际上是人工模拟原来由编译程序自动编制执行过程的行为。
.
1.在函数调用之前,系统需完成三件事:
⑴ 为被调用过程的局部变量分配存储区;
⑵ 将所有的实参、返回地址等信息传递给被调用过程保存;
⑶ 将控制转移到被调过程的入口。
2.从被调用过程返回调用过程之前,系统也应完成三件工作:
⑴ 保存被调过程的计算结果;
⑵ 释放被调过程的数据区;
⑶ 依照被调过程保存的返回地址将控制转移到调用过程。
函数调用原理
.
化递归为递推的具体方法
十三条规则,可以把直接递归过程转化为与之等价的迭代过程。
具体见《计算机算法基础》
余祥宣 崔国华 邹海明 出版社:华中科技大学出版社
.
递归式及其求解
1. 递归式
递归式是一组等式或不等式,它所描述的函数是用在更小的输入下该函数的值来定义的。
递归算法(或具有递归性质的迭代算法)的运行时间通常用递归式表示。
如:归并排序(MERGESORT)的运行时间T(n)表示如下:
T(n)=(1) if n=1
T(n)=2T(n/2)+(n) if n>1.
T(n)的解是(nlogn)
.
递归式和递推式
1) 递推式 Recurrence
数列:按一定次序排列的一列数称为数列(sequence of number)。
数列中的每一个"数"都叫做这个数列的项。排在第一位的数称为这个数列的第1项,排在第二位的数称为这个数列的第2项……排在第n位的数称为这个数列的第n项,数列的一般形式可以写成a1,a2,a3,…,an,…,简记为{an}。
递推公式:通过给出数列的第1项(或前若干项),并给出数列的某一项与它的前一项(或前若干项)的关系式来表示数列,这种表示数列构造方式的式子叫做这个数列的递推公式。
.
递推公式是数列所特有的表示法,它包含两个部分:
(1)初始条件——边界值;
(2)递推关系——an与其他一项或多项之间的构造规律。
二者缺一不可。
例如:
斐波纳契数列的递推公式为fn=fn-1+fn-2
等差数列递推公式:an=an-1+d
等比数列递推公式:bn=bn-1×q
.
2) 递归式 Recursion
递归公式:当递推式中只含数列中的项,而