Posted on 2007-02-20 12:56
dennis 閱讀(1274)
評論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法
1。遞歸的定義：
遞歸的定義由兩部分組成：
1）稱作定位點(diǎn)（anchor）或者基本情況（ground case），它們是一些基本元素，這些基本元素是集合序列中其他所有對象的基礎(chǔ)。
2）給出除基本元素或者已創(chuàng)建對象之外的新對象的構(gòu)造規(guī)則，可以再三使用這個(gè)規(guī)則不斷產(chǎn)生新的對象。
2。遞歸的實(shí)現(xiàn)：一般是由操作系統(tǒng)完成的，但是大部分的計(jì)算機(jī)系統(tǒng)的遞歸定義都是利用運(yùn)行時(shí)堆棧實(shí)現(xiàn)的。在系統(tǒng)內(nèi)，無論何時(shí)調(diào)用一個(gè)方法都會創(chuàng)建一個(gè)活動記錄。一個(gè)遞歸調(diào)用并不僅僅是一個(gè)方法調(diào)用其自身，而是方法的一個(gè)instance調(diào)用相同方法的另一個(gè)instance，在計(jì)算機(jī)內(nèi)部，這些調(diào)用是用不同的活動記錄表示，并由系統(tǒng)區(qū)分。
3。尾遞歸：
僅在方法的末尾實(shí)行一次遞歸調(diào)用，這樣的遞歸叫尾遞歸。尾遞歸很容易被循環(huán)所替換，或者說它只是一個(gè)名字比較好聽的循環(huán)，如：
void?tail(int?i)
{
??if(i>0){
????System.out.print(i+"?");
????tail(i-1);
??}
}替換為循環(huán)：
void?tail2(int?i){
???for(;i>0;i--)
?????System.out.print(i+"?");
} 尾遞歸對一些沒有顯式循環(huán)結(jié)構(gòu)的語言（如Prolog）特別重要
4。非尾遞歸：
遞歸相比于迭代結(jié)構(gòu)的優(yōu)點(diǎn)就是非常清晰并易于理解，這一點(diǎn)可以在二叉樹遍歷上得到體現(xiàn)。3種遍歷方式的遞歸版本與迭代版本在可讀性上不可同日而語。
問題：逆序輸出一行輸入（以ruby語言為例）
def?reverse
??s=STDIN.getc
??if?s.chr!="/n"
????reverse
????print?s.chr
??end
end?
reverse?運(yùn)行此程序，輸入一行字符，將逆序輸出，本質(zhì)上是利用運(yùn)行時(shí)堆棧完成的遞歸調(diào)用
5。間接遞歸：
方法通過一連串的調(diào)用，然后間接地調(diào)用它自身，這樣的遞歸稱為間接遞歸。
6。嵌套遞歸
一般出現(xiàn)在函數(shù)的定義中，如果這個(gè)函數(shù)不僅用它自身定義，而且還江它自身作為一個(gè)參數(shù)，如：
???? 0????? ???? ?n=0
h(n)=n??? ???? n>4
h(2+h(2n))?? n<=4
7。過分遞歸：遞歸帶來的邏輯簡單性和可讀性的代價(jià)是拖長了運(yùn)行時(shí)間并且相對于非遞歸方法，它占用了更多的運(yùn)行時(shí)堆棧空間。如果遞歸層次太深，可能導(dǎo)致運(yùn)行時(shí)堆棧溢出，程序非正常結(jié)束的錯誤。
8?；厮荩╞acktracking技術(shù)）：在某點(diǎn)有多條道路供選擇的時(shí)候，但不清楚哪一條能解決問題。在嘗試一條道路失敗后，返回岔口再試另一條道路。但是必須確定所有的道路都是可嘗試的，可返回的。這種技術(shù)成為回溯。
在迷宮問題中和8皇后問題中使用此技術(shù)。具體程序不再列出（好長@_@）