递推法

“琦琦养了1对小兔子，2个月之后小兔子就具备了繁殖能力，算是‘成年兔了。假设成年兔每个月生育1对幼崽，且兔子们都健康地活着，那么100个月后，一共生出了多少对大大小小的兔子呢？”岭童小子一边念题目，一边抓脑袋——计算量这么大，啥时候才能算出来呀！

面对难题，他没有放弃，而是继续思考：1个月后幼崽1对，成年兔0对，兔子一共只有1对。2个月后幼崽刚成年，还不能生育小兔子，此时幼崽0对，成年兔1对，兔子总数为1对。3个月后，成年兔生育出1对幼崽，兔子总数为2对……

算到这里，岭童小子开始“晕”了。

“能不能请星空帮忙呢？他的特点不就是运算速度快吗？”岭童小子一边嘟哝着一边看向星空。星空默不作声地看着他，似乎在说：“你怎么才想到我呀！”

有了小帮手，岭童小子立刻拿出草稿纸，开始列表分析。

咦！岭童小子从表格里发现了一个有趣的现象：从第3个月开始，每个月的兔子总数是前面2个月兔子总数的和。有办法了！按捺住内心的激动，岭童小子开始敲打键盘——编程开始了！

时间一分一秒地过去，岭童小子一点儿都不觉得累，终于——

“嘿嘿，我真聪明！一下子就计算出了兔子100个月后的总数。而且，不管你想知道哪个月的兔子总数，我都可以随时告诉你！咱编写的程序就是这么牛！”岭童小子得意极了。

哈哈，嶺童小子真聪明，还会用表格分析数据。

从初始的一个或若干个数据出发，通过递推关系逐步推进，从而得到最终结果，这种求解问题的方法叫“递推法”。在递推问题中，每个数据都和它前面或后面的若干个数据有一定关联，这种关联可以通过“递推关系式”来表示。

岭童小子列出了每个月的兔子总数分别为：1、1、2、3、5、8、13、21、34……从中可以看出，它的递推关系式为：当月兔子总数=上个月的兔子总数+上上个月的兔子总数。

从第三项开始，每一项都是前两项的和，这就形成了一个著名的数列——斐波那契数列。在编写程序时，我们需要用到列表，用来存放每个月的兔子总数。岭童小子很聪明，建立了一个名为“当月兔子总数”的列表。

第一步，将第1个月的兔子数量1加入“当月兔子总数”这个列表中。代码见图1。

第二步，将第2个月的兔子数量1继续加入“当月兔子总数”这个列表中。代码见图2。

第三步，把上个月的兔子总数与上上个月的兔子总数相加，将它们的和加入“当月兔子总数”这个列表里。代码见图3。

将第三步循环，一步一步递推，直到你需要知道的月份为止。这样，我们就能得到最终的结果。

同学们，你们看懂了吗？扫描下方的小程序码，看看长沙市芙蓉区马坡岭小学的优秀作品吧！

曹晓敏：湖南省特级教师，湖南省优秀科技辅导员，长沙市首批卓越教师，长沙市骨干教师，长沙市芙蓉区马坡岭小学信息技术教师。