2.递推关系（一）

关系（一）"/>

2.递推关系（一）

在计算机进行计算时，使用首项和递推公式很容易计算出每个元素的值。递推关系实质上可以视为是递归函数关系，例如等差数列的递推公式 f(i)=f(i-1)+d 看做递归函数时，表明求解函数值f(i)需要用到函数值f(i-1) 。

递推关系是递推算法的核心，有以下类别的递推关系：

1. 一阶递推：在计算f(i)时，只使用到前面（指项的位置小于i）计算过的一项。例如等差数列：f(i)=f(i-1)+d
2. 多阶递推：在计算f(i)时，需要使用到前面计算过的多项。例如Fibonacci数列：f(i)=f(i-1)+f(i-2)
3. 间接递推：在计算f(i)时，使用一个中间量，而中间量则需要使用前面计算过的项。例如：f(i)=g(i-1)+3 ; g(i)=f(i-1)+1
4. 多维递推：元素处于一个多维矩阵中，递推需要使用矩阵中其他位置的元素。例如：f(i,j)=f(i-1,j-1) + f(i-1,j-2)
5. 逆向递推：这种计算不是从前面的元素往后递推，而是反过来。例如：f(i)=f(i+1)+3

在递推算法中，除了寻找递推关系外，还需要确定递推起点。递推起点值需要通过非递推的方式给出，其他的数据项才能够通过递推关系式计算出。

在编程时可以用一维数组f来存储所有的元素值，递推的过程就是利用公式逐个填写数组元素值的过程。

（以上内容参考教材讲解）

下面来看具体的实例：