一.分而治之
將原問題劃分為若干個規模較小而結構與原問題相同或相似的子問題，然后分別解決這些子問題，最后合并子問題的解，即可得到原問題的解，步驟抽象如下：
- 分解：將原問題分解為若干子問題
- 解決：遞歸求解所有子問題，如果子問題的規模小到可以直接解決，就直接解決它
- 合并：將子問題的解合并為原問題的解
子問題之間應該是相互獨立且沒有交叉的，從嚴格的定義上將，子問題個數為1的情況稱為減治，而大于1的情況稱為分治。
分治法作為一種思想，即可使用遞歸的手段去實現，也可以通過非遞歸的手段去實現。
二.遞歸
遞歸的一個很符合精髓且搞笑的定義：要理解遞歸，你要先理解遞歸，直到你能理解遞歸為止。
遞歸的核心在于——反復調用自身函數，但是每次能把問題范圍縮小，直到范圍縮小到可以直接得到邊界數據的結果，然后再在返回的路上求出對應的解。
兩個重要概念：
- 遞歸邊界：分解問題的盡頭
- 遞歸式（或者稱之為遞歸調用、遞歸函數）：分解子問題的手段
????????如果使用遞歸而式而不進行阻止，那么最后將會無法停止這個黑洞似的無窮盡的算法。遞歸的代碼結構中移動存在上述兩個概念，他們支撐起了整個遞歸最關鍵的邏輯。
三.遞歸計算階乘
直接先上代碼：
#include <iostream>
using namespace std;int F(int n){if(n==0) return 1;elsereturn F(n-1)*n;
}int main() {int n=0;cin>>n;cout<<F(n);return 0;
}仔細觀察，不難發現：
- 遞歸邊界：n==0
- 遞歸式：F(n-1)*n
來仔細的分析一下，對于F(5)來說——相當于是F(4)*5,以此類推，直接將F(5)分解到了F(0)，此時F(0)=1，即子問題的答案，再將所有子問題的答案合并，即可完成本次求解~
假設輸入的是3，則推倒過程依次為：
- F(3)
- F(2)*3
- F(1)*2*3
- F(0)*1*2*3
- 得到最后的F(0)的值以后，再返回去依次計算F(1)、F(2)、F(3)
四.遞歸計算裴波那契數列
#include <iostream>
using namespace std;int F(int n){if(n==0||n==1) return 1;elsereturn F(n-1)+F(n-2);
}int main() {int n=0;cin>>n;cout<<F(n);return 0;
}仔細觀察，也沒什么難度：
- 遞歸邊界：0和1的返回值均為1
- 遞歸式：根據定義，第三項開始即為前兩項的和
????????對于這類遞歸問題，只要找到了遞歸邊界和遞歸式，寫起來代碼就沒什么難度。遞歸邊界用來返回最簡單底層的結果，遞歸式用來減小規模并進一步向下一層遞歸。遞歸圖可以將遞歸放在一個平面上思考，有利于更快分析題目~
五.全排列
????????某種意義上來說，學會遞歸的思維正是從一個只會暴力的小白蛻變的過程，比如當我們要求輸入1~n之間數的全排列，如果硬碰硬直接霸王硬上弓，這個復雜度簡直不能想象——畢竟光數量都達到n的階乘個，何況找起來也是很費事的。
? ? ? ? 從遞歸的角度去考慮，如果把問題描述成“1~n這n個整數的全排列”，那么就可以拆分為若干個子問題：“輸出以1開頭的全排列”、“輸出以2開頭的全排列”……以此類推。不妨設置一個數組P，用來存放當前的排列；再設置一個散列數組hashTable，其中hashTable[x]當x已在P中時賦值為true。
? ? ? ? 現在按照順序往P中的第1位到第N位填入數字。不妨假設當前已經填好了1~index-1位，正準備去填寫index位。我們需要枚舉1~n，如果當前枚舉的數字x還沒喲再1~index-1中，即填入到index位，同時設置hashTable[x]為true，然后去處理index+1位；如果遞歸完成時，以便讓P[index]填寫下一個數字。
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=11;int n,P[11],hashTable[maxn]={false};
//p為當前排列
//hashTable用來記錄x是否已經在P中！ void generateP(int index) //當前處理的正是第index位
{if(index==n+1) //1~n已經處理完了，所以相當于n+1為遞歸邊界~ {for(int i=1;i<=n;i++)cout<<P[i]; //輸出當前排列 cout<<endl;return;}for(int x=1;x<=n;x++) //枚舉1~n，試圖將x填入到P[index]位上！ {if(hashTable[x]==false) //false即表示不存在~ {P[index]=x; //填入到index位 hashTable[x]=true; generateP(index+1); //遞歸處理下一位：即index+1 hashTable[x]=false;}}
}int main() {n=3;generateP(1);return 0;
}- 遞歸邊界：index==n+1
- 遞歸式：generateP(index+1);
六.N皇后問題
????????N 皇后問題指的是如何將 N 個皇后放置在 N × N 的棋盤上，并且使皇后彼此之間不能相互攻擊。即給你一個整數 N ，返回所有不同的 N?皇后問題的解決方案數量~
????????這玩意，不知道大家有沒有想起來行列式的定義：將行列式視為從矩陣的不同行和不同列中選取元素并相乘的代數和。每一項的符號由列標的逆序數決定，即如果列標的逆序數為奇數，則該項為負；若為偶數，則該項為正——其實就是全排列~不過不同的是，行列式可以在對角線上選擇元素，而對于可以斜線行走的皇后，這一點顯然也是不行。因此可以基于全排列的代碼，然后對每一個全排列的結果進行單獨判斷是否存在對角線元素，即可完成~?
?如下：判斷是否在同一對角線，只需要看行距之差和列距之差的絕對值是否相同，即可：
int count=0;
void generateP(int index) //當前處理的正是第index位
{if(index==n+1) //1~n已經處理完了，所以相當于n+1為遞歸邊界~ {bool flag=true; //flag為true時表示當前為一個合法方案~ for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(abs(i-j)==abs(P[i]-P[j])) flag=false; //不合法 }if(flag)count++;return;}for(int x=1;x<=n;x++) //枚舉1~n，試圖將x填入到P[index]位上！ {if(hashTable[x]==false) //false即表示不存在~ {P[index]=x; //填入到index位 hashTable[x]=true; generateP(index+1); //遞歸處理下一位：即index+1 hashTable[x]=false;}}
}對于遞歸，只要想清楚邊界、遞歸式、問題需要的答案，就沒什么難度~
)
