问题描述

有一对兔子，从出生后的第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子，假设所有的兔子都不死，问30个月内每个月的兔子总对数为多少？

分析

原书直接告诉读者本题的的结果是斐波那契数列，然后就将重点放在了如何用Python打印出斐波那契数列上面，这就好比直接把答案抛出，却未做更多解释——这也让问哥产生了要为本书重新编写所有案例的想法。但为什么是斐波那契数列呢？原书通过把每个月所有兔子的数量列出来进行观察，判断出这是斐波那契数列。但是，问哥觉得这样做未免有点本末倒置了，如果需要先把答案手工算出，再去想如何用程序去优化计算过程，那我们的计算机思维何在？

看到题目，问哥首先想到的就是递归，每个月兔子生下的子兔子，还会在两个月后再生下孙兔子，子子孙孙的数量要加在一起。符合递归的特征：

1. 有终止条件——30个月
2. 不断重复相似的计算——每对新出生的兔子两个月后（第三个月开始）又会繁殖新兔子
3. 初始条件不同——从第三个月开始，每个月都有新出生的兔子，相对这些新出生的兔子而言，它们的初始条件是不一样的

由于最终我们要返回的不是某个月存活的兔子总量（那样更简单一点），而是要列出30个月里每个月的兔子数量，换句话说，是一个包含30个数字的列表。于是这时我们可以决定要定义的递归函数的返回值是一个列表。

可以这样认为，递归函数代表了一对兔子，它们自出生那个月开始，每个月都存在，也就是说，如果是第一对兔子（祖兔子），不考虑后代的话，它们返回的应该是全为1的列表——代表30个月，每个月都有1对兔子。——此为函数的第一步。

但是由于从第三个月开始，这对兔子会繁殖一对新兔子（子兔子），就代表产生了一次递归调用。而这对子兔子（递归函数）返回的也是列表，只不过列表的长度是28——因为它们是从第3个月开始计算到第30个月，类似地，第四个月该对兔子又会繁殖一对新兔子，但返回的列表长度只有27，以此类推。——此为函数的第二步。

最后假设，这第一对子兔子也没有繁殖，那它们返回的应该是全为1的、长度为28的列表，但是我们最终是要得到的是每个月的总数，所以我们还是要把这个返回的列表里的数量加到祖兔子的列表里，所以我们需要遍历子兔子的列表，从祖兔子的列表第3个元素开始，依次累加。而第二对子兔子返回的长度为27的列表也要累加进去，以此类推。——此为函数的第三步，也是最重要的一步。

然而，事实是，在得到结果之前，子兔子还会繁殖孙兔子，于是在返回列表之前，还需要在第二步的时候继续向下递归，以期得到孙兔子的列表，同样的，长度递减。

于是就这样子子孙孙调用下去，直到第30个月，遍历结束，返回的列表长度为0，然后递归返回，一层一层向上累加，直到祖兔子。

代码实现如下：

def rabbit(month:int)->list:r = [1]*month # 这对兔子在每个月都要被计算在内for m in range(2,month): # 从第3个月开始，要加上子兔子，以及这些兔子在未来繁殖的兔子arr = rabbit(month-m) # 接收递归返回，列表长度递减for i in range(len(arr)):r[m+i]+=arr[i] # 加上子兔子及孙兔子及所有后代在每个月的数量return rprint(rabbit(30))

输出结果

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]

从结果可以看出，答案确实是斐波那契数列。但和原书不同的是，至少我们现在明白了这些数字是怎么计算出来的，然后才可以思考如何更快地得到斐波那契数列。换句话说，如果问题的条件是每对兔子在第四个月才可以繁殖新兔子，那应该怎样得到结果呢？

关于如何得到斐波那契数列，已经有太多例子了，这里不过多探讨，简要把代码列出。

a = b = 1
fib = [a]
while len(fib)<30:fib.append(b)a,b = b,a+b
print(fib)