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;
}