Feng.Li's Java See

编写递归程序有几个重要的原则，细节详叙如后。
    1. 要解决的问题可拆分为几个与原问题类似的子问题（子问题仍可拆分）。
    2. 每个子问题必须比原来问题的规模更小（即使小一号也行，当然如果能够迅速减小规模更好）。
    3. 遇到足够小的子问题时就直接解决之，防止问题无限细分下去，也就是防止无限递归（递归终止条件很重要）。 
先看一个最简单的递归程序，下面程序求整数n的阶乘：
int factorial(int n)
{
    return n <= 1 ? 1 : n*factorial(n-1);
}
所谓递归程序，就是程序在执行中又调用其自身，如上面函数factorial在其函数体内调用了函数factorial。函数在每次被调用时都会生成一个包含自身局部变量的副本，即算是函数调用自身时也是如此。 递归程序主体主要由两部分构成：一是递归执行部分，包含递归执行所需的条件；一是递归终止部分，含递归终止条件。上面求阶乘的程序中把这两部分写在一行代码里面，把其分别抽出来便是：
int factorial(int n)
{
    if(n <= 1) return 1;     // 递归终止体
    return n*factorial(n-1); // 递归执行体
}

下面以几个经典算法问题的递归程序求解为例来分析编写递归程序中可以遵循的简单规则。
1. 求正整数n所有可能的和式的组合，如给定正整数3，所有和加起来等于3的和式如下：
3 = 3 + 0
3 = 2 + 1
3 = 1 + 1 + 1
其中一个和式中的因子只能为自然数，因子允许重复出现。

这个问题是一个组合问题的变形，用递归程序实现如下（分析见注释）：
#define MAXSIZE 50       
static int buff[MAXSIZE]; // 存储和式因子组合的缓冲
/// 求当前和式中因子之和。
int Sum(int buff[],int i)
{
    int sum = 0;
    for(int m=0; m<=i; m++)
        sum += buff[m];
    return sum;
}
/// 打印当前满足条件的和式。
void printFactor(int buff[],int i,const int number)
{
    int count = 0, m;
    for(m=0; m<=i; m++)
        printf("%4d",buff[m]);
    if(number==buff[0])
        printf("%4d",0);
    printf("\n");
}
/// 递归求解所有和式组合。
/// i - 当前可选自然数的最大值。
/// top - 当前组合中因子个数。
/// number - 问题中要求解和式的正整数。
void divide(int i,int top,int number)
{   
    for(int j=i; j>0; j--)               // 注意这里的循环条件，可以有效防止出现重复的组合
    {
        buff[top ] = j;

        if(number == Sum(buff,top))      // 首先要确定递归中止条件
            printFactor(buff,top,number);
        else if(number < Sum(buff,top))  // 继续增加和式中的因子
            continue;

        if(top >= number)                // 和式中的因子不应该超过和的大小
            continue;

        divide(j,top+1,number);          // 减小问题规模，继续递归
    }
    return;
}

int main()
{
    int i,top = 0;
    int number = 8;
    printf("input a souce number:");
    scanf("%d",&number);
    i = number;
    divide(i,top,number);

    return 0;
}