遞歸算法是一些基本數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的基礎(chǔ)，不掌握遞歸那很多數(shù)據(jù)結(jié)構(gòu)沒(méi)法說(shuō)了。我們?cè)谶@里總結(jié)一下遞歸的用法。

遞歸簡(jiǎn)論：

我們熟悉的大多數(shù)數(shù)學(xué)函數(shù)都是由一個(gè)簡(jiǎn)單的公式來(lái)描述的，例如我們可以用C=5(F-32)/9來(lái)將華氏溫度轉(zhuǎn)成攝氏溫度。這種公式在java程序中實(shí)現(xiàn)實(shí)在是太簡(jiǎn)單的，而實(shí)現(xiàn)這種公式有一種統(tǒng)一的名稱，稱為迭代。
但是還有一種比較復(fù)雜的函數(shù)沒(méi)法直接使用，如下：
f（x)=2f(x-1)+x2，f(0)=0。
我們可以從條件推出f(1)=1,f(2)=6,f(3)=21,f(4)=58。
但是這種公式在程序種該如何表達(dá)？

引入

當(dāng)一個(gè)函數(shù)用它自己來(lái)定義時(shí)就稱之為遞歸，java是允許遞歸的。但重要的一點(diǎn)是：java提供的僅僅是遵守遞歸思想的一種嘗試。不是所有的遞歸函數(shù)都能由java的遞歸來(lái)模擬實(shí)現(xiàn)。
對(duì)于上面的遞歸函數(shù)，我們可以由如下代碼實(shí)現(xiàn)

package 遞歸簡(jiǎn)論;
/**
 * 遞歸（recursive）
 * 
 * 我們這里實(shí)現(xiàn)一個(gè)簡(jiǎn)單的遞歸函數(shù)：f（x)=2f(x-1)+x2，f(0)=0。
 * 
 * @author xuxiao
 *
 */
public class Recursive {
public static int f(int x) {
    if(x==0)
        return 0;
    else
        return 2*f(x-1)+x*x;
}
}

程序結(jié)構(gòu)

程序中的if(x==0)
return 0;

稱之為基準(zhǔn)情況（base case），即此時(shí)函數(shù)的值可以直接算出而不用求助于遞歸，正如f（0）=0一樣。若沒(méi)有函數(shù)這個(gè)基準(zhǔn)線，遞歸函數(shù)是沒(méi)有任何意義的，而程序中沒(méi)有基準(zhǔn)線，則會(huì)陷入無(wú)限循環(huán)的遞歸深淵。
實(shí)際上遞歸調(diào)用在處理上和調(diào)用普通方法沒(méi)什么區(qū)別，舉個(gè)例子，我以參數(shù)4調(diào)用函數(shù)f，那么程序就會(huì)計(jì)算2f（3）+44。這樣就會(huì)執(zhí)行一個(gè)f（3）的調(diào)用，又因此要去調(diào)用f（2），f（1），f（0），最后f（0）直接得到，從而返回上一層，f（1）也計(jì)算出來(lái)了，f（2），f（3），f（4）也依次得到了返回值。
遞歸調(diào)用的核心就是反復(fù)調(diào)用自身，直到基準(zhǔn)線的出現(xiàn)。因此上面的程序是有漏洞的，即如果我參數(shù)的值是-1，那么我的遞歸永遠(yuǎn)達(dá)不到基準(zhǔn)線。

上面對(duì)遞歸的討論可以將遞歸函數(shù)總結(jié)為兩個(gè)法則：

1.基準(zhǔn)線：必須要有基準(zhǔn)，否則遞歸不能求解
2.不斷推進(jìn)，對(duì)于那些要求遞歸的情景，遞歸總是朝著一個(gè)基準(zhǔn)情景推進(jìn)。（也就是說(shuō)如果我的函數(shù)是f（x)=2f(x)+x2，那這個(gè)函數(shù)也是無(wú)解的）

遞歸程序設(shè)計(jì)法則

1.基準(zhǔn)情形（在實(shí)際的編程中，基準(zhǔn)線可能會(huì)不止一條，找到正確且合適的基準(zhǔn)線是我們努力的目標(biāo)）
2.不斷推進(jìn)
3.設(shè)計(jì)法則。假設(shè)所有遞歸調(diào)用都能運(yùn)行
4.合成效益法則。在求解一個(gè)問(wèn)題的同一實(shí)例時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)的工作。
ps：合成效益法則表明，我們?cè)谶f歸計(jì)算如斐波那契數(shù)列的簡(jiǎn)單數(shù)學(xué)函數(shù)時(shí)使用遞歸是不明智的。