C++抽象编程——递归简介（1）

        最近看了递归，看得我头皮发麻，石乐志。所以就找个时间把所学都总结整理一下。所有的都是学自《PRogramming abstraction in C++》. 大多数的用来解决编程的算法策略都有不在计算领域的计算部分。当我们重复完成一个任务的时候，我们通常考虑的是循环。当我们做某项界定的时候，我们通常考虑的是条件控制语句。用的最多的就是 if  while还有for语句了。在你解决更多问题之前，你得学会一项强大的解决问题的策略跟工具。这个策略就是我们的递归策略。递归，就是定义为一种把大问题通过分割到含有同样形式的小问题的一种策略。（That strategy, called recursion, is defined as any solution technique in which large problems are solved by reducing them to smaller problems of the same form）。递归是一种新的思考问题的方式，对初学者来说，很难，想学好就要多练习，多理解。

     7.1 A simple example of recursion（递归例子）

        为了更好的理解递归，我们最好就举个实际的例子。试想一下。你被任命为基金组织的协助者，在为一个志愿者很多，但是资金缺乏的组织工作，你的任务是筹集$1,000,000用于捐赠。

当然，如果你认识哪个大款肯给你出这笔钱，问题就变得很简单了。但是这样的几率几乎为0. 那么怎么实现这个目标呢？在这里，我们可以尝试把要筹的款的账目适当降低，比如每个人出100，这样如果你有10,000个朋友就能完成目标。但是你又可能没那么多个朋友，那么我们可以换个思路。你是基金的负责人，我们说了，你的自愿者很多，你可以找10个志愿者小组的组长，向他们每个人要100,000，然后他们通过同样的方式向下属要10,000，......  直到每个人的手中都可以支付起100的时候，就任务完成。那么我们用伪代码（pseudocode）的形式表示就是：

void collectContributions(int n) {if (n <= 100) {Collect the money from a single donor.} else {Find 10 volunteers.Get each volunteer to collect n/10 dollars.Combine the money raised by the volunteers.}}

Get each volunteer to collect n/10 dollars.这一步直接就是把钱缩小了10倍，接下来的步骤都是一样，向接下来的10个人筹钱，唯一不同的就是，n每次都缩小10倍。这时候我们可以很轻松的写出这一行的代码了：
collectContributions(n / 10)；当然，在这里要记住，n<=100的时候，说明每个人都是可以筹齐100的，就没有必要再向接下来的10个人筹款，也就是说，不用再调用
collectContributions(n / 10)；
直接执行 if 里面的语句。
上面的例子结构是一个很典型的递归的结构例子，一般的递归函数结构都含有一下的结构组成
if (test for simple case) {Compute a simple solution without using recursion.} else {Break the problem down into subproblems of the same form.Solve each of the subproblems by calling this function recursively.Reassemble the subproblem solutions into a solution for the whole.}上面是递归函数的模板，我们称之为递归范式（recursive paradigm）。注意，if 里面是simple cases，就是说这部分内容不含递归的部分，也可以看做是递归的边界，以后会很经常看到它，这个很重要。也可以理解为数学中的特殊例子
当问题满足了以下的一些特点时，我们可以考虑使用递归
1. You must be able to identify simple cases for which the answer is easily determined.2. You must be able to identify a recursive decomposition that allows you to break any complex instance of the problem into simpler problems of the same form.
也就是说，问题能区分出我们的simple cases，并且能将问题递归分解为更小的含有同样形式的函数。
在上叙述的问题中，原始的问题通过将问题分成了更小的子问题，这些小问题都是跟原始问题是同种的形式。这样的解决问题的递归方法，我们称之为分离—组合算法。这是我自己的理解翻译的，我也不知道专业术语是不是这样的。（Because the solution depends on dividing hard problems into simpler instances of the same problem, recursivesolutions of this form are often called divide-and-conquer algorithms）
这里先提到递归的主要形式，接下来就会提到具体递归的原理跟调用过程。先这样，晚上再写（2）。纯手写，就是我翻译得可能太差，毕竟没有中文版...