Python经典编程习题100例：第11例：古典兔子问题

兔子问题是一个经典的递归问题，它提出了这样一个场景：一对兔子在一个月内可以生出一对小兔子，并且每个月都会生出新的一对小兔子。如果兔子不会死亡，那么一年后一共有多少对兔子？

这个问题可以用递归的方式解决。假设我们有一个函数 rabbit(n)，它表示在n个月后有多少对兔子。那么，我们可以建立如下的递归关系：

1. 在第一个月，有一对初生的兔子，所以 rabbit(1) = 1。
2. 在第n个月，兔子对数等于第n-1个月和第n-2个月的兔子对数之和，因为每对兔子每个月都会生出一对新的兔子。所以 rabbit(n) = rabbit(n-1) + rabbit(n-2)。

下面是用Python实现的代码：

def rabbit(n):
if n == 1 or n == 2:
return 1
else:
return rabbit(n-1) + rabbit(n-2)

在这个函数中，我们首先检查输入的月份数。如果月份数是1或2，我们直接返回1，因为一对初生的兔子就是我们的基准情况。如果月份数大于2，我们就递归地调用 rabbit(n-1) 和 rabbit(n-2)，并将这两个结果相加。这就是我们的递归关系。

请注意，这个函数会重复计算很多结果，因为 rabbit(n-1) 和 rabbit(n-2) 都会被多次计算。在实际应用中，我们通常会使用动态规划来避免这种重复计算。

接下来，我们可以调用这个函数来计算一年后有多少对兔子：

rabbit(12)

这个函数将返回一年后有多少对兔子。

请注意，由于这是一个递归问题，对于较大的输入值，这个函数可能会运行得非常慢。在实际应用中，我们通常会使用动态规划或其他方法来更有效地解决这个问题。

另外，这个问题还可以用数学公式来解决。一年后（12个月后）的兔子总数是一个斐波那契数列的第13项，这个数列的通项公式是 F(n) = (1/sqrt(5)) * ((sqrt(5)/2)^n - (-sqrt(5)/2)^n)。这个公式可以用来快速计算出一年后有多少对兔子。

无论使用哪种方法，都可以通过编程来解决这个问题。希望这个例子能帮助你理解如何使用递归来解决实际问题。