1.递归和分治-灵析社区

递归是编程技巧，直接体现在代码上，即函数自己调用自己；在调用的函数执行完毕之后，程序会回到产生调用的地方，继续做一些其他事情。调用的过程被称作为递归，返回的过程被称作为回溯。
分治是一种算法设计的思想，将大问题分解成多个小问题，例如归并排序将大问题：「排序整个数组」，分解为小问题：「排序左半和右半」；绝大部分情况下「分治算法」通过「递归」实现。即：子问题的求解通过递归方法实现。

算法和数据结构并不是凭空想象出来的，「递归」函数也不例外。「递归」函数基于「自顶向下」拆分问题，再「自底向上」逐层解决问题的思想设计而成，这是所熟知的「分而治之」的算法思想。

分而治之（Divide-and-Conquer）的思想分为如下三步：

这样的三步恰好与递归的程序写法相吻合：

拆分：即对当前的大问题进行分析，写出相应代码，分解为子问题。

解决：即通过递归调用解决子问题；

合并：即在回溯的过程中，根据递归返回的结果，对子问题进行合并，得到大问题的解。

因此，分治算法一般通过递归实现。

更加形象的一种说法是：一开始我们只有一个问题，我们通过分治，将其分解成多个问题，发散开来，“自顶向下”走出去。在解决完子问题之后，在回溯的过程中合并子问题的解，将发散开来的问题合并成一个，“自底向上”走回来。

典型的分治思想的应用是：归并排序、快速排序、绝大多数「树」中的问题（先把原问题拆分成子树的问题，当子树中的问题解决以后，结合子树求解的结果处理当前结点）、链表中的问题。我们在本教程里不对「分治思想」展开叙述。

「分治思想」的特例是「减治思想（Decrease-and-Conquer）」：每一步将问题转换成为规模更小的子问题。「减治思想」思想的典型应用是「二分查找」「选择排序」「插入排序」「快速排序」算法。「分治」与「减治思想」的区别如下：

分治思想：将一个问题拆分成若干个子问题，然后再逐个求解，根据各个子问题得到的结果得到原问题的结果；
减治思想：在拆分子问题的时候，只将原问题转化成一个规模更小的子问题，因此子问题的结果就是上一层原问题的结果，每一步只需要解决一个规模更小的子问题，相比较于「分治思想」而言，它没有「合并」的过程。

使用「递归」的思想解决问题的方案是：从「结果」推向「源头」，再从「源头」返回「结果」。我们以计算 5! 为例向大家解释什么是「自顶向下」地解决问题。

下面的幻灯片演示了使用「递归」方法「自顶向下」地计算 5! 的步骤。编程语言在执行计算的过程中，使用了数据结构「栈」。

在计算 5! 的过程当中，需要记录拆分的过程当中的每一个子问题，并且在求解每一个子问题以后，逐层向上汇报结果。后拆分的子问题先得到了解决，整个过程恰好符合「后进先出」的规律，因此需要借助的数据结构是「栈」。

使用「递归」实现的算法需要走完下面两条路径：

因此使用「递归」函数解决的问题如上图所示，有「先走出去，再走回来」的过程。