原文地址http://www.cnblogs.com/liukemng/p/3719385.html

遞推法就是根據(jù)已知條件，分析推導(dǎo)出問題中的聯(lián)系，然后一步一步進(jìn)行推倒直至得到結(jié)果。

根據(jù)具體問題我們需要選擇是正推還是逆推來解決問題。

下面先舉一個遞推中的經(jīng)典例子，就是求兔子數(shù)量的問題：

現(xiàn)有一只一個月大的兔子，已知當(dāng)兔子在第三個月大時每月就可以生下一只小兔子（好吧，就按兔子是無性繁殖的），求一年后兔子的總數(shù)量。

我們根據(jù)問題分析，發(fā)現(xiàn)可以把兔子分三類：一個月大、二個月大、三個或三個以上月大，列表分析：

根據(jù)上面圖表分析可知：

下月“一月大”的兔子數(shù)量等于上月“2月大”+上月“>=3月大”的兔子數(shù)量；

下月“二月大”的兔子數(shù)量等于上月“一月大”的兔子數(shù)量；

下月“>=3月大”的兔子數(shù)量等于上月“二月大”+上月“>=3月大”的兔子數(shù)量；

既然分析完問題，代碼就很簡單了：

/// <summary>/// 遞推（正推）計算兔子的數(shù)量/// </summary>public static void ShowRabbitsCount() {    int oneMonthCount = 1;    int twoMonthCount = 0;    int threeOrMoreMonthCount = 0;    for (int month = 2; month <= 12; month++)    {       //臨時存儲上月各種兔子數(shù)量       int PReOneMonthCount = oneMonthCount;       int preTwoMonthCount = twoMonthCount;       int preThreeOrMoreMonthCount = threeOrMoreMonthCount;       //更新本月各種兔子的數(shù)量       oneMonthCount = preTwoMonthCount+preThreeOrMoreMonthCount;       twoMonthCount = preOneMonthCount;       threeOrMoreMonthCount += preTwoMonthCount;       Console.WriteLine(string.Format("第 {0} 個月兔子的總數(shù)為：{1}", month, oneMonthCount + twoMonthCount + threeOrMoreMonthCount));    }}
運(yùn)行結(jié)果：
 
下面再看一個逆推的例子：
假設(shè)有一個人從1月份開始到本年12月初時體重減少到150斤，他每個月增加的體重為當(dāng)月初體重的2%，每月鍛煉減少的體重為10斤（這里也按這10斤是月底突然減掉的），計算此人一月初時的體重。
根據(jù)問題分析：
12月初的體重為150斤，然后： 本月初體重+10=上月初體重*1.02
/// <summary>/// 遞推（逆推）計算開始時的體重/// </summary>public static void ShowWeight(){    double endWeight = 150;    double perMonthReduce = 10;    for (int month = 11; month > 0; month--)    {        double preStartWeight = (endWeight + perMonthReduce) / 1.02;        endWeight = preStartWeight;        Console.WriteLine(string.Format("第 {0} 個月的開始體重為：{1}", month, preStartWeight));    }}
運(yùn)行結(jié)果：