2.7  递归和效率

递归是强大的问题求解技术，常用来为最复杂的问题生成清晰的解决方案。与迭代解决方案相比，该方案易于理解和描述。通过使用递归，可以简洁明快地实现解决方案。

本章列举了大量示例，以帮助您进一步理解递归，从而能构建自己的递归解决方案。大多数例子都很简单。但遗憾的是，本章介绍的许多递归解决方案效率不高，并不实用。不过，递归函数binarySearch和solveTowers是例外，它们的效率很高2。

有些递归解决方案效率不高，原因有以下两点：

与函数调用相关的开销

一些递归算法本来就效率不高

注释：导致某些递归算法效率不高的原因

第一个因素不是递归函数特有的，而是普遍存在于各类函数。在C++和其他高级编程语言的大多数实现中，函数调用会导致开销增大。如前所述，每次函数调用都会生成一个活动记录，记录类似于箱式跟踪中的箱。递归函数扩大了这种开销，因为对函数的一次初始调用可生成大量递归调用。例如，调用factorial(n)生成n次递归调用。另一方面，由于递归调用的模块化，因此能够明确地阐明复杂程序，代码清晰带来的补偿往往超过额外开销导致的损失。

注释：递归可以将复杂的解决方案简单化

但不能滥用递归。例如在实际中，不应使用递归函数计算阶乘。有了本章开始给出的迭代定义，可编写出迭代阶乘函数。迭代函数几乎与递归函数同样清晰，但效率更高。若递归没有优势，则不必为使用递归而付出开销代价。总而言之，在简单迭代解决方案无法求解的情况下，递归才真正显出价值。

注释：如果递归解决方案效率不高并且存在清晰高效的迭代解决方案，则不要使用递归

有关递归和效率的第二点是一些递归算法的内在低效性。低效问题与上述问题大相径庭。它与编译器如何实现递归函数没有任何关系，而与算法使用的求解函数相关。

例如，回顾本章前面的兔子繁殖问题的递归解决方案。
 

注释：兔子繁殖问题的递归解决方案本身效率就不高

图2-19演示了rabbit(7)的计算。前面曾提过一个问题：若计算rabbit(10)，递归图会怎样？分析这个问题可知：图将占据本章大多数空间。rabbit(100)又将如何？它将充满整个世界。

对于兔子繁殖问题，根本问题在于它反复计算同一个值。例如，由rabbit(7)的图可知，计算rabbit(3)达5次之多。若n变大，则许多值将重复计算近万亿次。由于计算次数过多，该解决方案不可行。即使每次计算仅需很少时间，总时间还是相当惊人。

递归关系并非一无是处。要解决兔子繁殖问题，一种方法是根据同一个递归关系构建迭代解决方案。迭代解决方案向前行，不后退，而且每个值只计算一次。可以用以下迭代函数来计算rabbit(n)，即使n值非常大也没有问题。
 

/** Iterative solution to the rabbit problem. */  
int iterativeRabbit(int n)  
{  
// Initialize base cases:  
int previous = 1;               // Initially rabbit(1)  
int current = 1;                    // Initially rabbit(2)  
int next = 1;                           // Result when n is 1 or 2  
// Compute next rabbit values when n >= 3  
for (int i = 3; i <= n; i++)  
{  
// current is rabbit(i - 1), previous is rabbit(i - 2)  
next = current + previous;          // rabbit(i)  
previous = current;                                 // Get ready for next iteration  
current = next;  
} // end for  
return next;  
}               // end iterativeRabbit 

注释：可以使用兔子繁殖问题的递归关系创建效率更高的迭代解决方案

所以，迭代解决方案比递归解决方案效率高。在有些情况下，更容易找出递归解决方案。因此，有时须将递归解决方案转换为迭代解决方案。若递归函数调用自身一次(而非多次)，则转换过程更容易。在确定函数是不是多次调用自身时，要认真分析。函数rabbit调用本身两次；但对于binarySearch函数，尽管C++代码中有两次调用，而实际上，该函数只调用自身一次。这两个调用出现在if语句中，只有其中之一会执行。

注释：如果递归解决方案容易发现但是迭代解决方案效率更高，则将递归转换为迭代

如果函数的最后一个操作是单个递归调用，那么将递归解决方案转换到迭代解决方案会更容易。这种情况称为尾递归(tail recursion)。例如，writeBackward函数使用一个尾递归，因为该函数的最后一个操作是递归调用。不要认为这是显而易见的，请看函数fact。虽然其递归调用出现在函数定义的最后，但fact的最后操作是乘。所以说，fact不是尾递归。

注释：尾递归函数

回顾writeBackward的定义：
 

void writeBackward(string s)  
{  
int length = s.size();  
if (length > 0)  
{  
// Write last character  
cout << s.substr(length - 1, 1);  
writeBackward(s.substr(0, length - 1)); // Write rest  
}   // end if  
}  // end writeBackward 

这个函数是尾递归，它最后的递归调用仅用修改了的参数重复函数的操作。可以用迭代来执行这个重复操作，这将更直接、更有效。writeBackward的迭代定义如下：
 

/** Iterative version. */  
void writeBackward(string s)  
{  
int length = s.size();  
while (length > 0)  
{  
cout << s.substr(length - 1, 1);  
length--;  
}           // end while  
} // end writeBackward 

注释：修改尾递归通常非常直接

由于尾递归函数比相应的迭代函数效率低，而且将尾递归函数转换为等效迭代函数的步骤很机械，因此一些编译器将尾递归自动替换为迭代。消除其他形式的递归要复杂些，但是如果有必要的话，还得去做。

有些递归算法(例如rabbit)本身效率不高，而另一些递归算法(例如折半查找3)则效率极高。在涉及算法分析的高级课程中，可了解到如何确定递归算法的相对效率。第10章将简要介绍一些此类技术。

第5章将继续讨论递归，分析一些有直接递归解决方案的难题。当然，本书其他章节也会用到递归。

问题11 判断下面这些在本章出现过的递归函数哪些是尾递归：fact、writeBackward、writeBackward2、rabbit、游行队伍问题中的P、getNumberOfGroups、maxArray、binary- Search和kSmall。