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