在定義一個過程或者函數時，出現調用本過程或本函數的成分，稱之為遞歸。如果調用自身，稱之為直接遞歸；
若過程或者函數p調用過程或者函數q，而q又調用p，稱之為間接遞歸；
任何間接遞歸都可以等價地轉換為直接遞歸；
如果一個遞歸過程或遞歸函數中遞歸調用語句是最后一條執行語句，則稱這種遞歸為尾遞歸；
可以使用遞歸解決的問題，應該滿足以下三個特點：
需要解決的問題可以轉換為一個或多個子問題來求解，而這些子問題的求解方法和原問題完全相同，只是數據規模不同；
遞歸調用的次數必須是有限的；
必須有結束遞歸的條件來終止遞歸；
一般來說，在以下三種情況下，常常使用到遞歸的方法：
定義遞歸：問題本身的定義是遞歸的，如數列定義；
數據結構遞歸：問題涉及的數據結構本身是遞歸的，如單鏈表；
求解方法遞歸：問題的解決方法是遞歸的，如漢諾塔問題；
遞歸模型是對遞歸問題的抽象，它反映一個遞歸問題的遞歸結構；
一般來說，遞歸模型有兩部分組成：遞歸出口和遞歸體。前者決定遞歸過程何時結束，后者確定遞歸如何進行；
如果{P(1),P(2),P(3),…,P(n)}是命題序列，且滿足以下兩個性質，則所有命題為真：
P(1)為真；
任何命題都可以從它的前一個命題推導出來；
如果{P(1),P(2),P(3),…,P(n)}是命題序列且滿足以下兩個性質，則所有命題均為真：
P(1)為真；
任何命題均可以由它前面所有命題推導得出；
數學歸納法是一種論證方法，而遞歸是算法和程序設計的一種實現技巧，數學歸納法是遞歸的基礎；
遞歸算法設計的核心是給出遞歸模型：
對原問題F(sn)進行分析，抽象出合理的小問題F(sn-1)；
假設F(sn-1)可解，在此基礎上給出F(sn)的解，即確定F(sn)和F(sn-1)的關系；相當于確定遞歸體；
確定一個特殊的情況，如F(0)或者F(1)，由此得到遞歸出口；
前面提到遞歸處理手法的使用場景：問題定義、數據結構、求解方法；實際上圍繞這三個點，我們就可以對其實施遞歸算法設計的一般步驟了；
對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小的時候）則直接解決，否則將其分解為K個規模較小的子問題。這些子問題相互獨立且與原問題形式相同，遞歸地解決這些子問題，然后將各個子問題的合并得到原問題的解；
該問題的規模縮小到一定程度就可以容易地解決；
該問題可以分解為若干個規模較小的相同問題；
利用該問題分解出的子問題的解，可以通過合并得到該問題的解；
該問題所分解出的各個子問題是相互獨立的，也就是子問題之間不包含公共的子問題；
分治法通常采用遞歸算法設計技術，在每一層遞歸上都包含三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
求解子問題：若子問題規模較小而容易被解決則直接求解，否則遞歸求解各個子問題；
合并：將各個子問題的解合并為原問題的解；
蠻力法是一種簡單直接地解決問題的方法，通常根據問題的描述和所涉及的概念定義找出所有可能的解；然后選擇其中一種或者多種解進行測試，如果該解不可行，則探尋下一種可能的解；
搜索所有解空間：問題的解存在于規模不大的解空間中；
搜索所有的路徑：這類問題中不同的路徑對應不同的解；
直接計算：基于問題的描述和所涉及的概念定義，直接進行計算，往往是一些簡單題，不需要算法技巧；
模擬和仿真：按照求解問題的要求直接進行模擬或者仿真即可；
一個復雜問題的解決方案是由若干個小的決策步驟組成的決策序列；解決一個問題的所有可能的決策序列構成該問題的解空間；
應用回溯法解決問題時，首先應該明確問題的解空間。解空間中滿足約束條件的決策序列稱為可行解；
一般來說，解任何問題都有一個目標，在約束條件下使目標達成的最優的可行解成為該問題的最優解；
問題的解有一個不等長或者等長的解向量X={x1,x2,x3…xn}構成，其中xi表示第i步的決策；所有滿足約束條件的解向量組構成問題的解空間；
問題的解空間一般用樹來表示，也稱為解空間樹或者狀態樹。樹中的每一個結點確定所求解問題的一個問題狀態；
解空間樹通常有兩種類型：
子集樹：當所給的問題是從n個元素的集合中選擇滿足某種性質的子集時，相應的解空間樹稱為子集樹；
排列樹：當所給的問題是確定n個元素的滿足某種性質的排列時，相應的解空間樹稱為排列樹；
而針對兩種解空間樹的類型，回溯法通常求解兩類問題：找所有解和找最優解；
在包含問題所有解的解空間樹中，按照深度優先搜索策略，從根結點出發搜索解空間樹的方法；它體現了走不通就退回再走的思路；
回溯法在搜索解空間時，通常采用兩種策略避免無效搜索，提高回溯的搜索效率：
用約束函數在擴展結點處剪除不滿足約束的子樹；
用限界函數剪去得不到問題解或者最優解的子樹；
限界函數和約束函數都屬于剪枝函數；剪枝函數存在的意義基于該觀點：我們往往只需要解空間中的部分樹或者最優的數；
確定問題的解空間樹；問題的解空間樹應至少包含問題的一個（最優）解；
確定結點的擴展規則；
以深度優先方式搜索解空間樹，并在搜索過程中可以采用剪枝函數來避免無效搜索，提高回溯的效率；
也就是說，回溯法=深度優先搜索 剪枝；
分枝限界法類似于回溯法，也是在問題對的額解空間樹上搜索問題解的算法；在一般情況下，分枝限界法與回溯法的求解目標并不相同；回溯法的目標是找出解空間中滿足約束條件的所有解；分枝限界法的目標則是找出滿足約束條件的一個解；或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優解；
所為分枝，就是采用廣度優先的策略，依次搜索活結點的所有分枝，也就是所有相鄰結點；采用一個限界函數，計算限界函數值，選擇一個最有利的子結點作為擴展結點，使搜索朝著解空間樹上有最優解的分枝推進，以便盡快地找出一個最優解；
分枝限界法和回溯法的主要區別：
| 方法 | 回溯法 | 分枝限界法 |
|---|---|---|
| 解空間搜索方法 | 深度優先 | 廣度優先 |
| 存儲結點的數據結構 | 棧 | 隊列、優先隊列 |
| 結點存儲特性 | 活結點的所有可行子結點被遍歷后才從棧中出棧 | 每個節點只有一次成為活結點的機會 |
| 常用應用 | 找出滿足條件的所有解 | 找出滿足條件的一個解或者特定意義的最優解 |
在所有解空間樹時，每個活結點可能有很多孩子結點，其中有些孩子結點搜索下去是不可能產生問題解或者最優解的；好的限界函數在擴展時將刪除這些不必要的孩子結點從而提高搜索效率：
目標是求最大值：設計上界函數up（根節點的up值通常大于或者等于最優解的up）；如果si是sj的雙親結點，應滿足up(si)>=up(sj)；當找到一個可行解up(sk)后，將所有小于up(sk)的結點剪枝；
目標是求最小值：設計下界函數lb（根節點的lb值一定要小于或等于最優解的lb值）；若si是sj的雙親結點，應滿足lb(si)<lb(sj)，當找到一個可行解lb(sk)后，將所有大于lb(sk)的結點剪枝；
根據選擇下一個擴展結點的方式來組織活結點表，不同的活結點表對應不同的分枝搜索方式：
隊列分枝限界法：隊列分枝限界法將活結點表組織成一個隊列，并按照先進先出的原則選擇下一個結點為擴展結點，其步驟如下：
將根節點加入活結點隊列；
從活結點隊列中取對頭結點作為當前擴展結點；
對當前擴展結點，先從左到右地產生孩子結點，用約束條件檢查，把所有滿足約束條件的孩子結點加入活結點隊列；
重復2-3，直到找到一個最優解；
優先隊列分枝限界法：優先隊列分枝限界法將活結點表組織成一個優先隊列，并選取優先級最高的活結點成為當前擴展結點，其步驟如下：
計算起始結點（根結點）的優先級并加入優先隊列；優先級往往由與特定問題相關的信息的函數值來決定；
從優先隊列中選取出優先級最高的結點作為當前擴展結點，使搜索朝著解空間樹上可能有最優解的分枝推進，以便能盡快地找出一個最優解；
對當前擴展結點，從左到右地產生它的所有孩子節點，然后用約束條件檢查，對所有滿足約束條件的孩子結點計算優先級并加入優先隊列；
重復2-3，直到找到一個解或者優先隊列為空為止；
分枝限界法在搜索解空間樹時，結點的處理是跳躍式的，回溯也不是單純地沿著雙親結點一層一層地向上回溯；具體有兩種方式確定最優解的解向量：
對每個結點保存從根結點到該結點的路徑：每個結點都帶有一個可能的解向量，這種方法實現起來比較簡單，但是浪費空間；
在搜索過程中構建搜索經過的樹結構：每個結點帶有一個雙親結點指針，當找到最優解時，同過雙親指針找到對應的最優解向量；這種做法需要保存搜索經過的樹結構，每個結點增加一個指向雙親結點的指針；
如何確定合適的限界函數？
如何組織待處理的活結點？
如何確定解向量的各個分量？
貪心法的基本思路是在求解問題時總是做出當前看來最好的選擇，也就是說貪心法不從整體最優上考慮，所做出的僅是在某種意義上的局部最優選擇；
但是人們通常希望得到整體最優解，所以在使用貪心法解決問題時需要證明所設計的算法確實是整體最優解或求解了它要解決的問題；
貪心法從問題的某一個初始解出發，采用逐步構造最優解的方法向給定目標前進，每一步都產生n元最優解向量的一個分量；
貪心法在每一步決策時所用的依據稱為最優量度標準，也稱為貪心準則；
每一次貪心選擇都將問題簡化為規模更小的子問題，并期望每次所做的局部最優選擇產生出一個全局最優解；
所謂貪心選擇性質是指問題的整體最優解可以通過一系列局部最優解的選擇，也就是貪心選擇來達到；
貪心法僅在當前狀態下做出最好選擇，即局部最優選擇，然后再去求解做出這個選擇后產生的相應子問題的最優解；
如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質；問題的最優子結構性質是該問題可以通過動態規劃算法或者貪心法求解的關鍵特性；
動態規劃是一種多階段決策問題的優化方法；將多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解；
能采用動態規劃問題求解的問題，一般具有3個性質：
最優性原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優性原理；
無后效性：某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關；
有重疊子問題：即子問題之間不是獨立的，一個子問題在下一階段決策中可能被多次使用到（該性質不是動態規劃適用的必要條件，但是如果沒有該性質，動態規劃算法同其他算法相比就沒有優勢）；
實際應用中簡化的步驟：
分析最優解的性質，并刻畫其結構特征；
遞歸地定義最優解；
以自底向上或者自頂向下的記憶化方式計算出最優解；
根據計算最優解時得到的信息，構造該問題的最優解；
動態規劃思想和分治法類似，都是將待求解問題分解為若干個子問題(階段)，然后按順序求解子階段，前一子問題為后一字問題的求解提供了有用的信息；
在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題的解就是初始問題的解；
動態規劃又和貪心法有些類似，在動態規劃中，可以將一個問題的解決方案視為一系列決策的結果；不同的是在貪心法中，每采用一次貪心準則就做出一個不可回溯的決策，還需要考察每個最優決策序列中是否包含一個最優子序列；
