递归算法之整数划分

将正整数n表示成一系列正整数之和，n=n1+n2+...+nk,其中n1>=n2>=...>=nk,k>=1.
将最大加数n1不大于m的划分个数记做：q(n, m).
1.q(n, 1) = 1, n>=1.
2.q(n, m) = q(n, n),m>=n.
3.q(n, n) = 1+q(n, n-1).
4.q(n, m) = q(n, m-1)+q(n-m, m),n>m>1,即：正整数的最大加数n1不大于m的划分有n1=m的划分和n1<=m-1的划分组成。

#include <stdio.h>

static int division(int n, int m);
int main(int argc, char **argv)
{
        int n;
        int num;

        scanf("%d", &n);
        getchar();

        num = division(n, n);
        printf("num = %d\n", num);

        return 0;
}

static int division(int n, int m)
{
        if((n < 1) || m < 1){
                return 0;
        }

        if((n == 1) || m == 1){
                return 1;
        }

        if(n < m){
                return division(n, n);
        }

        if(n == m){
                return (1 + division(n, n-1));
        }

        return (division(n, m-1) + division(n-m, m));
}

[xxxx@localhost graph]$ ./a.out
6
num = 11