2.1 递归解决方案（2）
上面的查找策略将使查找单词的问题范围缩减到半本词典，如图2-1所示。此处要注意两个要点。首先，一旦将词典分成两部分，就会知道怎样继续在其中一半查找：使用与查找整本词典相同的策略，再查找下一个中间页。其次，要注意存在特殊情况：经过多次折半查找，最后只剩一页未查，无法继续分割。在此情况下，问题的规模非常小，可以直接在所余单页中查找单词。这种特殊情况就是所谓的基例(base case，也称基本实例或退化实例)。
注释：基例是一种特殊情况，其解决方案已知
这是一种分而治之的策略。首先将词典分成两半，然后操作正确的一半，从而解决词典查找问题。通过相同的分而治之策略解决更小的问题，划分将一直进行，直至到达基例。您将会看到，这是很多递归解决方案的固有策略。
注释：折半查找使用分而治之的策略
为进一步探讨词典问题解决方案的本质，请看下面稍微严格一些的描述：
- search(aDictionary: Dictionary, word: string)
- if (aDictionary is one page in size)
- Scan the page for word
- else
- {
- Open aDictionary to a point near the middle
- Determine which half of aDictionary contains word
- if (word is in the first half of aDictionary)
- search(first half of aDictionary, word)
- else
- search(second half of aDictionary, word)
- }
把这个解决方案编写成一个函数，可观察到几个非常重要的问题：
1. 这个函数的一个操作是调用自身。也就是说，函数search调用函数search。这个操作就形成了递归。该方案的策略是将aDictionary分成两半，并确定哪一半包含单词word，再将相同策略应用于包含单词的一半。
2. 每次在函数search中递归调用函数search时传递的词典范围是上次递归的一半。换句话说，每调用函数search(aDictionary, word)一次，aDictionary的大小就减半。该函数通过解决另一个本质相同但规模更小的查找问题，解决了初始的问题。
3. 有一个查找问题的处理方式不同于其他所有问题。当aDictionary仅含一页时，就使用另一种技术：在该页直接查找单词。查找单页是查找问题的基例。当到达基例时，递归调用停止并直接解决问题。
4. 问题规模不断减小的方式确保了最终能到达基例。
注释：递归函数调用自身
每次递归调用都会解决一个同类但是规模较小的问题
测试基例使得递归调用能够停止
最后，某个较小的问题必然是基例
上面描述了递归解决方案的一般形式。并不是所有递归解决方案都如上例一样完全符合这些标准，但是相似性远大于差异性。当试图创建递归解决方案时，要牢记以下4个问题。
提示：创建递归解决方案的4个问题
1. 怎样根据同类型的更小问题来定义问题？
2. 每次递归调用是如何减小问题规模的？
3. 哪个问题实例可用作基例？
4. 随着问题规模的减小，最终能否到达基例？
现在来看两个相对简单的问题：计算数字的阶乘和逆置字符串。这些递归解决方案进一步阐明了词典查找问题所引出的要点，同时演示了返回值的递归值函数和递归void函数之间的区别。