递归

在递归中，每次嵌套调用都会让函数体生成自己的局部变量，正好可以用来保存不同状态下的数值，为我们省去了大量中间变量的操作，极大地方便了设计和编程。

如何把复杂的问题简单化？

初始状态，也就是 n=1 的时候，命题是否成立；

如果 n=k-1 的时候，命题成立。那么只要证明 n=k 的时候，命题也成立。其中 k 为大于 1 的自然数。

假设 n=k-1 的时候，问题已经解决（或者已经找到解）。那么只要求解 n=k 的时候，问题如何解决（或者解是多少）；

初始状态，就是 n=1 的时候，问题如何解决（或者解是多少）。

复杂的问题，每次都解决一点点，并将剩下的任务转化成为更简单的问题等待下次求解，如此反复，直到最简单的形式。

递归和循环其实都是迭代法的实现，而且在某些场合下，它们的实现是可以相互转化的。但是，对于某些应用场景，递归确很难被循环取代。主要有两点原因：

第一，递归的核心思想和数学归纳法类似，并更具有广泛性。这两者的类似之处体现在：将当前的问题化解为两部分：一个当前所采取的步骤和另一个更简单的问题。

一个当前所采取的步骤。这种步骤可能是进行一次运算（例如每个棋格里的麦粒数是前一格的两倍），或者做一个选择（例如选择不同面额的纸币），或者是不同类型操作的结合（例如今天讲的赏金的案例）等等。
另一个更简单的问题。经过上述步骤之后，问题就会变得更加简单一点。这里“简单一点”，指运算的结果离目标值更近（例如赏金的总额），或者是完成了更多的选择（例如纸币的选择）。而“更简单的问题”，又可以通过嵌套调用，进一步简化和求解，直至达到结束条件。

归并排序中的分治思想

归并排序算法的核心就是“归并”，也就是把两个有序的数列合并起来，形成一个更大的有序数列。

将长度为 n 的数列，每次简化为长度为 n-1 的数列，直至长度为 1。

分而治之，我们通常简称为分治。它的思想就是，将一个复杂的问题，分解成两个甚至多个规模相同或类似的子问题，然后对这些子问题再进一步细分，直到最后的子问题变得很简单，很容易就能被求解出来，这样这个复杂的问题就求解出来了。

归并排序通过分治的思想，把长度为 n 的数列，每次简化为两个长度为 n/2 的数列。这更有利于计算机的并行处理，只需要 log2n 次归并。

假设初始的数组为{7, 6, 2, 4, 1, 9, 3, 8, 0, 5}，我们要对它进行从小到大的排序。

第一次分解后，变成两个数组{7, 6, 2, 4, 1}和{9, 3, 8, 0, 5}。

然后，我们将{7, 6, 2, 4, 1}分解为{7, 6}和{2, 4, 1}，将{9, 3, 8, 0, 5}分解为{9, 3}和{8, 0, 5}。

如果细分后的组仍然多于一个数字，我们就重复上述分解的步骤，直到每个组只包含一个数字。到这里，这些其实都是递归的嵌套调用过程。

然后，我们要开始进行合并了。我们可以将{4, 1}分解为{4}和{1}。现在无法再细分了，我们开始合并。在合并的过程中进行排序，所以合并的结果为{1,4}。合并后的结果将返回当前函数的调用者，这就是函数返回的过程。

重复上述合并的过程，直到完成整个数组的排序，得到{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

归并排序使用了分治的思想，而这个过程需要使用递归来实现。

归并排序算法用分治的思想把数列不断地简化，直到每个数列仅剩下一个单独的数，然后再使用归并逐步合并有序的数列，从而达到将整个数列进行排序的目的。

在单台机器上实现归并排序的时候，我们只需要在递归函数内，实现数据分组以及合并就行了。而在多个机器之间分配数据的时候，递归函数内除了分组及合并，还要负责把数据分发到某台机器上。

数据分割和映射

分割是指将数据源进行切分，并将分片发送到 Mapper 上。映射是指 Mapper 根据应用的需求，将内容按照键 - 值的匹配，存储到哈希结构中。这两个步骤将大的数据集合切分为更小的数据集，降低了每台机器节点的负载，因此和分治中的问题分解类似。不过，MapReduce 采用了哈希映射来分配数据，而普通的分治或递归不一定需要。

归约

归约是指接受到的一组键值配对，如果是键内容相同的配对，就将它们的值归并。这和本机的递归调用后返回结果的过程类似。不过，由于哈希映射的关系，MapReduce 还需要洗牌的步骤，也就是将键 - 值的配对不断地发给对应的 Reducer 进行归约。普通的分治或递归不一定需要洗牌的步骤。

合并

为了提升洗牌阶段的效率，可以选择减少发送到归约阶段的键 - 值配对。具体做法是在数据映射和洗牌之间，加入合并的过程，在每个 Mapper 节点上先进行一次本地的归约。然后只将合并的结果发送到洗牌和归约阶段。这和本机的递归调用后返回结果的过程类似。

总结

分治主要就是用在将复杂问题转化为若干个规模相当的小问题上。分治思想通常包括问题的细分和结果的合并，正好对应于递归编程的函数嵌套调用和函数结果的返回。细分后的问题交给嵌套调用的函数去解决，而结果合并之后交由函数进行返回。所以，分治问题适合使用递归来实现。同时，分治的思想也可以帮助我们设计分布式系统和并行计算，细分后的问题交给不同的机器来处理，而其中的某些机器专门负责收集来自不同机器的处理结果，完成结果的合并。