文档介绍：主讲教师王佳
信息学院
界限与递归
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. 递归式
递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。
递归算法（或具有递归性质的迭代算法）的运行时间通常用递归式表示。
如：归并排序（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
递归公式：当递推式中只含数列中的项，而