最近看了遞歸，看得我頭皮發麻，石樂志。所以就找個時間把所學都總結整理一下。所有的都是學自《PRogramming abstraction in C++》. 大多數的用來解決編程的算法策略都有不在計算領域的計算部分。當我們重復完成一個任務的時候，我們通?？紤]的是循環。當我們做某項界定的時候，我們通?？紤]的是條件控制語句。用的最多的就是 if while還有for語句了。在你解決更多問題之前，你得學會一項強大的解決問題的策略跟工具。這個策略就是我們的遞歸策略。遞歸，就是定義為一種把大問題通過分割到含有同樣形式的小問題的一種策略。（That strategy, called recursion, is defined as any solution technique in which large problems are solved by reducing them to smaller problems of the same form）。遞歸是一種新的思考問題的方式，對初學者來說，很難，想學好就要多練習，多理解。
7.1 A simple example of recursion（遞歸例子）
為了更好的理解遞歸，我們最好就舉個實際的例子。試想一下。你被任命為基金組織的協助者，在為一個志愿者很多，但是資金缺乏的組織工作，你的任務是籌集$1,000,000用于捐贈。
當然，如果你認識哪個大款肯給你出這筆錢，問題就變得很簡單了。但是這樣的幾率幾乎為0. 那么怎么實現這個目標呢？在這里，我們可以嘗試把要籌的款的賬目適當降低，比如每個人出100，這樣如果你有10,000個朋友就能完成目標。但是你又可能沒那么多個朋友，那么我們可以換個思路。你是基金的負責人，我們說了，你的自愿者很多，你可以找10個志愿者小組的組長，向他們每個人要100,000，然后他們通過同樣的方式向下屬要10,000，...... 直到每個人的手中都可以支付起100的時候，就任務完成。那么我們用偽代碼（pseudocode）的形式表示就是：
void collectContributions(int n) {if (n <= 100) {Collect the money from a single donor.} else {Find 10 volunteers.Get each volunteer to collect n/10 dollars.Combine the money raised by the volunteers.}}
這個翻譯我就不寫了。這里的重點是這一句Get each volunteer to collect n/10 dollars.這一步直接就是把錢縮小了10倍，接下來的步驟都是一樣，向接下來的10個人籌錢，唯一不同的就是，n每次都縮小10倍。這時候我們可以很輕松的寫出這一行的代碼了：collectContributions(n / 10)；當然，在這里要記住，n<=100的時候，說明每個人都是可以籌齊100的，就沒有必要再向接下來的10個人籌款，也就是說，不用再調用collectContributions(n / 10)；直接執行 if 里面的語句。
上面的例子結構是一個很典型的遞歸的結構例子，一般的遞歸函數結構都含有一下的結構組成
if (test for simple case) {Compute a simple solution without using recursion.} else {Break the problem down into subproblems of the same form.Solve each of the subproblems by calling this function recursively.Reassemble the subproblem solutions into a solution for the whole.}上面是遞歸函數的模板，我們稱之為遞歸范式（recursive paradigm）。注意，if 里面是simple cases，就是說這部分內容不含遞歸的部分，也可以看做是遞歸的邊界，以后會很經?？吹剿?，這個很重要。也可以理解為數學中的特殊例子當問題滿足了以下的一些特點時，我們可以考慮使用遞歸
1. You must be able to identify simple cases for which the answer is easily determined.2. You must be able to identify a recursive decomposition that allows you to break any complex instance of the problem into simpler problems of the same form.
也就是說，問題能區分出我們的simple cases，并且能將問題遞歸分解為更小的含有同樣形式的函數。
在上敘述的問題中，原始的問題通過將問題分成了更小的子問題，這些小問題都是跟原始問題是同種的形式。這樣的解決問題的遞歸方法，我們稱之為分離—組合算法。這是我自己的理解翻譯的，我也不知道專業術語是不是這樣的。（Because the solution depends on dividing hard problems into simpler instances of the same problem, recursivesolutions of this form are often called divide-and-conquer algorithms）
這里先提到遞歸的主要形式，接下來就會提到具體遞歸的原理跟調用過程。先這樣，晚上再寫（2）。純手寫，就是我翻譯得可能太差，畢竟沒有中文版...
新聞熱點
疑難解答
圖片精選
