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

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

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

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

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

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

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

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

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

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

既然分析完問(wèn)題，代碼就很簡(jiǎn)單了：

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