将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作p(n)。
例如正整数6有如下11种不同的划分，所以p(6) = 11：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。
前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
(1) q(n,1)=1,n >= 1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，
即n = 1 + 1 + 1 + … +1.
(2) q(n,m) = q(n,n),m >= n; 最大加数n1实际上不能大于n。因此，q(1,m)=1。
(3) q(n,n)=1 + q(n,n-1); 正整数n的划分由n1=n的划分和n1 ≤ n-1的划分组成。
(4) q(n,m)=q(n,m-1)+q(n-m,m),n > m >1;
正整数n的最大加数n1不大于m的划分由 n1 = m的划分(即，划分的整数中必须含有m，则减去m剩下的数的划分为q(n-m,m))
和n1 ≤ m-1 的划分（q(n, m-1)）组成，。
前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
q(n,m) = 1 n = 1, m = 1
q(n,m) = q(n,n) n = 1, m = 1
q(n,m) = 1 + q(n,n-1) n = m
q(n,m) = q(n,m-1) + q(n-m,m) n > m > 1
正整数n的划分数p(n) = q(n,n)。
1 public class Recursion {
2 public static int partition(int n, int m) {
3 if(n < 1 || m < 1){
4 return 0;
5 }
6
7 if(n == 1 || m == 1){
8 return 1;
9 }
10 if(n < m)
11 return partition(n, n);
12 if( n == m){
13 return partition(n, m - 1) + 1;
14 }
15 return partition(n, m-1) + partition(n-m, m);
16 }
17 public static int par(int n){
18 return partition(n, n);
19 }
20 public static void main(String[] args) {
21 System.out.println(par(6));
22 }
23
24 }
q(6,6) = 1 + q(6,5) = 11;
q(6,5) = q(6,4)+q(1,5) = q(6,4)+1 = 10;
q(6,4) = q(6,3)+q(2,4) = q(6,3) + q(2,2) = 9 ;
q(2,2) = 1+ q(2, 1) = 1 + q(2,0) + q(1,1) = 2;
q(6,3) = q(6,2)+q(3,3) = 7;
q(3,3) = 1 + q(3,2) = 3;
q(3,2) = q(3,1) + q(1,2) = 2
q(6,2) = q(6,1) + q(4,2) = 1 + q(4,2) = 4
q(4,2) = q(4,1) + q(2,2) = 1 + 2= 3