在上一篇文章中談到在使用循環(huán)的算法中，可以利用循環(huán)不變量證明算法的正確性，那如果是使用遞歸的算法呢。
遞歸的算法在計(jì)算中會(huì)形成某種遞歸結(jié)構(gòu)肿轨，因此可以利用結(jié)構(gòu)歸納法來證明正確性。
結(jié)構(gòu)歸納法（Structural induction）
看到這個(gè)名字蕊程，我們會(huì)自然想起數(shù)學(xué)歸納法椒袍。
其實(shí)它是數(shù)學(xué)歸納法的一般化，也就是說數(shù)學(xué)歸納法是它的特殊化藻茂。
它用于證明驹暑，某種遞歸結(jié)構(gòu) x（list or tree）滿足命題 P (x)，證明方法類似我們熟悉的數(shù)學(xué)歸納法辨赐。
首先提出一個(gè)命題 P (x)优俘，證明最小結(jié)構(gòu)和子結(jié)構(gòu)均滿足命題 P (x)，那么這種遞歸結(jié)構(gòu)滿足命題 P (x)掀序。
而這個(gè)命題經(jīng)過結(jié)構(gòu)歸納法證明后帆焕，能用作證明相應(yīng)算法的正確性。
例子
跟上一篇一樣不恭，我們使用歸并排序（Merge sort）作為例子叶雹，不過這次用到的是它的遞歸函數(shù)。
1: int* merge_sort(int* d, int c)
2: {
3: if (c > 1)
4: {
5: int lc = c / 2;
6: int rc = c - lc;
7: int* sld = merge_sort(d, lc);
8: int* srd = merge_sort(d + lc, rc);
9: return merge(sld, srd, lc, rc);
10: }
11: return d;
12: }
了解歸并排序的朋友會(huì)知道它使用了分治法
分治法的中心思想是把問題遞歸分割為子問題换吧，一直到不能繼續(xù)分割的最小子問題（base case）折晦，最小子問題的解決方法很簡(jiǎn)單明顯，這時(shí)遞歸返回并將子問題的答案逐層合并沾瓦，最后就是原問題的答案了筋遭。
歸并排序的 3 個(gè)步驟分別如下：
- 分割：行 5 得出標(biāo)記分半的數(shù)組索引（將數(shù)組分半）
- 解決：行 7, 8 將分半的數(shù)組分別遞歸解決并返回有序數(shù)組
- 合并：行 9 將 2 個(gè)有序數(shù)組合并為 1 個(gè)有序數(shù)組并返回
假設(shè)原數(shù)組為 [ 5 2 4 7 1 3 2 6 ]，它在分割階段呈現(xiàn)以下的二叉樹結(jié)構(gòu)
當(dāng)數(shù)組大小為 1 時(shí)暴拄，為最小子問題，已經(jīng)到達(dá)遞歸的 base case编饺，且大小為 1 的數(shù)組顯然為有序乖篷，此時(shí)停止遞歸。
在合并階段由底部至頂部逐層合并子問題答案透且，最終數(shù)組是原數(shù)組的有序結(jié)果
[ 1 2 2 3 4 5 6 7 ]撕蔼，如下
證明
首先提出命題
原數(shù)組大小為 n豁鲤，使用歸并排序遞歸分割的，高度為 m 的二叉樹
第 m 層有 2 ^ (m-1) 個(gè)大小為 n / 2 ^ (m-1) 的數(shù)組鲸沮。
然后使用結(jié)構(gòu)歸納法證明：
- 高度為 1 的二叉樹琳骡，顯然根節(jié)點(diǎn)數(shù)組等于原數(shù)組，第 1 層有 1 個(gè)大小為 n 的數(shù)組讼溺。
- 假設(shè)高度為 m 的二叉樹楣号，第 m 層有 2 ^ (m-1) 個(gè)大小為 n / 2 ^ (m-1) 的數(shù)組為真劳澄。
歸并排序的遞歸分割時(shí)琳水，把子問題對(duì)半分割為更小的子問題，因此下一層子問題數(shù)增倍簇爆，子問題大小減半剔猿。
因此第 m + 1 層會(huì)有 2 x 2 ^ (m-1) = 2 ^ m 個(gè)大小為 n / 2 ^ (m-1) / 2 = n / 2 ^ m 的數(shù)組视译。
滿足命題第 m + 1 層有 2 ^ ((m + 1) - 1) = 2 ^ m 個(gè)大小為 n / 2 ^ ((m + 1) - 1) = n / 2 ^ m 的數(shù)組。
因此當(dāng)二叉樹高度為最大值時(shí)归敬，已遞歸分割至最底層（數(shù)組大小為1不能繼續(xù)分割）酷含，停止遞歸并將子問題答案通過 merge 函數(shù)合并逐層返回，而 merge 函數(shù)在上一篇中已證明其正確性汪茧，因此歸并排序算法的正確性得以證明椅亚。
