本文专注于<递归算法和分治思想>

初衷：博主看到网上有很多人贴出各种OJ上的AC代码，很多都会标注上“递归”两字
我刚开始学习递归算法和分治法的时候，苦于没有人写出递归算法和分治法的详细解析,很难系统地学习
所以小博主冒然写一篇总结性的博文，希望可以帮助到更多的人，当然再强调下，只为像我一样的新人准备，AC牛神们可无视哈！
相信无论你是大牛还是和博主一样的新手，花上10几分钟看下来，肯定也会有一定的收获的！

写在前面：转载请注明出处！
作者：胖虎
CSDN博客地址：http://blog.csdn.net/ljphhj
如果你觉得现在走的辛苦，那就证明你在走上坡路！

本文的标题体现了本文主要要关注的知识点，我准备通过以下几部分来阐述我要说明的！


"算法基本介绍"->"典型案例分析讲解"->"笔试题、面试题的案例"

(本文介绍的所有算法实现代码，提供下载地址：http://download.csdn.net/detail/u011133213/7136981)

一、算法性质基本介绍（ps: 为没了解过递归算法和分治法的人提供，牛牛可略过！）


▲递归算法:


●递归算法的性质：
是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。


●递归算法的特点: 
1.调用自身 
2.必须有一个明确的递归结束条件（递归出口） 
3.递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
4.在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
（ps:3、4的特点即平时一般不推荐使用递归的原因）


●什么问题，我们可以用递归算法呢？
使用递归算法的要求:
1、每次调用在规模上都有所缩小（通常是减半（即分治)）
2、前一次处理要为后一次处理做准备(通常前一次的输出就作为后一次的输入)
3、在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。


▲分治思想：
●分治的基本思想：
是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。


●分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

●什么问题，我们可以用分治法呢？
使用分治法的要求:

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。

二、典型案例分析讲解

实际上更多的情况是分治思想和递归算法的结合，所以以下的一些典型案例就不具体划分！

▲依我现在了解比较典型的案例大概有：

求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题（回溯、递归）、棋盘覆盖（分治,递归）、Strassen矩阵乘法（分治）、最近点对问题(分治+递归)、循环赛日程表、凸包问题求解

(ps: 以上典型案例在后面都会讲解, 此博文持续更新哈，如果有哪位网友大神还有经典例子，希望留言哈！)


注意：以下有些算法用其他方式会有更好的效率，但是为了突出递归算法和分治思想，此博文中使用的方法将不会考虑到其他的更优的方法！


-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：求N的阶乘

题意：n! = n * (n-1) * (n-2) * ..... * 2 * 1
这便是个典型的递归的算法.设 f(n) 为求n的阶乘的函数,那么可以一个可以等价为 n * f(n-1)
而递归结束的条件为: n == 1时，求1!直接返回数值1


JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：欧几里德算法(求最大公约数)

题意：给出两个数m、n，求出两个数的最大公约数

JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：斐波那契数列

题意：斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

即F(0) = 0, F(1) = 1 为递归的终止条件

JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：汉诺塔问题（汉诺塔问题是经典递归问题）

题意：
有三个塔(分别为A号，B号和C号)。开始时．有n个圆形盘以从下到上、从大到小的次序叠置在A塔上。
现要将A塔上的所有圆形盘，借助B搭，全部移动到C搭上。且仍按照原来的次序叠置。 
移动的规则如下：
这些圆形盘只能在3个塔问进行移动.一次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比它小的盘子的上面。 


如图：


算法分析：
1.当n=1时，移动方式： A->C
2.当n=2时，移动方式:  A->B, A->C, B->C
3.当n=3时, 移动方式:  我们需要把上面两个2，借助C塔，移动到B塔上，然后把A塔的最大的盘移动到C塔，再借助A塔把B塔的两个盘移动到C塔（调用f(2)函数）


根据上面的列举，我们可以分析得到下面的解法.(通用性)


我们定义一个递归方法Hannoita(int N，char A，char B，char C)[这里的N代表移动的盘数，A表示盘子来源的塔，B表示移动时借助的塔，C表示盘子要移动到的目标塔]


设初始盘子个数为N
▲若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到C问题完全解决。
▲若A塔上有一个以上的盘子(N>1)，则进行如下操作：
1.先把(n-1)个盘子从A塔经过移动，叠放到B塔上。在不违反规则情况下，所有(N一1)个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。
2.用Hannoita(N-1，A, C，B)调用递归方法，注意：这里是借助于C塔，将(N一1)个盘子从A塔移动到B塔，A是源塔，B是目标塔。 
3.将剩下的第N个盘子(也就是最底下的一个)直接从A塔叠放到空着的C塔上。 
4.用第一步的方法，再次将B塔上的所有盘子叠放到C塔上。同样，这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的,用Hannoita(N一1，B，A，C)调用递归方法【注意：这里是借助于A塔，将(N—1)个盘子从B塔移动到C塔，B是源塔，C是目标塔】 


JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：二叉树的三种递归遍历方式

题意：二叉树的三种递归遍历方式,分别为先序遍历，中序遍历，后序遍历。我这里稍微讲下中序遍历的递归方式，其余的也一样哈


中序遍历：先遍历根节点的左子树，再遍历根结点，最后遍历根结点的右子树！
递归方式：我们会发现，当我们要遍历根结点的左子树的时候，根结点的left孩子，相当于左子树的根结点，那么遍历左子树又相当于调用了原来中序遍历的函数，同理遍历右子树也是！直接看代码的递归实现哈


JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。


快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：折半查找

题意：在一个有序的数组中，要查找一个值为key的数是否存在于这个数组中，我们用递归的思想可以把问题分解成两个小的子问题，然后再一直细分下去，直到找到这个值或者已经没办法往下分了，但是在数组中还没找到值等于key的数


在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
1）待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
2）待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。
3）待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值
4）如果最后找不到相等的值，则返回错误提示信息。


JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：图的遍历（DFS深度遍历/BFS广度遍历[非递归]）  

-------------------------------------------------------基本图知识
图的简单介绍：
▲图的二元组定义：
图G由两个集合V和E组成，记为：G=(V，E)
其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。

通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

-------------------------------------------------------基本图知识
▲有向图(若图G中的每条边都是有方向的，则称G为有向图(Digraph))
1、有向边的表示在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。
【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。


2、有向图的表示
  【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：
      V(G1)={v1，v2，v3}
      E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}
如图示：（图1）

-------------------------------------------------------基本图知识
▲无向图(若图G中的每条边都是没有方向的，则称G为无向图(Undigraph))
1、无向边的表示
无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
【例】无序对(vi，vj)和(vj，vi)表示同一条边。


2、无向图的表示
  【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：
    V(G2)={v1，v2，v3，v4}
    E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}
    V(G3)={v1，v2，v3，v4，v5，v6，v7}
    E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}
如图示：（图2）


注意：不考虑顶点到其自身的边。即若(v1，v2)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。
-------------------------------------------------------进入正题


算法思想：
先说明： 表示一个图的方法有好几种，我们这里采用邻接矩阵的方式来表示图。
▲图的邻接矩阵表示法:
在图的邻接矩阵表示法中：① 用邻接矩阵表示顶点间的相邻关系 Edges[图的顶点数][图的顶点数] ② 用一个顺序表来存储顶点信息 Vexs[图的顶点数]
【例】下图中无向图G5和有向图G6的邻接矩阵分别为Al和A2(图3)

▲DFS深度遍历:假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过（数组visited[index]的值置为"true"）。然后依次从v出发搜索v的每个邻接点w。若w未曾访问过（判断数组visited[index] ？= true），则以w为新的出发点继续进行深度优先遍历(递归调用)，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

▲BFS广度遍历:设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。

图的遍历JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：归并排序(稳定的排序方法)

题意：给出一个数组大小为N，通过分治法把它排成有序的数组，复杂度O(logN)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并，归并，按字面意思很容易理解，即通过 递归 + 合并（分治法）的排序方式


归并排序的JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：八皇后问题（回溯、递归）[详细讲解N皇后问题(超详细注释),讲解的时候以八皇后的问题来讲，实现的时候实现一个N皇后的JAVA代码]

▲八皇后问题的介绍


八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八


个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种解法！


▲八皇后问题算法思路：


用回溯的方法解决8皇后问题的步骤为：

1）从第一行开始，为皇后找到安全位置，然后跳到下一行

2）如果在第m行出现死胡同(找不到安全位置)，如果该列为第一行，棋局失败，否则后退到上一行，在进行回溯(找这一行的下一个满足的皇后位置)

3）如果在第8行上找到了安全位置，则棋局成功。（8行上全部的皇后不会打架了，就是一种解法）

8个皇后都找到了安全位置代表棋局的成功，用一个长度为8的整数数组SafeQueens[8]代表成功摆放的8个皇后，数组下标代表棋盘的row向量，而数组的值为棋盘的col向量，所以(row,col)的皇后可以表示为(SafeQueens[row] = col)

【这个问题的解法，博主会做一定的讲解，放在代码的注释里个人觉得会比较好】
N皇后的JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目: 棋盘覆盖（分治）

题意：在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4k种不同的棋盘，棋盘覆盖问题（chess cover problem）要求用图1(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。


图1：


图2：


如何应用分治法求解棋盘覆盖问题呢？
算法思想：分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。
当k>0时，可将2^k×2^k的棋盘划分为4个2^（k-1）×2^（k-1）的子棋盘，如图2(a)所示。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图2(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将


棋盘分割为1×1的子棋盘。（递归结束条件）


T(n)满足如下递推式：
T(n) = 1 当n=0时
T(n) = 4T(n-1) 当n>0时
解此递推式可得T(n)=O(4^n)


事先说明：
1、棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。在递归处理的过程中使用同一个棋盘。
2、子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标leftRow、leftCol和棋盘大小size表示。
3、特殊方格：用board[specialRow][specialCol]表示特殊方格，specialRow和specialCol是该特殊方格在二维数组board中的下标;
4、L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号,用type表示。

棋盘覆盖问题的JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：Strassen矩阵乘法（分治 + 递归）

Strassen矩阵乘法的复杂度t(n) = (nlog27)。因为log27 ≈2 . 8 1，所以与直接计算方法的复杂性(n3)相比，分而治之矩阵乘法算法有较大的改进。
题意：矩阵乘法是一种高效的算法可以把一些一维递推优化到log（ n )，还可以求路径方案等，所以更是是一种应用性极强的算法。矩阵，是线性代数中的基本概念之一。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。


我们来看看矩阵相乘的说明：
设A，B,C都为2*2的矩阵
那么求矩阵C = A*B，可写为
C11 = A11*B11 + A12*B21
C12 = A11*B12 + A12*B22
C21 = A21*B11 + A22*B21
C22 = A21*B12 + A22*B22
则共需要８次乘法和４次加法。
如果阶大于２，可以将矩阵分块进行计算。耗费的时间是O(nE3)。


要改进算法计算时间的复杂度，必须减少乘法运算次数。
按分治法的思想，Strassen提出一种新的方法，用７次乘法完成２阶矩阵的乘法，
算法如下：
M1 = A11 * (B12 - B12)
M2 = (A11 + A12) * B22
M3 = (A21 + A22) * B11
M4 = A22 * (B21 - B11)
M5 = (A11 + A22) * (B11 + B22)
M6 = (A12 - A22) * (B21 + B22)
M7 = (A11 - A21) * (B11 + B12)
完成了７次乘法，再做如下加法：
C11 = M5 + M4 - M2 + M6
C12 = M1 + M2
C21 = M3 + M4
C22 = M5 + M1 - M3 - M7
全部计算使用了７次乘法和１８次加减法，计算时间降低到O(nE2.81)。计算复杂性得到较大改进。(当n越大越明显)


递归方程为T(n) = 7*T(n/2) + O(n^2) (n > 2)，优于传统的划分T(n) = 8*T(n/2) + O(n^2) (n > 2)。


Strassen矩阵乘法的JAVA实现：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：最近点对问题（分治 + 递归）

题意：给出平面上的 N 个二维点，求出距离最小的 2 个点对。


算法思想：

我们设想如果将所有点按照X的坐标进行划分，这样所有点可以被模拟在一条直线上。这时候根据X轴来把所有点划分成两半(不断划分,直到被划分成的区域是只包含两个点或者三个点的时候，直接蛮力掉，求出这个区域的最近点对！)
1、当n<=3时，我们就可以直接算出最近点对！
2、当n>3时，我们将大问题k转换为求它左右两半区域的最近点对，再求跨越它左右两半的情况中的最近点对，进行比较三个最近点对值，就可以得到整个大问题k的最近点对值！
(当n>3时，划分集合区域S为SL（左区域）和SR（由区域），使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题（递归），得到LMin和RMin，分别表示SL和SR中的最近点对的距离。令CurrentMin=Min{LMin,RMin};。如果S中的最近点对(P1,P2)。P1、P2两点一个在SL和一个在SR中，那么P1和P2一定在以L为中心的间隙内，以L-d和L+d的区域内)。


算法步骤:
1、为了可以进行分治，我们先把所有点按照它的X坐标进行排序，使得所有点在X轴上可以找到相应的位置。
2、根据点的个数，把X轴这些点划分成两半，然后分别求出左右两半的最小距离。（LMin: 左半部分最小距离, RMin: 右半部分最小距离）
3、CurrentMin = Min{LMin, RMin}; 由于最小点对也可能是处于两半区域的中间，所以我们还需要在考虑两点处于中间的情况（具体的看上面算法思路中的分析）

最近点对问题的JAVA实现：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：循环赛日程安排表（分治）

题意：
设有n个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表：       
1.每个选手必须与其他n-1个选手各赛一次；       
2.每个选手一天只能参赛一次；        
3.n是偶数时,循环赛在n-1天内结束。n是奇数时,循环赛进行n天.

JAVA实现代码：

-------------------------------------------------------不积跬步无以至千里--------------------------------------------

题目：凸包问题求解（递归方式）

题意：
凸包:令S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸包。 


如下图1中由红线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 
图1：

凸包问题求解JAVA实现代码：