算法基础之递推（C++示例）
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从已知条件出发逐步推到问题结果，此种方法叫顺推。
从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果。递推算法的
执行过程如下:
(1)根据已知结果和关系，求解中间结果。
(2)判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。
递推与递归的区别
比如阶乘函数：f(n)=n*f(n-1)
在f(3)的运算过程中,递归的数据流动过程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而递推如下:
f(0)-->f(1)-->f(2)-->f(3)
相对于递归算法,递推算法免除了数据进出栈的过程，递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视。
例1、斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题，其大意如下：
如果一对一个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月才可以生出小兔子。也就是，1月份出生，3月份开始产仔。那么假定一年内没有产生兔子死亡事件，那么1年之后共有多少对兔子呢？
分析
第一个月：1对兔子；
第二个月：1对兔子；
第三个月：2对兔子；
第四个月：3对兔子；
第五个月：5对兔子；
第六个月：8对兔子；
……
从中可以看出，从第三个月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式如下：
第n个月兔子总数Fn=Fn-1+Fn-2。
这里初始第一个月的兔子数F1=1，第二个月的兔子数F2=1。
源码如下：
//请留意递归算法和递推算法对比
#include<iostream>
using namespace std;
//递归算法求解
int Fib(int n){
if(n==1 || n==2)
return 1;
else
return (Fib(n-1)+Fib(n-2));
}
//递推算法求解
int Fib2(int n){
int a=1,b=1,c;
for(int i=1;i<=n;i++){
if(i<=2)
c=1;
else{
c=a+b;
a=b;
b=c;
}
}
return c;
}
int main()
{
int n;
cout<<"请输入时间（月数）：";
cin>>n;
cout<<"经过"<<n<<"个月之后"<<endl;
cout<<"兔子的数量为（递归算法）："<<Fib(n)<<"对"<<endl;
cout<<"兔子的数量为（递推算法）："<<Fib2(n)<<"对"<<endl;
return 0;
}
运行之结果如下：
请输入时间（月数）：12
经过12个月之后
兔子的数量为（递归算法）：144对
兔子的数量为（递推算法）：144对
例2、猴子吃桃
猴子摘了一堆桃子，第一天吃了总数一半多一个，第二天吃了剩余桃子的一半多一个.......直到第十天，他发现只剩1个桃子，问他开始摘了几个桃子?
分析：
逆推法是根据结果推出已知条件，推算方法与顺推法类似，只是需要将结果作为初始条件向前推算。
根据第10天的桃子个数往前推算（逆推）：
第10天只剩1个桃子；
第九天吃了桃子的一半零一个，假设第9天吃之前的桃子个数为x，则有x-(x/2+1)=1，即x=2×(1+1)。其中第一个1表示第10天的桃子个数。接着往前推算；
假设第八天吃桃子之前有x个，第九天吃桃子前有y个（第九天的桃子个数可以由第10天的桃子个数推算
得到），则有x-(x/2+1)=y，即y=2×(y+1)。依此类推，可以得到第1天的桃子个数。
源码如下：
#include<iostream>
using namespace std;
int fun(int n)//逆推算法，n代表天数
{
int i, number=1;
for(i=1;i<=n-1;i++)
{
number=(number+1)*2;
}
return number;
}
int main()
{
cout<<"开始摘的桃子："<<fun(10)<<"个"<<endl;
return 0;
}
运行之结果如下：
开始摘的桃子：1534个
例3、从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
解题思路：要解决走N步共有多少种走法，我们在拿到题目的时候最直接的想法就是先画出当N=1、N=2、N=3。。。。。N=n时对应走法的图例，由简单到复杂、由特殊到一般的推理过程，找出规律获得解题的思路。
（1）当N=1时，绘出走法图
共有3种不同的走法，也就是黑色线条的数量，即f(1)=3
（2）当N=2时，绘出走法图
共有7种不同的走法，也就是绿色线条的数量，即f(2)=7
（3）当N=3时，绘出走法图
共有17种不同的走法，也就是红色线条的数量，即f(3)=17
由此看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。
a.上一步，即f（n-1）有多少个终点是有3种走法的。
对于N=3时，f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的，这3个点是怎么得到的呢？它的存在与N值有没有必然的联系？如果我们能找到它与N之间的关系，问题也就解决了。有了这样的思路以后，我们不难找到这样的规律：如果f（n-2）存在，即上上步存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条向上走的线路在到达f（n-1）之后， 向f（n）出发时也必然有左、上、右这三种走法，那么我们就得出了这样的结论：当f（n-2）存在时，f（n-2）的值实际上就等价于f（n-1）有多少个终点是有3种走法。
b.f（n-1）有多少个终点是有2种走法的
对于N=3时，有4个点D、E、F、G可以走出2种不同走法的，这4个点又是怎么得到的呢？它与N值有什么联系呢？ 实际上我们在解决了上一个问题的时候，这个问题就变得相当容易了， f（n-1）减掉刚才有3种走法的点，剩下的点不就是只有2种走法了吗？即f（n-1）-f（n-2）。
c. 得出f（n）的一般关系式
f(n)=3*f(n-2)+2*(f(n-1)-f(n-2) ) (n>=3)
化简：
f(n)=2*f(n-1)+f(n-2) (n>=3)
任何递推题，都会有临界条件。当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。只有当N>=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2)
源码如下：
#include <stdio.h>
#include <windows.h>
int main()
{
int n;
int i;
int fn_1,fn_2;
printf("please input n=");
scanf("%d",&n); //输入任意n值
int fn=0;
if(n==1)
fn=3; //初始化当n=1和n=2时的临界条件
else if(n==2)
fn=7;
else{
fn_1=7;
fn_2=3;
for(i=3;i<=n;i++)
{
fn=2*fn_1+fn_2; //当n>=3时fn的通式
fn_2=fn_1;//更新fn_1和fn_2的值
fn_1=fn;
}
}
printf("一共有%d种走法！\n",fn); //输出结果
return 0;
}
运行之结果如下：
please input n=5
一共有99种走法！
