Feng.Li's Java See

編寫遞歸程序有幾個(gè)重要的原則，細(xì)節(jié)詳敘如后。
    1. 要解決的問(wèn)題可拆分為幾個(gè)與原問(wèn)題類似的子問(wèn)題（子問(wèn)題仍可拆分）。
    2. 每個(gè)子問(wèn)題必須比原來(lái)問(wèn)題的規(guī)模更小（即使小一號(hào)也行，當(dāng)然如果能夠迅速減小規(guī)模更好）。
    3. 遇到足夠小的子問(wèn)題時(shí)就直接解決之，防止問(wèn)題無(wú)限細(xì)分下去，也就是防止無(wú)限遞歸（遞歸終止條件很重要）。 
先看一個(gè)最簡(jiǎn)單的遞歸程序，下面程序求整數(shù)n的階乘：
int factorial(int n)
{
    return n <= 1 ? 1 : n*factorial(n-1);
}
所謂遞歸程序，就是程序在執(zhí)行中又調(diào)用其自身，如上面函數(shù)factorial在其函數(shù)體內(nèi)調(diào)用了函數(shù)factorial。函數(shù)在每次被調(diào)用時(shí)都會(huì)生成一個(gè)包含自身局部變量的副本，即算是函數(shù)調(diào)用自身時(shí)也是如此。 遞歸程序主體主要由兩部分構(gòu)成：一是遞歸執(zhí)行部分，包含遞歸執(zhí)行所需的條件；一是遞歸終止部分，含遞歸終止條件。上面求階乘的程序中把這兩部分寫在一行代碼里面，把其分別抽出來(lái)便是：
int factorial(int n)
{
    if(n <= 1) return 1;     // 遞歸終止體
    return n*factorial(n-1); // 遞歸執(zhí)行體
}

下面以幾個(gè)經(jīng)典算法問(wèn)題的遞歸程序求解為例來(lái)分析編寫遞歸程序中可以遵循的簡(jiǎn)單規(guī)則。
1. 求正整數(shù)n所有可能的和式的組合，如給定正整數(shù)3，所有和加起來(lái)等于3的和式如下：
3 = 3 + 0
3 = 2 + 1
3 = 1 + 1 + 1
其中一個(gè)和式中的因子只能為自然數(shù)，因子允許重復(fù)出現(xiàn)。

這個(gè)問(wèn)題是一個(gè)組合問(wèn)題的變形，用遞歸程序?qū)崿F(xiàn)如下（分析見(jiàn)注釋）：
#define MAXSIZE 50       
static int buff[MAXSIZE]; // 存儲(chǔ)和式因子組合的緩沖
/// 求當(dāng)前和式中因子之和。
int Sum(int buff[],int i)
{
    int sum = 0;
    for(int m=0; m<=i; m++)
        sum += buff[m];
    return sum;
}
/// 打印當(dāng)前滿足條件的和式。
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 - 當(dāng)前可選自然數(shù)的最大值。
/// top - 當(dāng)前組合中因子個(gè)數(shù)。
/// number - 問(wèn)題中要求解和式的正整數(shù)。
void divide(int i,int top,int number)
{   
    for(int j=i; j>0; j--)               // 注意這里的循環(huán)條件，可以有效防止出現(xiàn)重復(fù)的組合
    {
        buff[top ] = j;

        if(number == Sum(buff,top))      // 首先要確定遞歸中止條件
            printFactor(buff,top,number);
        else if(number < Sum(buff,top))  // 繼續(xù)增加和式中的因子
            continue;

        if(top >= number)                // 和式中的因子不應(yīng)該超過(guò)和的大小
            continue;

        divide(j,top+1,number);          // 減小問(wèn)題規(guī)模，繼續(xù)遞歸
    }
    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;
}