递推学习总结

发表于 | 阅读次数:
字数统计: 678 字

回来学校之后觉得应该把基础补下，于是就有了这篇博客

本博客的主要内容来自焦作一中校本教材

递归

递推定义

直接或间接调用自己的算法叫做递归算法。在一个函数的内部直接或间接地出现有对自身的引用，称他为递归函数。

写一个递归函数的两个要素： 边界条件， 递归方程。 这两部分组成了一个递归函数。

递归的一般形式

1
2
3
4
5
void rec(参数列表) {
	if (test)    return; //边界条件
    rec(参数列表); //递归调用阶段
    . . . //递归返回阶段
}

因为递归的表达简单， 但是效率并不高， 所以基于递归出现了记忆化搜索。

记忆化搜索

不去做已经计算过的事情可以大大减少算法的复杂度， 如果该种情况在之前已经求出并且有记录， 那么在求解这种情况的时候直接返回之前的记录即可， 减少重复计算。

1
2
3
4
void rec(参数列表) {
    if (被计算过) return F[当前的情况]
	. . . //与递归的剩下部分大致相同
}

求解递归问题的一般思路

寻找把大问题化小的递归式， 寻找递归的边界条件。
将小问题的答案汇总成大问题的答案。

递归的几点注意

  1. 参数， 一般都会有一个参数表示递归的层数。
  2. 边界， 递归的第一句一定是一个 if 语句， 如果到达边界， 就要退出递归， 向上一层返回。
  3. 递归调用， 注意参数的传递，要有参数表示递归的层数， 另外递归函数的参数要向边界去靠近， 防止出现死循环。
  4. 本层递归结束的时候，考虑向上一层返回时， 把改过的全局变量改回去，这就是回溯的思想。

递推

递推的定义

通过数学的推导， 将复杂的运算化为重复的简单运算。直接从边界出发， 利用循环来求出目标解的方法

常见的递推关系

  1. 前项和
  2. 等差数列
  3. 等比数列
  4. 斐波那契数列
  5. 第二类 Stirling 数
  6. 错位排序数列
  7. 平分平面的最大区域数
  8. 组合数
  9. 卡特兰数

常见的递推关系的递推式

  1. 斐波那契数列 F[i] = F[i-1] +F[i-2];
  2. 第二类 Stirling 数 S(n,k) = S(n-1, k-1) + k*(n-1, k);
  3. 错位排序 d[1] = 0, d[2] = 1, d[n] = (n-1) * (d[n-2]+d[n-1]);