所有的計算都是遞歸抖部；要理解遞歸首先要理解遞歸说贝。
程序設計思想之一“遞歸”歷來是同學們的理解難點。據(jù)說慎颗，**要理解遞歸首先要理解遞歸! **當然乡恕，我們有更簡單的理解方法。比如俯萎，我們思考一個簡單的問題：給一個正整數(shù)n傲宜，求1+2+3+...+n的值。
重復強調以下算法設計原則：
1夫啊、明確輸入：正整數(shù)n函卒；
2、明確計算目標：1到n之間整數(shù)的累加撇眯；
3报嵌、設計處理過程。
當然熊榛，這么難的計算锚国，我們還不知道如何處理！即使我們不知道如何處理玄坦，大概也應該能寫出這樣的一個尚不知道處理流程的sum0函數(shù)：
int sum0(int n){
計算累加并賦值給res血筑；
return res绘沉；
}
如果sum0是一個懶惰的家伙，他抗議說：嘿豺总，我可不是高斯车伞，我怎么會算這樣的東西？太難了喻喳！我只知道如果n==1的累加和另玖，就等于1！但是沸枯，如果你告訴我n-1之間整數(shù)的累和的答案res日矫，我倒是可以可以告訴你答案是：n+res! 這家伙真是天才赂弓。
于是我們只好去請另外一個家伙來算是n-1之間的累和绑榴，比如我找到的是sum1，給他一個整數(shù)n-1 盈魁。不可思議的是翔怎，sum1也同樣抗議，嘿杨耙，你幫我算出(N-1)-1之間整數(shù)的累和吧......于是我只好再去找sum2來做接下來的工作赤套。這樣的把戲持續(xù)下去值得有一個天才的輸入是1。如下所示：
sum0(5) ----> sum1(4) ----> sum2(3) ----> sum3(2) ----> sum4(1) ---->1
如果我們要算的數(shù)是n==5珊膜，sum4接到任務的時候容握，輸入是5 - 4 == 1，他剛開口想說车柠，嘿剔氏，太難了，我......但是他只好閉嘴竹祷，因為求1到1之間數(shù)的累加就是1谈跛。好吧，sum4無奈地又沒好氣地對sum3說塑陵，答案是1感憾。這時候sum3也沒辦法偷懶了，因為他必須承擔自己的工作令花，告訴sum2答案阻桅，3。如此不斷地返回兼都，如下所示：
15<---- sum0(5) <--10-- sum1(4) <--6-- sum2(3) <--3-- sum3(2) <--1-- sum4(1)
值得注意的是嫂沉，這一群懶惰的家伙都一個德行而沒有任何差別：告訴我n-1為輸入的累和答案，我就告訴你n為輸入的累和答案俯抖。所以输瓜，作為雇主的話，也許我只需要雇傭一群sum0來干這項工作。因為sum0與sum1(或其他任何一個sum)的處理過程沒有任何區(qū)別尤揣。于是工作流程就變成了：
sum0(5) ----> sum0(4) ----> sum0(3) ----> sum0(2) ----> sum0(1) ---->1
15<---- sum0(5) <--10-- sum0(4) <--6-- sum0(3) <--3-- sum0(2) <--1-- sum0(1)
既然所有的sum都一樣搔啊，我們只需要定義一個新的函數(shù)sum，如下：
int sum(int n){
if(n == 1)
return 1;
return sum(n-1) + n北戏；//遞歸的返回點负芋！
}
以上講的都是設計思想，沒有涉及具體遞歸程序在計算機中的實現(xiàn)嗜愈。以下描述遞歸在計算機中的實現(xiàn)旧蛾，與教科書不同，為了幫助理解我們犧牲了一定的嚴謹性與準確性蠕嫁∠翘欤看完我這里的描述，希望大家還是要閱讀課本剃毒。
如果把sum程序編譯成機器可執(zhí)行的代碼病袄，我們一定會得到一個指令集，記為sum赘阀。sum(n)表示接受輸入為n的那段程序益缠，當他執(zhí)行到程序最后一句，它要調用自己“本身”基公，大家難理解的是所謂“本身”是什么幅慌。其實沒什么神秘的，如果我們用一種不怎么正確的理解方式轰豆，可以想象sum正常地去拷貝一份sum代碼出來放到內存的某個地方胰伍，給它輸入值n-1，然后等待sum(n-1)給它返回答案秒咨。這里的關鍵點是喇辽，把程序遞歸地調用自己看為對多個自己的代碼拷貝的調用。
還有一個關鍵點是雨席，sum(n-1)必須在返回值給sum(n)菩咨，這里稱為遞歸的返回點。為何一定會返回陡厘？注意抽米，sum程序一開始就設定了遞歸結束的條件：n == 1 。每一次調用sum糙置，n的值都要減1云茸，根據(jù)Well-order principle(不懂就忽略，這里只是告訴你有這個東西)谤饭，必然會在某個時刻使得n到達1标捺，然后sum(1)把值返回給調用它的sum(2)懊纳。準確定義遞歸結束條件是寫遞歸程序首先需要考慮的問題。
注意亡容，return這個關鍵詞可不是只是返回一個值這么簡單嗤疯。程序應該如何在內存中駐留，程序該如何執(zhí)行闺兢，如何返回（return干了啥）等茂缚，這些都不不是本文的內容。請參看相關課本內容屋谭。
擴展一小步脚囊，把求n的累加變成求n-1的累加，也可以直觀地把這種思路理解為桐磁，當我們要解一個大的問題悔耘，我們可以把問題分解成小問題，然后根據(jù)小問題的答案來整合出整個大問題的答案所意。試試做以下思考：
作業(yè)：
1淮逊、求n階乘：等于求n-1的階乘，再乘上n扶踊；
2、二分查找：把數(shù)據(jù)分為兩部分郎任，根據(jù)條件在某一部分進行檢索秧耗；
3、歸并排序：對n個數(shù)值進行排序等同于對兩次n/2數(shù)值的排序的歸并舶治；
4分井、GCD：求A和B的最大公因子，等于求更小數(shù)值B與A % B的GCD霉猛；
從解決問題的角度尺锚，遞歸的思想就是一種解決問題的方法，被廣泛地應用在程序設計中惜浅。說到嚴謹?shù)倪f歸理論瘫辩，其實，在高校不傳已久咯坛悉，《計算理論導引》有此方面的嚴格理論描述伐厌。
2017年7月整理
