1, 2, 4, 8, 16 …… 数列的下一项是什么？
1, 2, 3, 5, 8 …… 数列的下一项是什么？
递推 就是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。
可用递推算法求解的问题一般有以下两个特点：
- 问题可以划分成多个状态；
- 除初始状态外，其它各个状态都可以用固定的递推关系式来表示.
利用递推算法解决问题，需要做好以下四个方面的工作：
- 确定递推变量 应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。从直观角度出发，通常采用一维数组。
- 建立递推关系 递推关系是指如何从变量的前一些值推出其下一个值，或从变量的后一些值推出其上一个值的公式（或关系）。递推关系是递推的依据，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，通过分析和推理，才能确定问题的递推关系。
- 确定初始（边界）条件 对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。
- 对递推过程进行控制 递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步分析出用来结束递推过程的条件。
递推通常由循环来实现，一般在循环外确定初始（边界）条件，在循环中实施递推。递推法从递推方向可分为顺推与倒推。
顺推法 所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。
逆推法 所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。
一句话概括：顺推是从条件推出结果，倒推从结果推出条件。
递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有明确的计算公式可以遵循，因此常常采用递推算法实现。
数学里面的斐波那契数列便是一个使用递推算法的经典例子。13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题，其大意如下：
如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1月份出生，3月份才可产仔。那么假定一年内没有产生兔子死亡事件，那么 1年后共有多少对兔子呢?
我们先来分析一下兔子产仔问题。我们来逐月看一次每月的兔子对数：
♦第一个月：1对兔子;
♦第二个月：1对兔子;
♦第三个月：2对兔子;
♦第四个月： 3对兔子;
♦第五个月：5对兔子;
从上面可以看出，从第个3月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式如下：
第n个月兔子总数Fn = Fn-2 + Fn -1。
这里，初始第一个月的兔子数为F1=1，第二个月的兔子数为F2=1。
递推代码参考：
int Fibonacci2(int n) {
int a[100];
a[1] = 1;
a[2] = 1;
for (int i = 3; i <= n;i++){
a[i] = a[i - 1] + a[i - 2];
}
return a[n];
}递归代码参考：
int Fibonacci(int n) {
int f1, f2;
if (n == 1 || n == 2) {
return 1;
}else{
f1 = Fibonacci(n-1);
f2 = Fibonacci(n-2);
return f1 + f2;
}
}递归与递推区别
递推、递归查词典都为Recursion。
递推：从初值出发反复进行某一运算得到所需结果—–从已知到未知，从小到大。（比如每年长高9cm，20年180，30后270）。
递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果—-从未知到已知，从大到小，再从小到大。递归(Recursion)是从归纳法(Induction)衍生出来的。一个运算（操作），可以通过不断调用本身的运算形式，往往需要通过前一次的结果来得到当前运算的结果，因而，程序运行时，总是先一次次地「回溯」前一次的结果（回溯过程中这些结果是未知的，直到回溯到初值令回溯终止，再层层递推回来得到当前要求的值）。