遞推法

“琦琦養了1對小兔子，2個月之后小兔子就具備了繁殖能力，算是‘成年兔了。假設成年兔每個月生育1對幼崽，且兔子們都健康地活著，那么100個月后，一共生出了多少對大大小小的兔子呢？”嶺童小子一邊念題目，一邊抓腦袋——計算量這么大，啥時候才能算出來呀！

面對難題，他沒有放棄，而是繼續思考：1個月后幼崽1對，成年兔0對，兔子一共只有1對。2個月后幼崽剛成年，還不能生育小兔子，此時幼崽0對，成年兔1對，兔子總數為1對。3個月后，成年兔生育出1對幼崽，兔子總數為2對……

算到這里，嶺童小子開始“暈”了。

“能不能請星空幫忙呢？他的特點不就是運算速度快嗎？”嶺童小子一邊嘟噥著一邊看向星空。星空默不作聲地看著他，似乎在說：“你怎么才想到我呀！”

有了小幫手，嶺童小子立刻拿出草稿紙，開始列表分析。

咦！嶺童小子從表格里發現了一個有趣的現象：從第3個月開始，每個月的兔子總數是前面2個月兔子總數的和。有辦法了！按捺住內心的激動，嶺童小子開始敲打鍵盤——編程開始了！

時間一分一秒地過去，嶺童小子一點兒都不覺得累，終于——

“嘿嘿，我真聰明！一下子就計算出了兔子100個月后的總數。而且，不管你想知道哪個月的兔子總數，我都可以隨時告訴你！咱編寫的程序就是這么牛！”嶺童小子得意極了。

哈哈，嶺童小子真聰明，還會用表格分析數據。

從初始的一個或若干個數據出發，通過遞推關系逐步推進，從而得到最終結果，這種求解問題的方法叫“遞推法”。在遞推問題中，每個數據都和它前面或后面的若干個數據有一定關聯，這種關聯可以通過“遞推關系式”來表示。