當(dāng)一個(gè)函數(shù)用它自己來(lái)定義的時(shí)候就稱(chēng)為是遞歸的。--《數(shù)據(jù)結(jié)構(gòu)與算法分析java語(yǔ)言描述》
例如：我們可以在非負(fù)整數(shù)集上定義一個(gè)函數(shù)f，滿(mǎn)足f(0)=0且f(x)=2f(x-1)+x*x?？梢缘玫絝(1)=1，f(2)=6，f(3)=21。

public int f(int x){
    if(x == 0){
        return 0;
    }else{
        return 2 * f(x-1) + x * x;
    }
}

基本法則
1.基準(zhǔn)情況：必須要有某些基準(zhǔn)的情形，不用遞歸就能求解。
2.不斷推進(jìn)：對(duì)于那些要遞歸求解的情形，遞歸調(diào)用必須總能朝著一個(gè)基準(zhǔn)情形推進(jìn)。

• 當(dāng)x=0時(shí)可以算出而不用遞歸。和數(shù)學(xué)公式f(x)=2f(x-1)+xx一樣，若沒(méi)有f(0)=0這個(gè)事實(shí)在，這個(gè)公式就沒(méi)有意義。Java的遞歸若沒(méi)有基準(zhǔn)情況*也是毫無(wú)意義。上述代碼，當(dāng)x=0時(shí)返回0，就是基準(zhǔn)情況。
• f(4)需要執(zhí)行f(3)，因此要執(zhí)行f(2)，又要另外執(zhí)行f(1)，因此，2*f(0)+1得到f(1)=1。此時(shí)f(0)必須被賦值。由于屬于基準(zhǔn)情況，我們事先得知f(0)=0。從而f(1)=1。然后f(2)、f(3)、f(4)等的值都能夠計(jì)算出來(lái)