2.4  递归与数组

递归与数组

当使用数组时，递归是实用而强大的工具。我们将数组内容的逆置作为第一个示例，随后将关注涉及在数组中查找的几个问题。

2.4.1  逆置数组项

这个问题的解决方案与2.3.1节的第一个解决方案非常相似，在那里我们将字符串逆置。可以编写如下所示的伪代码：
 

writeArrayBackward(anArray: char[])  
if (the array is empty)  
Do nothing -this is the base case  
else  
{  
Write the last character in anArray  
writeArrayBackward(anArray minus its last character)  
} 

如何将anArray的最后一个字符去掉并将其传递给writeArrayBackward？可以传递数组中剩余字符的数量。在每次递归调用的时候，会将这个值减小1。另一种做法是传递最后一个字符的索引。也就是说，如果该索引为last，writeArrayBackward将对数组anArray[0..last]1执行操作，即anArray[0]到anArray[last]。递归调用将对子数组anArray[0..last-1]执行操作。这一思想更常见的版本是还传递第一个数组字符的索引。因此无须将这个索引假定为0，可以向writeArrayBackward传递数组anArry[first..last]。

函数writeArrayBackward的代码如下所示：
 

/** Writes the characters in an array backward.  
@pre  The array anArray contains size characters, where size >= 0.  
@post  None.  
@param anArray  The array to write backward.  
@param first  The index of the first character in the array.  
@param last  The index of the last character in the array. */  
void writeArrayBackward(const char anArray[], int first, int last)  
{  
if (first <= last)  
{  
// Write the last character  
cout << anArray[last];  
// Write the rest of the array backward  
writeArrayBackward(anArray, first, last - 1);  
}   // end if  
// first > last is the base case - do nothing  
}   // end writeArrayBackward 

问题4 在前面的writeArrayBackward定义中，当first的值超过last的值时，为什么会到达基例。

问题5 编写一个递归函数，计算并返回数组中前n个(n ≥ 1)实数的乘积。

问题6 说明上个问题中的函数是如何满足递归函数标准的。

问题7 编写一个递归函数，计算并返回数组anArray[first..last]中整数的乘积。