在學習數據結構與演算法的時候，一旦出現遞歸就很難理解。請問對於遞歸有沒有什麼好的理解方法？

01-04

出現遞歸就會在紙上畫半天才能理解。感覺腦子總是轉不過來彎。應該怎麼能夠快速的理清遞歸的演算法與思路？

看一下 SICP 前兩章然後做一下習題，接著你就會發現無論寫啥演算法不用遞歸就不舒服……

在用遞歸的時候，就像前面的同學說的那樣，當成一個黑盒子，不要老是想著遞歸這著方法，而是只是把遞歸函數當成一個普通的調用函數，對這個函數，你需要知道他的輸入與輸出。

比如最簡單的n的階乘的遞歸實現，代碼如下。

function factorial (n) { if (n === 1) { return n; } else { return n * factorial(n-1); } }

你在寫這個函數的時候，把函數定義部分代碼蒙起來，主要看這部分代碼

if (n === 1) { // 如果求1的階乘，那麼就直接返回 return n; } else { // n! = n * (n-1)! 這個數學等式 return n * factorial(n-1); }

那這樣看代碼，你懂了嗎？

如果你覺得還不懂的話，且聽我下面說完。

不說性能上面的影響，遞歸的使用能讓你的代碼變得簡單清晰，邏輯變得易懂，就比如下面這段代碼，用非遞歸的方式實現階乘。

function factorial (n) { var result = 1; for (var i = n; i &> 0; i--) { result *= i; } return result; }

這個函數與前面的遞歸函數求值是一樣的，但是在函數邏輯上面差別非常大。

在遞歸函數裡面，運用了一部分的數學邏輯在裡面，能清晰看見數學等式，而非遞歸實現裡面數學邏輯其實是隱藏起來的，是編碼人員在知道數學邏輯的情況下實現，而沒有體現在代碼層面上。這樣在數學邏輯變動的時候，維護起來是不太好的。

好噠，最後再說一句，如果遞歸不能讓你的代碼變得清晰，你自己看代碼也會迷惑，那就不要生硬得用遞歸了。

把遞歸當作一個黑盒方法，而不要跳進這個裡邊，你就能理解了

看到過查字典的比喻挺好的。想像用一本純英文詞典查單詞，要查某一個單詞的意思，翻到這個單詞時，看解釋，發現解釋中有一個單詞不認識，所以，無法明白這個要查的單詞是什麼意思；這時，再用這本詞典（函數本身）查那個不認識的單詞，又發現查的第2個單詞的解釋中又有一個單詞不認識，那麼，又再用這本詞典查第3個不認識的單詞，這樣，一個一個查下去，直到解釋中所有單詞都認識，這樣就到底了，就明白了最後一個單詞是什麼意思，然後一層一層倒回來，就知道我最初想查的第1個單詞是什麼意思了，問題就解決了。

遞歸一般用在可能無限循環下去的操作里，舉個例子，像電腦里的文件夾系統，打開一個文件夾，裡面有很多的文件或文件夾，裡面這些文件夾又可以打開，然後重複上面的過程，你是不知道你在什麼位置結束這個循環的。

所以你不能按順序一句句代碼的寫下去，因為你根本不知道什麼時候結束。這怎麼辦？

用到遞歸的時候，基本上我們想要進行操作都是由一個簡單的小操作重複完成的（實際上是這樣的環境時才用遞歸），那這是就可以寫一個函數來完成這個小操作然後循環就可以了。

比如有個需求，你要計算一個文件夾里總共有多少個文件，這裡的操作單元就是：一個文件夾只計算它下一級的文件數，不用去管它的子文件夾的子文件夾等等更下一層的情況。這樣每個文件夾把它下一級的文件數統計上來，它自身的文件數就是對的。

或者舉個更生活的例子，學校要統計去參加XX活動的人數，從上至下是學校-&>院系-&>專業-&>年級-&>班,雖然有很多層,但是對於系裡面來說，它只要把專業統計的人員加起來就可以了，不用去管年級、班級的人數，其他層也是一樣，它只管它下一級的人數。

所以我覺得很重要的是怎麼把一個任務合理的拆分成可以重複的單元，然後函數本身只要實現這個重複的這段操作就可以了。

這個和數學裡面一個證明方法很像，方法思路大概是：

1.參數為0的時候是正確的

2.假如參數為n的時候是正確的，可以得出n+1的時候是正確的，

滿足這兩個條件，那麼對於任何參數都是正確的。

這個過程是開始是固定的，但是沒有結尾，是從開始想遠處推倒。

遞歸呢，是整個過程有一個結尾，比如文件夾一直打開最後你肯定會遇到一個空文件夾或者全部是文件的文件夾，循環終止，是一個從任意處向終點推倒的過程。函數完成後的效果肯定是你選擇任意一個文件夾，它都可以計算出總共的文件數，所以看似是起點已知，但實際起點是任意的。

貼個示例代碼：

//文件 struct file { char* name; };


//文件夾

struct folder{

    struct folder* subfolders;

    int folderNum;

    struct file* files;

    int fileNum;

};

int countFiles(struct folder fol) { int num = fol.fileNum; //循環子文件夾，把文件數加起來 for (int i = 0; i&< fol.folderNum; ++i) { struct folder subFolder = fol.subfolders[i]; num += countFiles(subFolder); //在這個位置形成遞歸；但是你要計算的是fol的數量，你只需要直接使用subFolder的數量 //就像是接力賽，你要相信對subFolder的計算式正確的，在這個基礎上計算當前這個層級數量 } return num; }

之前也被遞歸折磨過，百思不得其解。

現在好點了，最少不是談遞歸色變。我的做法是：

首先找到遞歸學不好的癥結。是見得少（只知道fibonacii這個入門遞歸，一葉障目）？還是練得少（道理我都懂，但是手還是生）？無論是哪種癥結，都可以通過多看，多練（這個真的很重要）來減緩
然後忘記遞歸，去練習各種經典的演算法。二叉樹，圖，排序等。一定要寫代碼，一定要寫代碼，一定要寫代碼。

以上做法的效果是，你對遞歸是什麼，用在哪裡，不同的演算法怎麼用有了更深入的認識，而不是只停留在了概念。

你有兩個問題要解決：這麼寫什麼意思，和這麼寫對不對。

第二個問題是正兒八經證明程序正確性，請刷數學歸納法。

你還是先解決第一個問題吧。你把執行棧，棧幀，和函數調用，函數返回之間的關係理一理就好了，參數壓棧返回地址壓棧之類的。不用管遞歸不遞歸。

在紙上畫畫棧幀是不錯的方法，多畫幾次執行棧就瞭然於心了。

關於遞歸，可以參見這個問題答案：

請問對於遞歸有沒有什麼好的理解方法？

如果你想要理解遞歸的話。。。

那麼你必須要先理解遞歸。。。

費波那契數列對理解遞歸還是有用的，遞歸如果在腦袋裡面想不好理解的話，可以寫一個遞歸步驟少一些遞歸三四層的簡單例子，在紙上把調用過程用樹結構畫出來就很容易理解了，多畫幾遍就徹底理解了，有個例子可以寫對角線走九宮格試試

一層層向里想，到最裡層再回溯想。。。。

設計和理解的時候

不要急於很精細的去設計和理解

要粗略

如：foo(n) {foo(n-1)}

大致理解成foo反覆調用自己，就ok了

接下來在考慮如何修正（精細化）這個foo()函數

即：初始情況應該怎麼樣？何時結束

考慮到這兩點，正確的foo就寫出來了

我很少一次性寫對一個遞歸函數，很多時候我是寫個大概，然後debug，讓調試器告訴我哪裡還需要修正

雖然土了點

但這並不影響我寫出引以為豪的代碼

我個人覺得使用遞歸解決問題的一個關鍵思路是找到一個『通項公式』，例如菲波拉契數列的通項公式是：f(n)=f(n-1) + f(n-2)，顯然這裡的隱含條件是n&>=2，所以我們意識到f(0)和f(1)應該作為初始條件給出，這是形成的遞歸併能夠計算出結果的前提條件。

同樣，對f(n)=1-2+3-4……n這樣一個問題，簡單粗暴的方法的是根據奇偶累加(我因為使用了這種簡單粗暴的方法被面試官鄙視)，注重技巧性的方法是計算出通項公式：

當n為偶數時，顯然應該有n/2個-1，此時結果為-n/2；當n為奇數時，顯然結果為-(n-1)/2 + n，此時結果為(n+1)/2。

那麼還有沒有更加優雅的解法呢？答案是遞歸啊，我們可以注意到當n為奇數時，f(n) = f(n-1) + n，而f(n-1)顯然表示偶數項的和，可以直接計算出來，這樣在這個問題中我們就使用到了遞歸。

綜上所述，使用遞歸解決問題的關鍵是找到一個「通項公式」，可是是不是使用遞歸就一定代表著效率更好呢？這個問題留給大家思考！~(≧▽≦)/~

作為菜鳥回答一下。

遞歸和信任密不可分。

相信自己的階乘函數f可以計算n-1的值，相信自己的f(n-1)返回正確結果，那麼f(n)的實現就是return f(n-1)*n了，。

之後萬一n==0,就返回1，萬一n不是正整數就報錯，可以等報錯stackoverflow error 再添代碼啊。

想要理解別人的遞歸，你需要理解別人那種信任的心情吧

去學習一下 Lisp

理解方法沒有我當時也是很不理解用了最簡單粗暴的方法

用筆遞歸調用了那一語句就把這條語句的執行結果寫在紙上直到所有遞歸都結束

最後你會發現原來遞歸是這樣子

然後就再也沒有擔心過遞歸了

多做幾次很有成效跟學弟也是這樣說的效果不錯

1. 學習棧幀的構成，深刻理解函數調用過程中，參數的傳遞、局部變數的創建、函數返回值的生成返回過程

針對1中內容，可以學習《深入理解計算機系統》相關章節，或者直接到網上度一篇關於棧幀構成的好文，學習一下。

2. 我想提一點，參數傳遞，值傳遞、引用傳遞，對這兩點的不同要理解透徹。

3. 遞歸本質上就是函數層層調用，為什麼遞歸有深度限制，os為什麼要限制遞歸的深度？這又跟操作系統對進程的管理有關。那麼虛擬機，比如jvm是否有不同？這些算是我給你拋個點子，你可以思考一下。

遞歸將連續的類似過程分解，並一個函數作為單個過程的載體，通過不斷調用自身以進入下一過程。

如果理解不了的話，先理解尾遞歸

int fun(){

//pass

return fun;

}

遞歸遞歸，遞推回歸……拆開理解

抓住重複，善用棧圖。