當數學歸納法遇上遞迴：簡介遞迴演算法的設計 When Mathematical Induction Meets Recursion - Introduction to the designing process of recursion algorithm (revision 2) 前言 前面已經有二位真‧強者發過遞迴文了，想必大家已經看懂遞迴在搞 什麼鬼。如果還沒有看懂，就看這一篇，讓你看完之後，可以對遞迴 有更進一步的認識；如果已經看懂的，就看這一篇，讓我用數學歸納 法來攪亂你已經搞懂的觀念XD！ 這一篇，不著重在遞迴怎麼寫，或遞迴怎麼運作的。我把焦點集中在 如何構思一個遞迴演算法。希望透過這一篇，可以讓大家對遞迴有更 深一層的認識。 數學歸納法簡介 所謂的數學歸納法，應該可以算是整數五大公設之一(我不確定)，它 的內容如下： 當一個敘述滿足 1. 在 n == 1 成立 2. 假定 n == k 成立時，n == k + 1 亦成立 我們就可以說此敘述在 n 為正整數的時候都會成立。其中，我們稱 條件 1 為歸納基底(Induction Basis)，條件 2 為歸納假設(Induc- tion Hypothesis)。 舉例來說，我們來證明 1 + 2 + 3 + .... + n == 0.5 * n * (n + 1) Pf: 1. 在 n == 1 時，顯然成立。 2. 假設在 n == k 時成立 我們有 1 + 2 + 3 + ... + k == 0.5 * k * (k + 1) 我們二邊同加 k + 1 1 + 2 + 3 + ... + k + (k+1) == 0.5 * k * (k + 1) + (k+1) == (k + 1) * (0.5 * k + 1) == 0.5 * (k + 1) * (k + 2) == 0.5 * (n') * (n' + 1), n' = k + 1 我們推得 n == k + 1 亦成立 3. 因為 1 2，由數學歸納法，可知適用所有 n 屬於正整數，原命 題皆正確。 從這一個證明我們學到了什麼？ 1. 我們要有一個歸納基底(Induction Basis)，做為證明的源頭 2. 我們假定我們在一定的範圍內會證明原命題，我們也可以證明在 更大的範圍原命題也是正確的，這叫歸納假設(Induction Hypo- thesis)。 3. 從 1 可以推得 2，2 可以推得 3，....，k 可以推得 k + 1， 從而你會解決題目。 遞迴簡介 緊接著歸納法，趁大家還沒有忘掉歸納法之前，我要趕快講遞迴，以 方便我把二者混為一談，讓大家看到數歸就會想到遞迴！ 所有的遞迴，無一例外，都必需要有二個部分，一個是終止條件，一 個是問題拆解。終止條件是用來界定我們什麼時候就不用再繼續化簡 問題（通常是我們已經會處理的小問題或被其他因素限制）；而問題 拆解的部分指的是我們把一個難以解決的大問題拆分為比較容易的小 問題。 來，現在我要催眠你，你相信： 歸納基底可以用來當做遞迴的終止條件， 歸納假設可以用來當做遞迴的問題拆解。 請牢牢記住！催眠結束。 接下來我們來說一下遞迴是什麼？遞迴是一個方法，我們會把一個大 問題拆解為若干個我們會解決的小問題(子問題)，我們透過整合小問 題的結果，來解決最初的大問題。 舉幾個例子： 「考試靠作弊」 考試很難，是一個大問題，我們可以把這一個大問題分成幾個部 分來解決：努力讀書、大量地做考古題、準備一個骰子、作弊。 我們可能會選努力讀書，也可能大量地做考古題，也有可能在做 答的時候擲骰子來猜答案，當然...也有可能作弊(噓)。不論如 何我們會把大問題簡化成上面的小問題(子問題)，最後交出的答 案就會是上面小問題的整合。 當然，為了忠於不知道誰發明的俗諺，我們就假定我們考試的時 候有一些題目我們剛好沒有讀到，也沒有做過類似題、擲骰子每 一次都是尖角向上(見鬼了 XD)，我們考試一定要靠作弊，請問 這是一個有效的遞迴關係嗎？ 也許是，如果你作弊可以得到正確答案；也許不是，如果你不會 也沒有能力作弊之類的。如果作弊這一個子問題可以被解決，它 就是一個有效的遞迴，如果子問題不能被解決，它就不是一個有 效的遞迴關係。 「考試靠作弊，作弊靠隔壁」 在這一步，我們的大問題由「考試」變成了「怎麼作弊」？不要 小看作弊了，作弊的方法千百種，要如何在高風險與高正確性之 間取得平衡是一個大問題(啥鬼?)。所以既然是大問題，我們就 繼續化簡問題。作弊的方法又有很多種，有小抄法、有通訊作弊 法、有左顧右盼法、有前後呼應法、...等等。我們把作弊這一 個大問題又化簡成若干小問題(子問題)。作弊的結果就會是以上 的整合。 當然，又因為一大堆不會抗力之因素，你不能弄小抄、通訊器材 壞掉、耳朵嚨了、嘴巴啞了，只能用左顧右盼法，那請問上面那 一句是用效的遞迴關係嗎？ 也許是，也許不是。關鍵在隔壁的會不會寫考卷，如果會這就是 一個有效的遞迴，如果不會，則作弊這一個子問題不能被解決， 連帶考試也不能被解決，這就不會是一個有效的遞迴。 「考試靠作弊，作弊靠隔壁，隔壁靠牆壁」 我們一路把考試這一個大問題變成隔壁的問題。可是對隔壁來說 考試也是一個大問題呀！他不一定能弄出正確的答案。怎麼辦呢？ 隔壁為了弄出答案，也把考試拆成若干小問題，大部分靠他自己 的聰明才智，有一部分實在寫不出來，可是這又是拿 0 分或拿 100 分的關鍵，他傍惶無助的望著牆壁發呆，希望牆壁上會有提 示。 好了，上面的問題是不是有效的遞迴關係式呢？也許是，也許不 是。關鍵在於牆壁上有沒有提示。如果有，則隔壁會寫，作弊能 得到正確答案，我們就會寫考卷，它就是一個有效的遞迴；如果 沒有，隔壁不會寫，作弊沒有用，我們當然寫不出來，它就不是 一個有效的遞迴。 「考試靠作弊，作弊靠隔壁，隔壁靠牆壁，牆壁倒下去」 像這一句很明顯就不是一個有效的遞迴，因為牆壁倒下去，所以 牆壁上就不會有提示，進而隔壁不會寫，作弊沒有用，我們自己 的考卷當然寫不出來，因此它就不是一個有效的遞迴。 回想一下我們學到了什麼？ 1. 數學歸納法感覺起來和遞迴很有關聯 2. 遞迴是用來大事化小，把大問題變成我們可以解決的小問題 3. 遞迴一定要有一個已知的終止條件(可以是大問題的限制或我們已 經會解決的問題) 4. 考試不能靠作弊，因為牆壁會倒下去！XD 範例一 請寫一段程式計算 1 + 2 + 3 + .... + n。當然，你不可以用公式。 我們要寫一個函式 int sum(int n) 來計算這一個值。 解： 我們回想上面，我們的歸納步驟： 1. 在 n == 1 時，顯然成立。 2. 假設在 n == k 時成立，我們可以推得 n == k + 1 亦成立 3. 因為 1 2，由數學歸納法，可知適用所有 n 屬於正整數，原命 題皆正確。 因為程式語言的限制，為了讓程式的撰寫比較容易，我們稍微修改一 下我們的歸納假設(當然也是對的)： 1. 在 n == 1 時，顯然成立。 2. 假設在 n == k - 1 >= 1 時成立，我們可以推得 n == k 亦成立 3. 因為 1 2，由數學歸納法，可知適用所有 n 屬於正整數，原命 題皆正確。 所以我們可以這樣想：在 n == 1 的時候，我們的 sum 的回傳值很 明顯：就是 1 嘛！然後，我們可以假定我們會算 n == k - 1 的值， 我們要解決 n == k 的問題，在 n == k 的時候， sum 的回傳值要 等於什麼呢？因為我們知道 n == k - 1 的時候 sum 的回傳值會是 前 k - 1 項的和，所以我們在 n = k 的時候，傳回 sum(k - 1) + k。也就是說我們 sum 函式可以這樣寫： 我們的 sum 函式可以這樣寫： int sum(int n) { if (n == 1) { return 1; /* 這是歸納基底 */ } else { return (sum(n - 1) + n); /* sum(n - 1) 是歸納假設 */ } } 這樣寫到底對不對？我們可以用數學歸納法來做正確性證明： 1. 在 n == 1 的時候，sum(1) == 1 顯然成立。 2. 假定在 n == k - 1 的時候，sum(k - 1) == 1 + 2 + ... + (k-1) 我們發現 sum(k) == sum(k - 1) + k == 1 + 2 + 3 + .... + (k-1) + k 所以可以證得 n == k 的時候，sum(k) 亦正確。 3. 由數學歸納法，知 sum 是滿足題意的函式。 回想一下，我們學到了什麼？ 1. 歸納基底可以當成遞迴的終止條件。 2. 歸納假設可以幫我們解決問題(把問題拆解)。 3. 數學歸納法可以幫我們證明演算法的正確性。 範例二 請寫一個程式來列出 n 階河內塔如何從柱 1 移到柱 3。(柱 2 可以 是中繼點) 解： 我們考慮我們要寫一個函式 honai 它會有四個參數，第一個是我們 要移動多少個圓盤，第二個是我們的起點柱子，第三個是我們的終點 柱子，第四個是我們的中繼柱子。 我們先嘗試使用數學歸納法： 1. 歸納基底：n == 1 的時候，直接從起點移到終繼點 2. 歸納假設：假定我們會解決 n == k - 1 的問題，試證我們也會 解決 n == k 的問題。 如果我們會解決 n == k - 1 的問題，我們可以先把起點上前 k - 1 個搬到中繼柱子，把 第 k 個 搬到終點柱子，在把剛才 k - 1 個搬到終點柱子 n == k 時，問題可以被解決！ 3. 由 1 2 證明我們會解決河內塔問題！ int hanoi(int n, int from, int to, int mid) { if (n == 1) { printf("move from %d to %d\n", from, to); } else { hanoi(n - 1, from, mid, to); printf("move from %d to %d\n", from, to); hanoi(n - 1, mid, to, from); } } 結語 從這一篇文章我們可以知道：數歸是一個用來設計遞迴演算法的有利 工具，你可以善用歸納基底、歸納假設弄出形形色色的遞迴，你也可 以用數歸來證明演算法的正確性。當然，設計演算法、證明正確性的 工具不只一種，然而無疑的，數歸卻是我們在高中都學過的XD，而且 是一個相當簡單而優美的方法。我想透過數歸來介紹遞迴應該可以讓 更多人「找到遞迴的真諦」吧。 另外，我想感謝《Introduction to Algorithms: A Creative App- roach》（中譯: 建構式演算法）的作者 Udi Manber。就是他的這一 本書讓我知道數歸與遞迴之間的關係，這是一本好書，建議大家學演 算法的時候可以看看，他用了很多數歸來證明演算法的正確性。 最後我想說：以後我不會在晚上發文了，不知不覺就天亮了。一整晚 沒有睡覺。如果文章有錯是正常的，我現在打一個字的倉頡拆碼都要 想半天，所以還請大家幫忙 DEBUG。謝謝。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.241.166 ※ 編輯: LoganChien 來自: 140.112.241.166 (10/16 08:18) ※ 編輯: LoganChien 來自: 140.112.241.166 (10/16 08:21)