递推算法 #

1. 递推算法介绍
2. 递推算法思想
3. 递推算法的应用

收获 #

学完本节内容，可以初步理解递推思想及其应用。

递推算法介绍 #

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。

这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。

这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法思想 #

递推算法通常可分为两种，一种是顺推法，一种是逆推法。
顺推法是从已知条件出发，逐步推算出要解决的问题的方法；逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程。
无论顺推还是逆推，其关键是要找到相邻的数据项间的关系（即递推关系）。
递推关系的定义如下：
给定一个数的序列H0,H1,…,Hn，若存在整数N0，使当n>N0时,可以用=/>/<等将Hn与其前面的某些项Hi(0<i<n)联系起来。

递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

递推算法的应用 #

常见的顺推法的应用包括：斐波那契数列，平面分隔问题，五人分鱼问题等

常见的逆推法的应用包括：汉诺塔问题，银行初始存款问题，猴子摘桃问题等

小结 #

理解递推算法的基本原理
初步了解递推算法的一些应用场景

习题 #

1. 习题1：简述递推算法的基本思想及分类
2. 习题2：说出几种常见的递推算法的应用场景