第二步，明确递归终止条件,就是当只剩下一个元素时
public static void perm(int a[], int k, int m){ if(k == m) { //只有一个元素 for (int i = 0; i <= m; i++) { System.out.print(a[i]+" "); } System.out.println(); } }第三步，寻找递归条件
public static void perm(int a[], int k, int m){ if(k == m) { //只有一个元素 for (int i = 0; i <= m; i++) { System.out.print(a[i]+" "); } System.out.println(); }else{ //还有多个元素，递归产生排列 for (int i = k; i <= m; i++) { swap(a,k,i); //排列到这个元素就要将其放在第一个位置 perm(a,k+1,m); swap(a,k,i); //从此出口出去后还需要将刚刚调换的位置换回来 } } }下面是递归这块的最后一个例题了，整数划分问题。
整数划分说明一下问题，什么是整数划分？
n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mi}为n的一个划分。
如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
举个例子，当n=5时我们可以获得以下这几种划分（注意，例子中m>=5）
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
编写程序，输入整数n,m，返回n的所有m的划分个数。
算法思路：我们用q(n,m)表示将n用不大于m的数字划分的方法的个数
1、n = 1时：只有一种划分法就是1
2、m = 1时：也只有一种划分法就是n个1相加
3、n < m时: 划分的方法也就只限于q(n,n)了，毕竟比n大的数也取不到嘛（不能取负数，要不然无限多了）
4、n = m时：就是1+(m-1)这一种情况加q(n,m-1)即1+q(n,m-1)。比如q(6,6)就是1+q(6,5)
5、n > m时：这种情况下又包含两种情况：
5(1)、划分中包含m时：即{m, {x1,x2,...xi}}(它们之和为n), 其中{x1,x2,... xi} 的和为n-m，所以就是n-m的m划分，即q(n-m,m)
5(2)、划分中不包含m时:划分中所有的值都比m小，即q(n,m-1)
因此第5中情况的划分为q(n-m,m)+1(n,m-1)
对第2中举例子详述：q(5,3):
(1)包含3: 1+1+3; 2+3; 既然每种情况都包含了3，那去掉3对其余各数相加为(5-3=)2的划分的个数和其相等，那就是对2(m=3)的划分了
(2)不包含3： 1+1+1+1+1; 1+1+1+2; 1+2+2;
第一步，明确函数输入和返回
public static int equationCount(int n, int m){ }第二步，明确递归终止条件
public static int equationCount(int n, int m){ if (n < 1 || m < 1) return 0; if(n == 1 || m == 1) return 1; }第三步，寻找递归关系
public static int equationCount(int n, int m){ if (n < 1 || m < 1) return 0; if(n == 1 || m == 1) return 1; if(n < m) return equationCount(n,n); if(n == m) return equationCount(n,m-1)+1; return equationCount(n-m,m)+equationCount(n,m-1); //n > m的情况 } 分治策略分治策略的基本思想就是将一个规模为n的问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将子问题的解合并得到原问题的解，和这种说法最贴切的就是我们之前一篇文章介绍的归并排序法了，这篇文章里我们还会再引出一遍。
我们将分治策略解决问题的步骤归纳为：将大问题分解成子问题，分别解决子问题，再将子问题的解合并成大问题的解.
先看第一个典型的例子——归并排序
这里我们对归并排序主要注重体现它分治策略的算法逻辑，而不过多深究这个排序算法是如何执行的，具体的图解归并排序请移步我的另一篇博文——数据结构之——八大排序算法。
归并排序的思想是，先将数组分割成为一个个小数组，直到每个小数组中只含有一个元素，那么在这一个小数组里面，这一个元素自然就是有序的，然后将其合并起来(由merge函数实现)，按从小到大的顺序，逐层向上，就是将小问题的解合并为大问题的解。
下面是将大问题分解成小问题的过程
/** * 只要数组的大小不为1，就一直分割，直到不能分割为止（即数组长度为1）， * 不能分割后按照出入栈顺序，会将分割的小数组分别排序后归并起来 * @param data 待排序数组 * @param start 起始位置 * @param end 终止位置 */ public static void merge_sort(int data[], int start, int end){ int mid = (start+end)/2; if(start < end){ merge_sort(data,start,mid); merge_sort(data,mid+1,end); merge(data,start,mid,end); } }下面是合并小问题的解，归并过程
/** * 这个函数是将数组合并在一起的，其实并没有将数组真的分开，只是用start和end指示不同的元素，来达到分割的目的 * @param p 指示子数组1的元素 * @param q 指示子数组2的元素 * @param r 指示合并后数组的元素 * @param start start到mid是需要合并的子数组1 * @param mid * @param end mid+1到end是需要合并的子数组2 */ private static void merge(int data[], int start, int mid, int end){ int p = start, q = mid+1, r = 0; int newdata[] = new int[end-start+1]; while(p <= mid && q <= end){ if(data[p] >= data[q]){ //从大到小排序 newdata[r++] = data[p++]; }else{ newdata[r++] = data[q++]; } } //此时，两个子数组中会有一个中元素还未被全部归并到新数组中，作如下处理 while(p <= mid){ newdata[r++] = data[p++]; } while(q <= end){ newdata[r++] = data[q++]; } //再将有序的数组中的值赋给原数组，其实也可以直接返回这个新数组 for (int i = start; i <= end; i++) { data[i] = newdata[i-start]; } } 二分查找