遞歸

應用場景

1. 一個問題的解可以分解成多個子問題的解。
2. 這個問題與分解之後的子問題，除了數據規模不同，求解思路完全一樣。
3. 存在遞歸終止條件。

遞歸代碼編寫技巧

1. 找到如何將大問題分解成小問題的規律，基於此寫出遞推公式，推敲終止條件，將遞推公式和終止條件翻譯成代碼。
2. 只要遇到遞歸，就把它抽象成一個遞推公式，不用想一層層的調用關係，不要試圖用人腦去分解遞歸的每個步驟。

遞歸代碼編寫難點

1. 警惕堆棧溢出。可以通過在代碼中限制遞歸調用的最大深度。
2. 警惕重複計算。可以通過一個數據結構（比如散列表）來保存已經求解過的f(k)。當遞歸調用到f(k)時，先看下是否已經求解過了，如果是，則直接從散列表中取值返回，不要重複計算。

回溯

概念

1. 類似枚舉搜索，枚舉所有解，找到滿足期望的解。
2. 把問題求解過程分成多個階段。每個階段都會面對一個岔路口，先隨意選一條路走。
3. 當發現這條路走不通的時候（不符合期望的解），就回退到上一個岔路口，另選一種走法繼續走。

實現

遞歸

和深度優先的區別

1. 深度優先遍歷的目的是遍歷，本質是無序的。
2. 回溯法的目的是求解過程，本質是有序的。

應用

1. 深度優先搜索
2. 八皇后
3. 0-1揹包問題
4. 圖的顏色
5. 旅行商問題
6. 數獨
7. 全排列
8. 正則表達式匹配

分治

概念

1. 將原問題劃分成N個規模較小、結構與原問題相似的子問題。
2. 遞歸低解決這些子問題，然後再合併其結果，就得到原問題的解。

和遞歸的區別

1. 分治算法是一種處理問題的思想。
2. 遞歸是一種編程技巧。
3. 分治算法一般比較適合用遞歸來實現。

實現

1. 分解：將原問題分解成一系列子問題。
2. 解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解。
3. 合併：將子問題的結果合併成原問題。

應用條件

1. 原問題與分解成的小問題具有相同的模式。
2. 原問題分解成的子問題可以獨立求解，子問題之間沒有相關性。
3. 具有分解終止條件。
4. 可以將子問題合併成原問題。