递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。
通常是通过计算前面的一些项来得出序列中的指定项的值。
递推通常用于数列的计算中。f(0)-->f(1)-->f(2)-->f(3)，例如：
(1) a5=10；

(2) a4=a5+2=12;

(3) a3=a4+2=14;

(4) a2=a3+2=16;

(5) a1=a2+2=18;

我们一开始只知道a5的值，要直接求a1的值，这时通过 f(n) = f(n-1) + 2 ；待f(n)的n值回到1时，我们就可以得到a1的值。这就是一个简单的递推的运算。下面我们通过实际做题来理解这种解题思路。

1055: 兔子繁殖问题

• 题目描述
  这是一个有趣的古典数学问题，著名意大利数学家Fibonacci曾提出一个问题：有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？
• 输入
  输入月数n（1<=n<=44）。
• 输出
  输出第n个月有多少对兔子。
• 参考代码：

#include<stdio.h>
int main()
{
    int n,a,b,s;
    a=b=1;//b代表最初的兔子数，a代表每个月增加的兔子数。
    scanf("%d",&n);
    for(int i=3;i<=n;i++){
        s=b;//暂存上个月的兔子数
        b=b+a;//计算新的一月兔子数量
        a=s;//更新上一个月兔子数量
    }
    printf("%d\n",b);
    return 0;
}

• 代码解析：
  这是一道典型的递推类题目，我们在遇到这类题目时，要注意找到问题的关键。例如这题，我们可以抓住几个点。一对兔子，出生三月后每月生一对兔子。新出生的兔子每隔三个月又生新的兔子。这里我们可以得出一个式子。从第三个月为起点，每个月每对兔子都会生出一对兔子。。
• 在这道题中，我们把循环里i的初值从3开始计算。因为第3个月时，他依然是只有一只兔子。而在这个月开始，每对兔子都会生一对兔子，也就是加上 上个月的兔子数。具体如何，大家在纸上列出来便可得知：

月份 数量
1 - 1（没有新出生兔子）
2 - 1（没有新出生兔子）
3 - 2（3月份新出生1只兔子）
4 - 3（4月份新出生1只兔子）
5 - 5（5月份出生2只兔子，其中一只兔子是老母兔生的，另一只是地三月份出生的兔子生的）
6 - 8（6月份出生3只兔子，其中一只兔子是老母兔生的，一只是地3月份出生的兔子生的，另一只是4月份出生的兔子生的）

从中我们可以看出明显的规律：

从第三月开始每月的兔子数量是上两月之和
在程序中可以总让第n-2月和第n-1月相加
所以要记录前两个月的数量以及将这交换两个数总是置为第n-2月和第n-1月
这就是著名的fabinacci数列，后一项等于前两项的和，也就是f(n)=f(n-1)+f(n+2)。

递推在程序中算比较常用的一种算法，希望大家都能够掌握好这一算法。