第2章 递归：镜子
本章内容
2.1 递归解决方案
2.2 返回值的递归
2.2.1 递归值函数：n的阶乘
2.2.2 箱式跟踪
2.3 执行动作的递归
2.4 递归与数组
2.4.1 逆置数组项
2.4.2 折半查找
2.4.3 查找数组中的最大值
2.4.4 查找数组中的第k个最小值
2.5 组织数据
2.6 更多示例
2.6.1 Fibonacci数列(兔子繁殖)
2.6.2 组织游行队伍
2.6.3 从n个事物中选出k个
2.7 递归和效率
本章小结
练习题
编程问题
预备知识
附录A 回顾C++基础
附录B 编程中的重要主题
附录C 统一建模语言
本章的目的是让您对递归有一个基本认识，递归是计算机科学家使用的最强大的问题求解技术之一。在学习本章内容前，不需要具备有关递归的任何知识。如果您已经掌握了递归方面的知识，那么可以根据需要回顾本章内容。
本章通过几个相对简单的问题，推演递归解决方案的思维过程。这些问题类型多样，包括计数、查找和组织数据。本章不仅从概念上分析递归，还讨论了有助于理解递归机制的技术。这些技术对跟踪和调试递归函数特别有用。
有些递归解决方案比最好的非递归方案都要简洁和灵活。例如，传统的Hanoi塔问题看起来很难，但若使用递归解决方案，则极其简单。不过有些递归解决方案效率极低，因此不提倡采用。
第5章将通过分析更复杂的问题来进一步讨论递归技术。在本书的其余章节，递归将在很多解决方案中扮演重要角色。
2.1 递归解决方案（1）
递归是极强大的问题求解技术。有些问题初看起来非常困难，但是使用递归解决方案经常很容易就可以解决。与其他问题求解技术类似，递归将一个问题分解为多个更小的问题。递归的惊人之处在于：这些小问题与初始问题的类型完全相同，即所谓的镜像。
注释：递归将问题分解为较小的同类问题
将一面镜子放在另一面镜子之前，让两面镜子彼此正对，将看到自己的很多重叠成像，而且后面的成像比前面的略小。递归就类似于这些镜像。换句话说，递归解决方案通过解决同类问题的较小实例来解决问题，之后通过解决同一问题的更小实例来解决新问题，依此类推。最终新问题变得非常小，其解决方案要么显而易见，要么已知。这将使初始问题得到解决。
例如，假定如果有问题P2的解决方案就可以解决问题P1，而P2是更小的P1实例。进一步假定如果能解决问题P3就能解决问题P2，而P3是P2的更小实例。若问题P3非常小，解决方案显而易见，那么就可以解决问题P2。然后利用P2的解决方案，可以解决原始问题P1。
乍一看，递归犹如魔术，但由后文可知，递归是一种非常重要并且实用的问题解决方法，是迭代技术之外的另一选择。迭代解决方案涉及循环。从一开始就应该知道，并非所有的递归方案都优于迭代方案。实际上，由于某些递归算法效率过低，因此很不实用。但是不管怎么样，递归都可以为非常复杂的问题提供简单灵巧的解决方案。
注释：某些递归算法效率不高，并不实用
为解释递归解决方案的基本原理，分析从词典中查找单词的问题。假设要查找单词vademecum。可以从词典第一页开始按顺序查找每个单词，直至找到vademecum为止。这种方法是顺序查找。很明显，需要用一种更快的方法来代替它。
注释：复杂问题可能有简单的递归解决方案
折半查找(binary search)就是一种更快的方法，这种方法类似于实际使用词典的方式。在词典中间页附近打开词典，大体看一下页面，判断要查找的单词在打开的前半部分还是后半部分。下面的伪代码首次尝试正式描述该过程：
- // Search a dictionary for a word by using a recursive binary search
- if (the dictionary contains only one page)
- Scan the page for the word
- else
- {
- Open the dictionary to a point near the middle
- Determine which half of the dictionary contains the word
- if (the word is in the first half of the dictionary)
- Search the first half of the dictionary for the word
- else
- Search the second half of the dictionary for the word
- }
注释：词典的折半查找
该解决方案有意模糊了一些问题：如何浏览单个页面？怎样定位词典的中间页？一旦找到中间页，怎样确定单词在哪一半？这些问题不难回答，但是它们现在会使这个解决方案的策略变得不清楚。