算法-递推

一.概念

        递推最通俗的理解就是数列，递推和数列的关系就好比算法和数据结构的关系，数列有点像数据结构中的线性表（可以是顺序表，也可以是链表，一般情况下是顺序表)，而递推就是一个循环或者迭代的枚举过程。

二.递推例子

1.斐波那契数列

        拿到这个题目，我们首先来看题目范围，最多不超过30，那是因为斐波那契数的增长速度很快，是指数级别的。所以如果n很大，就会超过c语言中32位整型的范围。这是一个最基础的递推题，递推公式都已经告诉你了，我们要做的就是利用一个循环来实现这个递推。 

我们只需要用一个F[31]数组，初始化好F[0]和F[1]，然后按照给定的公式循环计算就可以了。写成伪代码像这样:

int fib(int n){int i;//(1)int F[31]={0,1};//(2)for(i = 2; i <= n; ++i){    //(3)Fi]= F[i-1]+F[i-2];//(4)}return F[n];//(5)
}

(1)首先定义一个循环变量;

(2)再定义一个数组记录斐波那契数列的第n项，并且初始化第0项和第1项。·

(3)然后一个 for循环，从第2项开始;

(4)利用递推公式逐步计算每—项的值;·

(5)最后返回第n项即可。

2.泰波纳契数列