如何學習遞歸呢？

01-03

如何才能用遞歸來思考該用遞歸思考的問題，有什麼書可以學習？我感覺平時項目中很少用到遞歸，不像面向對象平時有書看，做項目的話也都是面向對象，久而久之就越來越提高。遞歸的話，怎麼進步呢？
最近在編一個和數據結構Tree有關的代碼，深感遞歸水平之低下啊。
昨天在Stack overflow上看到Eric Lippert大大也在教別人遞歸，他教了一個遞歸公式。他的遞歸公式如下：
Result M(Problem prob)

{
if (&
)
return &;
// The problem cannot be solved easily.
Problem smaller1 = &
Result result1 = M(smaller1);
Problem smaller2 = &
Result result2 = M(smaller2);
...
Result finalResult = &

return finalResu<
}
原帖 http://stackoverflow.com/questions/9304469/how-to-perform-a-recursive-search/9314805#9314805
請問這個遞歸公式很好用嗎？怎麼今天我套了半天都套不出來呢？當然Eric Lippert舉的二叉樹的例子我是看懂了

感謝 @Edwin邀請。

這個問題要分兩點看：

如果樓主的意思是要問遞歸的程序怎麼寫，那麼@小白說的其實也就是我說的：我看不出遞歸有什麼需要學的。在我們從小到大的數學課里最直接能表示成遞歸的就是數學歸納法和菲博那契數列。比如：

f(n) = f (n - 1) + f(n - 2), f(1) = 0, f(2) = 1

變成如下形式：

def f(n):

if n &< 0:

raise Exception()

elif n == 1:

return 0

elif n == 2:

return 1

else:

return f(n - 1) + f(n - 2)

很直接也很明白。如果要調試，插入幾個print語句看中間數據也就能看明白了。有什麼需要學的？

除非樓主是想問，怎麼對一個問題建模並轉化為遞歸的形式。那麼這個問題就大了。首先建模這東西超出了程序的範疇，那其實已經是數學的一部分。多數情況下程序員面對的不是這個，我的意思是：現在大多數應用不需要程序員設計演算法，合理地理解現有的演算法並選擇合適的應用到程序中就夠了。其次，對如今業界常用的工程語言來說（C以及衍生語言，各種腳本語言，但不包括多數函數式語言），遞歸在多數情況下不是一個高效的解決方案，所以用不著刻意地去模仿。

與其去考慮怎麼找一個好用的萬能程序框架，還不如靜下心來寫一些有真正功能的工具，或者讀一些開源的代碼。等你的閱歷多了，也許慢慢就能理解其中的不同。

要理解遞歸，先理解遞歸。。

當你的問題分析透徹，何時使用遞歸就會自然明了。遞歸只是一種函數調用的技巧，不是解決問題的公式。一個問題可以用遞歸做，也可以不用遞歸做，遞歸不是必須的。所以，理解你需要解決的問題，想清楚解決問題的步驟方法，你會突然發現，原來可以用遞歸來簡化問題。不要一開始就想著如何用遞歸。

更新1：

一個經典利用遞歸的例子

http://www.oschina.net/translate/regular-expression-matcher-code-by-rob-pike

其實這是個挺奇怪的問題，遞歸是不需要特殊學習的吧，理解了，自然就懂得怎麼用了。書的話，沒有專門用來講遞歸的，但是任何一本C或者C++的書籍都會講到遞歸。很多書上都會說，遞歸是最複雜和難以理解的部分，可是我卻認為，遞歸是最容易理解，最符合人的邏輯思維的方式。

剛在看一本書，剛好講到遞歸的定義，很有意思，摘抄如下：

」遞歸的定義如下：

遞歸：

參見『遞歸』。

什麼？這個定義什麼都沒說啊！好吧，改一下：

遞歸：

如果你還是沒明白遞歸是什麼意思的話，參見『遞歸』

」

看懂了吧，其實只是自己調用自己罷了，間接的調用自己也算。

練習的話，搞懂「漢諾塔」問題，應該就算是學會了，還是那句話，理解了自然就會用了。

至於你說的，實際項目中很少用到遞歸，是因為大部分情況下，遞歸的效率會很低，因為要不斷的重複函數調用過程。

By the way, 很早之前我發現，「九連環」這個遊戲也是一個遞歸的過程，提問者真的感興趣，可以買一個九連環來玩一下，玩熟了，你的遞歸也就練好了。

一個九連環不貴，幾塊錢，比買書省錢多了。

個人感覺和建議，有2點：

寫出遞歸函數也就是要處理好遞歸的3個主要的點: a)出口條件，即遞歸「什麼時候結束」，這個通常在遞歸函數的開始就寫好; b) 如何由"情況 n" 變化到"情況 n+1", 也就是非出口情況，也就是一般情況——"正在"遞歸中的情況； c) 初始條件，也就是這個遞歸調用以什麼樣的初始條件開始
可以說，上述a,b,c三個條件組成了我們的遞歸函數；解決好上述3點，也就很容易地寫出一個遞歸函數；剩下的就是去學習學習「數學歸納法」，請自己google之；不許要你稱為歸納法專家，但只需要認證體會它的思路，對於你理解和創造遞歸函數有很大幫助

刷題目，圖的廣度、深度遍歷、動態規劃等等，刷個幾十道。

謝邀。

我們從小，就一直聽著一個遞歸的故事長大：從前有座山，山裡有座廟，廟裡有個老和尚在講故事，老和尚在講：從前有座山，山裡有座廟.......

關於遞歸的學習，有一個很經典的例子：在學習遞歸，首先，你應該學習一下，什麼是遞歸。

遞歸是一種思考問題、描述問題的方法。一個基本的思想就是，把一個複雜問題化為一系列簡單問題的重複。

我們以遍歷樹為例，遍歷一棵樹，首先先從根節點開始，首先先遍歷根節點下的每一個子節點，然後，再把這些子節點，作為一個新的樹的根節點，重複上述的遍歷過程。偽代碼如下

tree_travel( tree_node root )
{
foreach( node in root.children )
tree_travel( node );

}

通過這個例子，我們可以發現，遞歸還有一個特點，就是問題的規模和解決問題的方法沒有關係，或者只是一個參數沒有很大的影響。遞歸所做的，就是把複雜的問題一級一級的展開，使得每一級的處理方法都一模一樣。我們在講一下漢諾塔的例子，我們假設三個柱子分別是ABC，盤子由小到大分別用1、2、3...表示。

對於兩個盤子的情況：

首先，先將1盤子從A移動到B，然後將2盤子從A移動到C，最後將1盤子從B移動到C。

三個盤子的情況：

首先，先將1、2盤子從A移動到B，然後將3盤子從A移動到C，最後將1、2盤子從B移動到C。

那麼1、2兩個盤子怎麼樣從A移動到B，再從B移動到C呢？其實，這個問題我們剛剛在舉兩個盤子的例子的時候已經解決過了。

那麼，對於64個盤子的情況，我們也可以很容易解決。

首先，先將1，2，3......63盤子從A移動到B，然後將64盤子從A移動到C，最後將1，2，3......63盤子從B移動到C。

而對於1，2，3.....63這63個盤子怎麼樣從A移動到B，再從B移動到C，我們在解決63個盤子的情況的時候，已經處理過了。

關於遞歸，上面有幾位講得也比較好，我也就不贅述了。

關於另一個問題，為什麼平時的項目中，很少見到遞歸。這個是因為，一個正經的程序，是應當盡量少或者儘可能不出現遞歸的程序。在程序中使用遞歸，除了能夠少寫幾行代碼，給程序員帶來一點點方便以外，沒有別的太多的好處，甚至有時候是有害的。

首先，你應當明確一點，所有的遞歸程序，都可以改寫成非遞歸的方法，而在這個非遞歸的方法中，你不得不維護一個棧，來完成原來程序調用棧的能夠，從而使得程序能達到跟遞歸一樣的效果。為什麼說遞歸是不好的呢，那是因為調用棧的大小是有限的，而遞歸的深度，有的時候是不好估計的。一旦遞歸的深度過大，使得調用棧溢出了，那麼對程序的影響是非常大的。而在非遞歸的方法中，由於棧由自己維護，即使「遞歸」的深度過大，程序也在你的控制範圍之內，可以自己中斷「遞歸」過程並作相應的處理。

然後，遞歸使得程序書寫的效率提高，但並不意味著執行的效率會提高，比如那個斐波那契數列的例子，你自己算一下就會發現有將近一般的計算式重複的，比如那個fibo(n-2)是會計算兩次的，而越深的項重複次數就會越多。除了這個問題外，遞歸程序的執行效率一般也不必循環高，因為在棧上開闢新空間、分配局部變數的時間也是不小的。你可以自己嘗試的寫一下這樣的程序，和@陳甫鵃同學的那個程序一樣，還是那個斐波那契數列的例子，也還是python，非遞歸的解法。數字不用很大，求斐波那契數列的第50項，遞歸的方法就已經很難在你能容忍的時間內完成了。

def fibo( n ):
if n &<= 0:
raise Exception()
elif n == 1:
return 0
elif n == 2:
return 1
else:

a = 0
b = 1
s = 0
while n &> 2:
s = b + a
a = b
b = s
n -= 1
return s

最後，關於遞歸的建議，一定要會遞歸的解決問題，但是要避免寫遞歸的程序。

首先是思想方法上要轉變，不要試圖解決問題(這是常規的思考方式)，而應該「鼠目寸光」地只想解決一點點，要點是，解決一點點之後，剩下來的問題還是原來的問題，但規模要比原問題小了

思想和語言是密切相關的，所以問題的提法也很重要。一個問題這樣提可能感覺很難寫出遞歸，換種提法，可能就寫出來了。

平時就要注意用遞歸的方式思考，譬如什麼是鏈表？以遞歸來看就是一個指針，指向一個含有鏈表的指針。一旦你用這種方式看待鏈表，你會發現寫鏈表的代碼非常容易。反之，則非常容易拖泥帶水

從代碼層面看，遞歸就是函數的循環，所以只要透徹理解函數，寫遞歸代碼沒什麼難的。

從編碼形式上來說，遞歸函數，是相當于歸納了一個問題，和它相鄰的問題的解之間的關係。

從調用過程上來說，遞歸函數，包含遞推和回歸過程。

遞推，就是在棧上的堆疊和調用深度的增加，

回歸，就是棧指針向原來位置移動，調用深度的降低，對應著代碼中在某種情況下的 return。

對於彙編層面而言，遞歸函數就是在函數體中，call 了自己的入口地址。和非遞歸函數相比沒有什麼特殊的。

推薦幾本書：《The little Schemer》，《計算機程序的構造和解釋》（SICP），《哥德爾，埃舍爾，巴赫》（GEB）。

讀《SICP》計算機程序的構造和解釋 (豆瓣)

這本書裡面各種遞歸，沒有for/while，而且解釋的非常詳細，值得學習。

從理解漢諾塔開始，這是在線顯示

http://www.neu.edu.cn/cxsj/case/case11.html

一本小書就可以了。《The Little Schemer》。無需任何基礎，如果讀完你沒有滿頭星星，那就恭喜你啦，遞歸出師，這個問題解決了。

http://www.ccs.neu.edu/home/matthias/BTLS/

簡單，遞歸就是將可復用的代碼邏輯抽象為循環調用的方法，每次傳遞狀態信息作為參數。合理的設計參數是重點。

凡是用數學歸納法可以解決的問題，都可以寫成遞歸

其實遞歸和循環是等價的，你可以用循環解決的問題，都可以用遞歸來解決。也就是說，你可以嘗試著觀察自己所寫過的使用了循環結構的代碼，然後試圖對它們進行一個``定義上""的歸納，比如一個數的階乘的計算方法是n*(n-1)*...*2*1，它的定義可以想成是n*(n-1)!，這樣，你就把一個循環變成了一個遞歸了。只要練習多了，你就會自然而然地用遞歸的方式來想問題了。關鍵一點就是：

_循環_要求你思考一件事情_怎麼做_，而_遞歸_要求你思考一件事情_怎麼定義_。這是我的理解～

每次函數調用都是跳到函數入口，每次跳進去都會有一套新的空間和環境。

實在不明白的話，假設fun是一個遞歸函數，裡邊有n次遞歸，你就複製fun1，fun2… …funn，複製跟fun一模一樣的代碼，然後你依次替換那n次遞歸就行了。

我怎麼覺得還得附帶的加進去理解好棧以及後入先出的概念。。。。

盜夢空間

學會拆解問題，把大問題拆解成小問題，小問題拆解成能解決的問題。

寫一個對象和map互轉就會了。