分治策略(Divide and Conquer)是一種常用的算法技術,使用分治策略設計的算法通常是遞歸算法.很多時候我們看明白一個復雜的遞歸都有點費時間，尤其對模型所描述的問題概念不清的時候，想要自己設計一個遞歸那么就更是有難度了。如果遞歸僅僅是循環，估計現在我們就看不到遞歸了。遞歸之所以現在還存在是因為遞歸可以產生無限循環體. ### 用歸納法來理解遞歸 數學都不差的我們，第一反應就是遞歸在數學上的模型是什么。畢竟我們對于問題進行數學建模比起代碼建模拿手多了。 自己觀察遞歸，我們會發現，遞歸的數學模型其實就是歸納法。即:歸納法適用于想解決一個問題轉化為解決他的子問題，而他的子問題又變成子問題的子問題，而且我們發現這些問題其實都是一個模型，也就是說存在相同的邏輯歸納處理項。當然有一個是例外的，也就是遞歸結束的哪一個處理方法不適用于我們的歸納處理項，當然也不能適用，否則我們就無窮遞歸了。這里又引出了一個歸納終結點以及直接求解的表達式。如果運用列表來形容歸納法就是： - 步進表達式：問題蛻變成子問題的表達式 - 結束條件：什么時候可以不再是用步進表達式 - 直接求解表達式：在結束條件下能夠直接計算返回值的表達式 - 邏輯歸納項：適用于一切非適用于結束條件的子問題的處理，當然上面的步進表達式其實就是包含在這里面了。 ### 分治策略一般性描述 把上面的設計思想加以歸納,可以得到分治算法的一般描述.設P是待求解的問題,|P|代表問題的輸入規模,一般的分治算法Divide-and-Conquer偽碼描述如下: ~~~ 算法 Divide-and-Conquer(P) 1. if |P| < c or |P| = c then S(P) 2. divide P into P1,P2,P3,...,Pk 3. for i = 1 to k do 4. yi ← Divide-and-Conquer(Pi) 5.Return Merge(y1,y2,y3,....,yk) ~~~ ### 需要滿足的兩個條件 編程人員還是停留在“自己調用自己”的程度上。這其實這只是遞歸的表象（PS:嚴格來說連表象都概括得不全面，因為除了“自己調用自己”的遞歸外，還有交互調用的遞歸）。而遞歸的思想遠不止這么簡單。遞歸，并不是簡單的“自己調用自己”，也不是簡單的“交互調用”。它是一種分析和解決問題的方法和思想。簡單來說，遞歸的思想就是：把問題分解成為規模更小的、具有與原問題有著相同解法的問題。比如二分查找算法，就是不斷地把問題的規模變小（變成原問題的一半），而新問題與原問題有著相同的解法。有些問題使用傳統的迭代算法是很難求解甚至無解的，而使用遞歸卻可以很容易的解決。比如Hanoi塔問題。但遞歸的使用也是有它的劣勢的，因為它要進行多層函數調用，所以會消耗很多堆棧空間和函數調用時間。 既然遞歸的思想是把問題分解成為規模更小且與原問題有著相同解法的問題，那么是不是這樣的問題都能用遞歸來解決呢？答案是否定的。并不是所有問題都能用遞歸來解決。那么什么樣的問題可以用遞歸來解決呢？一般來講，能用遞歸來解決的問題必須滿足兩個條件： - 可以通過遞歸調用來縮小問題規模，且新問題與原問題有著相同的形式。 - 存在一種簡單情境，可以使遞歸在簡單情境下退出。 如果一個問題不滿足以上兩個條件，那么它就不能用遞歸來解決。為了方便理解，如斐波那契數列來說下：求斐波那契數列的第N項的值。這是一個經典的問題，說到遞歸一定要提到這個問題。斐波那契數列這樣定義：f(0) = 0, f(1) = 1, 對n > 1, f(n) = f(n-1) + f(n-2) 這是一個明顯的可以用遞歸解決的問題。讓我們來看看它是如何滿足遞歸的兩個條件的： - 對于一個n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是說規模為n的問題，轉化成了規模更小的問題； - 對于n=0和n=1，存在著簡單情境：f(0) = 0, f(1) = 1。 因此，我們可以很容易的寫出計算費波納契數列的第n項的遞歸程序： ~~~ int fib(n){ if(n == 0) return 0; else if(n == 1) return 1; else return f(n-1) + f(n-2); } ~~~ 在編寫遞歸調用的函數的時候，一定要把對簡單情境的判斷寫在最前面，以保證函數調用在檢查到簡單情境的時候能夠及時地中止遞歸，否則，你的函數可能會永不停息的在那里遞歸調用了。 ### 兩個熟悉的例子 先看兩個熟悉的例子:字符串回文現象的遞歸判斷和二分查找算法 #### 字符串回文現象的遞歸判斷 回文是一種字符串，它正著讀和反著讀都是一樣的。比如level,eye都是回文。用迭代的方法可以很快地判斷一個字符串是否為回文。用遞歸的方法如何來實現呢？首先我們要考慮使用遞歸的兩個條件： - 這個問題是否可以分解為形式相同但規模更小的問題？ - 如果存在這樣一種分解，那么這種分解是否存在一種簡單情境？ 先來看第一點，是否存在一種符合條件的分解。容易發現，如果一個字符串是回文，那么在它的內部一定存在著更小的回文。 比如level里面的eve也是回文。 而且，我們注意到，一個回文的第一個字符和最后一個字符一定是相同的。所以我們很自然的有這樣的方法：先判斷給定字符串的首尾字符是否相等，若相等，則判斷去掉首尾字符后的字符串是否為回文，若不相等，則該字符串不是回文。注意，我們已經成功地把問題的規模縮小了，去掉首尾字符的字符串當然比原字符串小。 接著再來看第二點， 這種分解是否存在一種簡單情境呢？簡單情境在使用遞歸的時候是必須的，否則你的遞歸程序可能會進入無止境的調用。對于回文問題，我們容易發現，一個只有一個字符的字符串一定是回文，所以，只有一個字符是一個簡單情境，但它不是唯一的簡單情境，因為空字符串也是回文。這樣，我們就得到了回文問題的兩個簡單情境：字符數為1和字符數為0。 綜上兩點分析,滿足分治策略需要滿足的兩個條件了.即編寫出解決回文問題的遞歸實現如下代碼所示.: ~~~ int is_palindereme(char *str, int n){ printf("Length: %d \n",n); printf("%c ----- %c\n", str[0], str[n-1]); if(n == 0 || n == 1) return 1; else{ return ((str[0] == str[n-1]) ? is_palindereme(str+1, n-2) : 0); } } ~~~ 運行結果[ ](http://www.nowamagic.net/librarys/veda/detail/2317) [ ](http://www.nowamagic.net/librarys/veda/detail/2317) #### 二分查找算法的遞歸實現 典型的遞歸例子是對已排序數組的二分查找算法。現在有一個已經排序好的數組，要在這個數組中查找一個元素，以確定它是否在這個數組中，很一般的想法是順序檢查每個元素，看它是否與待查找元素相同。這個方法很容易想到，但它的效率不能讓人滿意，它的復雜度是O(n)的。現在我們來看看遞歸在這里能不能更有效。 還是考慮上面的兩個條件： - 第一：這個問題是否可以分解為形式相同但規模更小的問題？ - 第二：如果存在這樣一種分解，那么這種分解是否存在一種簡單情境？ 考慮條件一：我們可以這樣想，如果想把問題的規模縮小，我們應該做什么？可以的做法是：我們先確定數組中的某些元素與待查元素不同，然后再在剩下的元素中查找，這樣就縮小了問題的規模。那么如何確定數組中的某些元素與待查元素不同呢？ 考慮到我們的數組是已經排序的，我們可以通過比較數組的中值元素和待查元素來確定待查元素是在數組的前半段還是后半段。這樣我們就得到了一種把問題規模縮小的方法。 接著考慮條件二：簡單情境是什么呢？容易發現，如果中值元素和待查元素相等，就可以確定待查元素是否在數組中了，這是一種簡單情境，那么它是不是唯一的簡單情境呢？ 考慮元素始終不與中值元素相等，那么我們最終可能得到了一個無法再分的小規模的數組，它只有一個元素，那么我們就可以通過比較這個元素和待查元素來確定最后的結果。這也是一種簡單情境。 這個問題可以用遞歸來解決，二分法的代碼如下： ~~~ void selectionSort(int data[], int count){ int i, j, min, temp; for(i = 0; i < count; i ++) { /*find the minimum*/ min = i; for(j = i + 1; j < count; j ++) if(data[j] < data[min]) min = j; temp = data[i]; data[i] = data[min]; data[min] = temp; } } int binary_search(int *data, int n, int key){ int mid; if(n == 1){ return (data[0] == key); } else{ mid = n/2; printf("mid=%d\n", data[mid]); if(data[mid-1] == key) return 1; else if(data[mid-1] > key){ printf("key %d 比 data[mid-1] %d 小，取前半段 \n", key, data[mid-1]); return binary_search(&data[0], mid, key); } else{ printf("key %d 比 data[mid-1] %d 大，取后半段 \n", key, data[mid-1]); return binary_search(&data[mid], n - mid, key); } } } ~~~ 程序運行結果：  這個算法的復雜度是O(logn)的，顯然要優于先前提到的樸素的順序查找法。 ### 小結 遞歸的基本思想是把規模大的問題轉化為規模小的相似的子問題來解決。在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況。另外這個解決問題的函數必須有明顯的結束條件，這樣就不會產生無限遞歸的情況了。 關于[程序算法藝術與實踐](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多討論與交流，敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).