在昨天介紹遞迴函式的最後，曾經提到在我們面對複雜的問題時，遞迴的優勢便是我們可以把複雜的問題拆開成多個較小的部分來看，今天我們將會針對拆開問題這個部分進行更多的討論。

在前面提到的把問題拆開的方法，我們一般會將其稱為分治法 (divide-and-conquer paradigm)。實際上，它屬於一種演算法的基礎框架，是程式設計中較進階的部分。不過由於它的概念相對來說比較簡單，而且在使用遞迴函式時也經常會被提到，因此就讓我們來了解一下分治法吧。

分治法的基本概念是把一個大問題拆開變成小問題再解決，它提出的想法是一個看起來複雜的大型問題通常都是由多個問題組合而成，因此當我們把問題分解 (Divide) 成多個小問題後再把它們一一解決 (Conquer) 時，再重新把解決後的小問題合併 (Combine) 回來檢視便會發現原來的大問題也已經被解決掉。綜上所述，我們可以發現，分治法指的就是三個重要的步驟：

1. 分解 (Divide)： 把問題拆開成多個相同或相似的小問題
2. 解決 (Conquer)： 當小問題無法再被拆開時，我們便試著思考如何解決那些小問題
3. 合併 (Combine)： 把小問題解決後，我們再試著把小問題的解重新組合起來，這時候得到的結果便是原來問題的解

從合併排序法中看分治法

每次提到分治法時，合併排序法 (Merge Sort) 都會被用來當範例，這是因為它是一種以分治法為基礎而設計的演算法。因此，今天就讓我們也以合併排序法為例子，並從它的思考方式來了解分治法吧。

問題：把以下的數字從小至大進行排序

[94, 83, 56, 33, 60, 47, 54, 88]

在沒有學過演算法的基礎下，這無疑是一個有點複雜的問題，那我們可以怎麼解決它呢？

1. 分解大問題
首先把多個數字進行排序的話的確很困難，但如果今天只有兩個數字的話又如何呢？當我們從八個數字減少到兩個數字時，我們突然會發現問題變成了兩個數字比較大小，這樣問題就簡單許多了，因為我們只需要使用 if-else 陳述式就能做到。所以，我們可以先把八個數字拆開來，變成四組兩個數字的比較組合，而其中一個最直觀的分組方式就是把數字集合不停的從中間分開，直到每一個數字都是各自獨立的，再把它們兩兩分組進行比較。

94 83 56 33 60 47 54 88 - 原來的數字集合
94 83 56 33|60 47 54 88 - 第一次從中間分開
94 83|56 33|60 47|54 88 - 第二次從中間分開
94|83|56|33|60|47|54|88 - 第三次從中間分開
94 vs 83|56 vs 33|60 vs 47|54 vs 88 - 兩兩分組進行比較

2. 解決小問題
當問題變成比較兩個數字的大小並把較小的數字排在前面時，問題就簡單多了，這時候我們只要準備陣列再把比較的結果儲存進去就可以了。

94 vs 83|56 vs 33|60 vs 47|54 vs 88 - 兩兩分組進行比較
[83, 94]|[33, 56]|[47, 60]|[54, 88]

3. 把小問題的解合併
當我們把每一個分組都順利的比較完畢並儲存起來後，下一步便是時候把它們重新組合回大問題了。可是，我們要怎麼合併呢？如果直接把所有的陣列合在一起的話，我們會發現，它們還不是完成排序的狀態。

[83, 94, 33, 56, 47, 60, 54, 88] - 比起一開始，有種排序過卻又並不完全的感覺

這時候便要再次回到分解大問題的步驟了，既然我們不能直接把所有的陣列合在一起的話，那麼再次分解成兩兩分組後才合在一起又如何呢？當然，直接合在一起的話就跟上面沒有分別了，因此這次我們需要善用從前面的步驟得到的結果，那就是每一個小陣列都是把較小的數字排在前面的，因此，我們可以先儲存第一個數字再儲存第二個數字試試看。

[83, 94]|[33, 56]|[47, 60]|[54, 88]
[94][56]|[60][88] -> [83, 33]|[47, 54] - 儲存小陣列的第一個數字
[83, 33, 94, 56]|[47, 54, 60, 88] - 儲存小陣列的第二個數字

看起來好像好一點了，我們會發現第二組的數字已經是正確排序的狀態，可是第一組的數字還是錯誤的，這代表我們的方法還差了一點關鍵。這時，當我們重新去看儲存小陣列的第一個數字跟第二個數字的步驟時，我們便可以發現即使數字是從小到大儲存在小陣列中，可是小陣列跟小陣列之間卻不一定是前面比較小，甚至有可能出現小陣列的第一個數字比另一個小陣列的第二個數字還要大。因此，我們這次在合併小陣列時再次像解決小問題時從各自的第一個數字開始逐一比較大小並儲存吧：

[83, 94]|[33, 56]|[47, 60]|[54, 88]
[83, 94][56]|[60][54, 88] -> [33][47] - 83 vs 33, 47 vs 54
[83, 94][]|[60][88] -> [33, 56][47, 54] - 83 vs 56, 60 vs 54
[94][]|[][88] -> [33, 56, 83][47, 54, 60] - 不用比較, 60 vs 88
[][]|[][] -> [33, 56, 83, 94][47, 54, 60, 88] - 不用比較
[56, 83, 94][47, 54, 60, 88] -> [33] - 33 vs 47
[56, 83, 94][54, 60, 88] -> [33, 47] - 56 vs 47
[56, 83, 94][60, 88] -> [33, 47, 54] - 56 vs 54
[83, 94][60, 88] -> [33, 47, 54, 56] - 56 vs 60
[83, 94][88] -> [33, 47, 54, 56, 60] - 83 vs 60
[94][88] -> [33, 47, 54, 56, 60, 83] - 83 vs 88
[94][] -> [33, 47, 54, 56, 60, 83, 88] - 94 vs 88
[][] -> [33, 47, 54, 56, 60, 83, 88, 94] - 不用比較

這樣，我們就終於得到了正確的排序結果了。

而回顧以上合併排序法的思考流程後，我們可以歸納出以下的重點：

1. 分解大問題後問題的目的並不會亦不應變化
在上面的例子中，雖然我們透過把八個數字減少到兩個數字來讓問題的方向從排序轉變為單純的比較大小，可是我們可以看到小問題的目的仍然是把較小的數字排在較大的數字的前面。

2. 分解、解決跟合併並不是互不關聯的步驟
我們很容易會在看到分治法有三個步驟時便把三個步驟想成是互不關聯的，但事實上卻不是如此。從上面的例子中可以看到，我們在合併小陣列時還是會包含分解的想法跟解決的方法在裡面。

從分治法的思想學會把問題拆開的習慣

對程式有一定認識的讀者可能會發現，這篇文章一直沒有提到一個分治法的特點，那就是它必須要搭配遞迴函式來使用。一般來說，分治法是透過遞迴函式來完成它的三個步驟的。不過，我覺得分治法最重要的是它把問題拆開的思想，因此並沒有著墨於它與遞迴函式的關係。

我認為，從分治法中，比起學習如何使用遞迴函式，更重要的是要學習如何把問題拆開並把它變成我們的一種習慣。很多程式新手在學習分治法後只是把它看成一種遞迴函式的應用方式，因此會覺得它可以使用的地方很少。可是，如果我們學會了它的思想，並養成遇到難以解決或複雜的問題時便試著把它拆開成多個小問題的習慣的話，雖然可能會因為拆開來的小問題種類繁多而使我們不能使用遞迴函式跟分治法，但我們仍然可以透過這些小問題更容易的看到問題的解決方法。