2.6  更多示例

下面的3个问题需要计算特定事件，或者将事件或事物组合。这些问题可以很好地说明具有多个基例的递归解决方案。然而，这些解决方案的效率相当低下，因此并不实用。不要为其效率感到沮丧，递归可以很有用并有效，虽然并非总是如此。当前的目标是通过解决简单的问题来理解递归。

2.6.1  Fibonacci数列(兔子繁殖)

兔子繁殖速度极快。若兔子不会死，其数量将很快无法控制。最近通过对随机选择的兔子进行研究，我们假定以下"事实"：

兔子不会死。

兔子在出生后两个月性成熟，也就是性成熟从它出生后第三个月开始。

兔子总是雄性和雌性配对而生。在每月初，每对性成熟的雄雌兔子产一对雄雌兔子。

假设开始时只有一对刚出生的雄雌兔子。在6个月后(包括第6个月之初产出的兔子)，共有多少对兔子？6是一个相对较小的数，因此计算比较容易。

第1个月：1对，最初的1对兔子。

第2个月：仍1对，因为这一对尚未性成熟。

第3个月：2对，最初一对已性成熟，并产出第2对。

第4个月：3对，最初一对又产1对，上月初产的1对尚未性成熟。

第5个月：5对，第3个月时的所有兔子(2对)都已性成熟，产出2对；加上第4个月时的兔子(3对)，共5对。

第6个月：8对，第4个月时的兔子产出3对，再加上第5个月时的5对，共8对。

现在创建一个计算rabbit(n)(第n个月的兔子对数)的递归解决方案。在此必须确定如何用rabbit (n-1)来计算rabbit(n)。注意，rabbit(n)是第n个月开始前的兔子对数加上第n个月初产出的兔子对数。在第n个月开始前，兔子对数为rabbit(n-1)。在第n个月初，并不是所有rabbit(n-1)对兔子都性成熟。只有那些在n -2个月存在的兔子才能在第n个月初产出兔子。也就是说，在第n个月初产出的兔子对数是rabbit(n-2)。于是得到递归关系：

rabbit(n) = rabbit(n-1) + rabbit(n-2) 

注释：第n个月兔子的数量

图2-18演示了这种关系。

这一递归关系与前面的示例类似，可以通过解决相同类型的多个较小问题来解决某个问题。这在概念上不难理解，但在选择基例时必须谨慎。很容易认为rabbit(1)应是问题基例，因为根据问题的表述，rabbit(1)的值为1。但rabbit(2)情况如何？将前面的递归定义应用于rabbit(2)，将得到：

rabbit(2) = rabbit(1) + rabbit(0) 

递归定义要求指定第0个月的兔子对数，但这是一个未定义的值。

一种可行的解决方案是将rabbit(0)定义为0，但这过于牵强。一个更好的选择是将rabbit(2)本身看成值为1的特例。这样，递归定义就有两个基例，即rabbit(2)和rabbit(1)。如下所示。

注释：由于存在两个较小的问题，因此需要两个基例

rabbit(1)、rabbit(2)和rabbit(3)等数字序列恰好是Fibonacci数列。该数列是很多自然现象的模型。

根据上述定义，很容易编写出计算rabbit(n)的C++函数。

/** Computes a term in the Fibonacci sequence.  
@pre  n is a positive integer.  
@post  None.  
@param n  The given integer.  
@return  The nth Fibonacci number. */  
int rabbit(int n)  
{  
if (n <= 2)  
return 1;  
else // n > 2, so n - 1 > 0 and n - 2 > 0  
return rabbit(n - 1) + rabbit(n - 2);  
}   // end rabbit 

注释：rabbit计算Fibonacci数列，但是效率并不高

在实际应用中会使用这个函数吗？图2-19显示了rabbit(7)生成的递归调用。试想rabbit(10)生成的递归调用会有多少？总之，函数rabbit的效率不高。因此，对于较大的数值n并不适用。本章最后将进一步讨论这个问题，到时候将介绍根据相同递归关系生成高效解决方案的一些技术。

提示：重复计算某些值的递归解决方案效率相当低。在此情况下，迭代要优于递归。