遞歸與分治策略
遞歸與分治策略是五大常見算法策略之一，分治策略的思想就是 分而治之 ，即先將一個規模較大的大問題分解成若干個規模較小的小問題，再對這些小問題進行解決，得到的解，在將其組合起來得到最終的解。而分治與遞歸很多情況下都是一起結合使用的，能發揮出奇效（1+1>2），這篇文章我們將先從遞歸說起，再逐漸向分治過渡，主要講解方式是通過9個例題來說明問題的，問題都是根據難度由簡到難，由淺入深，對遞歸與分治能有個大概的了解雛形，當然最重要還是要做大量練習才能掌握。
0.0、Fibonacci數列(易)
遞歸
我們第一次接觸遞歸一般都是在初學C語言時候的一道題目——Fibonacci數列中看到的，可能剛開始感覺有點不可思議，函數居然可以調用自己！Amazing！但事實如此，它確實存在，而遞歸也為我們某些算法的設計提供很大的便利，一般來說遞歸函數在理解起來並不是很難，甚至可以通過數學歸納法給予證明，但一直讓人詬病的一點莫過於Debug的時候了，有時候調試一個較為複雜的遞歸函數能把人逼瘋。
我們在這裡將會 由易到難 ，用一些例題先來講解遞歸函數。採用Fibonacci數列來做這個引例來介紹遞歸函數。
Fibonacci
第一個數是1，第二個數也是1，從第三個數開始，後面每個數都等於前兩個數之和。要求：輸入一個n，輸出第n個斐波那契數。
我們先來整理一下思路，分下面三步來看：
- 1、明確函數的輸入和輸出(即函數的作用)
- 2、明確遞歸終止條件
- 3、尋找函數的遞歸關係式
第一步，函數輸入n，輸出(也就是返回)第n個斐波那契數：
public static int fibonacci(int n){ }第二步，明確遞歸終止條件：
public static int fibonacci(int n){ if(n == 1) return 1; else if (n == 2) return 1;}第三步，尋找函數的遞歸關係：
public static int fibonacci(int n){ if(n == 1) return 1; else if(n == 2) return 1; else return fibonacci(n - 1) + fibonacci(n - 2);}就這樣，我們的一個斐波那契數列的遞歸函數就寫完了。當然，這只是我們的一個開胃小菜，下面繼續是入門級別的一個題，算階乘。
階乘
輸入一個數，輸出它的階乘。我們同樣用那三步往下走。
第一步，函數輸入n，返回n的階乘
public static int factorial(int n){ }第二步，明確遞歸終止條件：
public static int factorial(int n){ //0的階乘等於1 if(n == 0) return 1;}第三步，尋找函數的遞歸關係
public static int factorial(int n){ //0的階乘等於1 if(n == 0) return 1; else return factorial(n - 1) * n;}做完前兩個你肯定會覺得這不是很簡單嗎，不要急，我們要由易到難，由淺入深，這樣階梯式的科學學習。下面這個例子是小青蛙跳台階問題，這個問題被用於遞歸和動態規劃類問題的例題，我們這裡先用遞歸解答，後面還會用動態規劃策略來解決這個問題。
小青蛙跳台階
一隻青蛙一次可以跳上1級台階，也可以跳上2級，求該青蛙跳上一個n級的台階共有多少種跳法。
還是三步走，第一步，明確函數的輸入及返回
public static int Jump_Floor1(int n){ }第二步，明確遞歸終止條件
如果n=1，那小青蛙只能一次跳上第一節台階，所以一種跳法，如果n=2，那小青蛙可以一次跳一節跳兩次，或者直接一次跳兩節，所以兩種跳法。
public static int Jump_Floor1(int n){ if(n <= 2){ return n; }}第三步，尋找函數的遞歸條件
這裡可不能簡單的return Jump_Floor1(n-1)就完事兒了，分了兩種情況：1、第一次跳1級就還有n-1級要跳，2、第一次跳2級就還有n-2級要跳
public static int Jump_Floor1(int n){ if(n <= 2){ return n; }else{ //這裡涉及到兩種跳法，1、第一次跳1級就還有n-1級要跳，2、第一次跳2級就還有n-2級要跳 return Jump_Floor1(n-1)+Jump_Floor1(n-2); }}下面這個例題是排列問題，就是求出一組數的全排列。
全排列問題
我們在全排列問題種需要用到一個交換函數swap用於交換兩個數的位置，作如下定義：k數組種元素為待排列元素，k和m為待交換兩元素的下標
private static void swap(int a[], int k, int m){ //交換k和m下標的元素的值 int temp = a[k]; a[k] = a[m]; a[m] = temp;}接下來繼續回到遞歸函數
第一步，明確函數的輸入以及返回，這裡我們需要輸入待排列元素組成的數組，數組的第一個元素的下標，以及最後一個元素的下標
public static void perm(int a[], int k, int m){}第二步，明確遞歸終止條件,就是當只剩下一個元素時
public static void perm(int a[], int k, int m){ if(k == m) { //只有一個元素 for (int i = 0; i <= m; i++) { System.out.print(a[i]+" "); } System.out.println(); }}第三步，尋找遞歸條件
public static void perm(int a[], int k, int m){ if(k == m) { //只有一個元素 for (int i = 0; i <= m; i++) { System.out.print(a[i]+" "); } System.out.println(); }else{ //還有多個元素，遞歸產生排列 for (int i = k; i <= m; i++) { swap(a,k,i); //排列到這個元素就要將其放在第一個位置 perm(a,k+1,m); swap(a,k,i); //從此出口出去後還需要將剛剛調換的位置換回來 } }}下面是遞歸這塊的最後一個例題了，整數劃分問題。
整數劃分
說明一下問題，什麼是整數劃分？
- n=m1+m2+...+mi; （其中mi為正整數，並且1 <= mi <= n），則{m1,m2,...,mi}為n的一個劃分。
- 如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬於n的一個m劃分。這裡我們記n的m劃分的個數為f(n,m);
- 舉個例子，當n=5時我們可以獲得以下這幾種劃分（注意，例子中m>=5）
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
編寫程序，輸入整數n,m，返回n的所有m的劃分個數。
算法思路：我們用q(n,m)表示將n用不大於m的數字劃分的方法的個數
- 1、n = 1時：只有一種劃分法就是1
- 2、m = 1時：也只有一種劃分法就是n個1相加
- 3、n < m時: 劃分的方法也就只限於q(n,n)了，畢竟比n大的數也取不到嘛（不能取負數，要不然無限多了）
- 4、n = m時：就是1+(m-1)這一種情況加q(n,m-1)即1+q(n,m-1)。比如q(6,6)就是1+q(6,5)
- 5、n > m時：這種情況下又包含兩種情況：
5(1)、劃分中包含m時：即{m, {x1,x2,...xi}}(它們之和為n), 其中{x1,x2,... xi} 的和為n-m，所以就是n-m的m劃分，即q(n-m,m)
5(2)、劃分中不包含m時:劃分中所有的值都比m小，即q(n,m-1) - 因此第5中情況的劃分為q(n-m,m)+1(n,m-1)
- 對第2中舉例子詳述：q(5,3):
(1)包含3: 1+1+3; 2+3; 既然每種情況都包含了3，那去掉3對其餘各數相加為(5-3=)2的劃分的個數和其相等，那就是對2(m=3)的劃分了
(2)不包含3： 1+1+1+1+1; 1+1+1+2; 1+2+2;
第一步，明確函數輸入和返回
public static int equationCount(int n, int m){}第二步，明確遞歸終止條件
public static int equationCount(int n, int m){ if (n < 1 || m < 1) return 0; if(n == 1 || m == 1) return 1;}第三步，尋找遞歸關係
public static int equationCount(int n, int m){ if (n < 1 || m < 1) return 0; if(n == 1 || m == 1) return 1; if(n < m) return equationCount(n,n); if(n == m) return equationCount(n,m-1)+1; return equationCount(n-m,m)+equationCount(n,m-1); //n > m的情況}分治策略
分治策略的基本思想就是將一個規模為n的問題分解成k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸的解這些子問題，然後將子問題的解合併得到原問題的解，和這種說法最貼切的就是我們之前一篇文章介紹的歸併排序法了，這篇文章里我們還會再引出一遍。
我們將分治策略解決問題的步驟歸納為：將大問題分解成子問題，分別解決子問題，再將子問題的解合併成大問題的解.
先看第一個典型的例子——歸併排序
歸併排序
這裡我們對歸併排序主要注重體現它分治策略的算法邏輯，而不過多深究這個排序算法是如何執行的，具體的圖解歸併排序請移步我的另一篇博文—— 數據結構之——八大排序算法 。
歸併排序的思想是，先將數組分割成為一個個小數組，直到每個小數組中只含有一個元素，那麼在這一個小數組裡面，這一個元素自然就是有序的，然後將其合併起來(由merge函數實現)，按從小到大的順序，逐層向上，就是將小問題的解合併為大問題的解。
下面是將大問題分解成小問題的過程
/** * 只要數組的大小不為1，就一直分割，直到不能分割為止（即數組長度為1）， * 不能分割後按照出入棧順序，會將分割的小數組分別排序後歸併起來 * @param data 待排序數組 * @param start 起始位置 * @param end 終止位置 */public static void merge_sort(int data[], int start, int end){ int mid = (start+end)/2; if(start < end){ merge_sort(data,start,mid); merge_sort(data,mid+1,end); merge(data,start,mid,end); }}下面是合併小問題的解，歸併過程
/** * 這個函數是將數組合併在一起的，其實並沒有將數組真的分開，只是用start和end指示不同的元素，來達到分割的目的 * @param p 指示子數組1的元素 * @param q 指示子數組2的元素 * @param r 指示合併後數組的元素 * @param start start到mid是需要合併的子數組1 * @param mid * @param end mid+1到end是需要合併的子數組2 */private static void merge(int data[], int start, int mid, int end){ int p = start, q = mid+1, r = 0; int newdata[] = new int[end-start+1]; while(p <= mid && q <= end){ if(data[p] >= data[q]){ //從大到小排序 newdata[r++] = data[p++]; }else{ newdata[r++] = data[q++]; } } //此時，兩個子數組中會有一個中元素還未被全部歸併到新數組中，作如下處理 while(p <= mid){ newdata[r++] = data[p++]; } while(q <= end){ newdata[r++] = data[q++]; } //再將有序的數組中的值賦給原數組，其實也可以直接返回這個新數組 for (int i = start; i <= end; i++) { data[i] = newdata[i-start]; }}二分查找
然後是分治策略的另一個經典例子———二分查找，顧名思義，就是在一個有序（從小到大）的數組中查找一個元素的位置，先從最中間將數組變為兩個小數組，然後與中間值進行對比，如果相等直接返回，不相等又分兩種情況，如果中間元素比待查找值小，就從後半個數組中繼續二分查找，反之，從前半個數組中二分查找。
public static int Binary_Search(int []data, int x, int n){ //data為待搜索數組(有序)，x為待搜索元素，n為數組大小 int left = 0, right = n - 1; //指示左右的兩個指示器 while(left <= right){ //left可以等於right，因為有可能剛好兩個指示器同時指示到了待查找元素上 int mid = (left+right)/2; if(data[mid] > x) right = mid-1; else if(data[mid] < x) left = mid+1; else return mid; } return -1; //表示查找失敗}棋盤覆蓋
下面我們逐漸加大難度，接下來這個問題叫做棋盤覆蓋，我們先簡單介紹一下這個問題。
在一個2^k × 2^k （k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。顯然，特殊方格在棋盤中可能出現的位置有4^k種，因而有4^k種不同的棋盤，圖4.10(a)所示是k=3時64種棋盤中的一個。棋盤覆蓋問題（chess cover problem）要求用圖4.10(b)所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。
圖4.10(a)
圖4.10(b)
在這裡為了方便講解，我們採用k=2時候的情況來說明這個問題，設初始情況為
第一次將其分割成四個小塊，分成了四個子棋盤，以黃線為分割線
然後分別對其進行填充
填充完後，又可以將其分割
重複上述填充操作，即可對所有方格填充
當k更大的時候的過程可以參考這位大佬的博客 棋盤覆蓋問題 ，接下來我們用代碼實現。
static int board[][] = new int[4][4]; //棋盤static int tag = 1; //骨牌編號/** * 分治算法典例2———棋盤覆蓋問題 * @date 2019/11/3 afternoon * @param tr 棋盤左上角方格的行號 * @param tc 棋盤左上角方格的列號 * @param dr 特殊方格所在的行號 * @param dc 特殊方格所在的列號 * @param size 棋盤寬度 * @param s 當前棋盤寬度的一半 * @param tr+s 當前棋盤中間行的行號 * @param tc+s 當前棋盤中間列的列號 */public static void chess(int tr, int tc, int dr, int dc, int size){ if(size == 1) return; int newtag = tag++; int s = size / 2; //分割棋盤 //覆蓋左上角子棋盤 if(dr < tr+s && dc < tc+s){ //特殊方格在此棋盤中 chess(tr,tc,dr,dc,s); }else{ //此棋盤中無特殊方格 board[tr+s-1][tc+s-1] = newtag; chess(tr,tc,tr+s-1,tc+s-1,s); } //覆蓋右上角子棋盤 if(dr < tr+s && dc >= tc+s){ chess(tr,tc+s,dr,dc,s); }else{ board[tr+s-1][tc+s] = newtag; chess(tr,tc+s,tr+s-1,tc+s,s); } //覆蓋左下角子棋盤 if(dr >= tr+s && dc < tc+s){ chess(tr+s,tc,dr,dc,s); }else{ board[tr+s][tc+s-1] = newtag; chess(tr+s,tc,tr+s,tc+s-1,s); } //覆蓋右下角子棋盤 if(dr >= tr+s && dc >= tc+s){ chess(tr+s,tc+s,dr,dc,s); }else{ board[tr+s][tc+s] = newtag; chess(tr+s,tc+s,tr+s,tc+s,s); }}接下來的問題依然有一些難度，叫做列印日程表問題。
日程表問題
問題：設有n=2^k個選手參加循環賽，要求設計一個滿足以下要求比賽日程表：
1）每個選手必須與其它n-1個選手各賽一次；
2）每個選手一天只能賽一次。
分析，按照上面的要求，可以將比賽表設計成一個n行n-1列的二維表，其中第i行第j列的元素表示和第i個選手在第j天比賽的選手號。
採用分治策略，可將所有參加比賽的選手分成兩部分，n=2^k 個選手的比賽日程表就可以通過n=2^（k-1） 個選手的的比賽日程表來決定。遞歸的執行這樣的分割，直到只剩下兩個選手，比賽日程表的就可以通過這樣的分治策略逐步構建。
說個大白話就是：先默認構造日程表第一行，即0，1，2，3，...然後先分割日程表，將左上角複製到右下角，右上角複製到左下角
初始化第一行不做贅述，讓chess[0][i] = i+1即可
下面在Excel中用圖示做一演示
代碼實現
/** * 將比賽日程表設計成n行n列，表中除了第一列，其他n-1列才是我們要的，數組下標行列都從0開始，第i行j列代表第（i+1）位選手在第j天的對手： * 表格初始化會將第一行按1到n一次填充，然後遞歸填充下面的，用左上角和右上角分別去填充右下角和左下角，因為要是對稱矩陣（具體原因好好想想） * @param p 表示行序號 * @param q 表示列序號 * @param t 表示當前傳進函數方格的規模也就是大小 * @param arr 表格 */public static void arrange(int p, int q, int t, int arr[][]){ if(t>=4){ //如果規模大於4，就繼續遞歸 arrange(p,q,t/2,arr); arrange(p,q+t/2,t/2,arr); } //填左下角 for(int i=p+t/2;i