資源描述：
《深入理解遞歸函數(shù)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、深入理解遞歸函數(shù)剛開始接觸編程對遞歸調(diào)用都是比較頭痛，很多年前我也會一樣。昨天晩上睡覺突然想起了譚浩強C語言的漢諾塔遞歸調(diào)用，記得當吋是在高中的時候，我表姐在上大學(xué)，她把譚浩強的C語言給了我，只看書不實踐，現(xiàn)在想起來效果還真差。其中遞歸調(diào)用漢諾塔看了好久都沒有整明白，直到上大學(xué)學(xué)習(xí)C語言也還沒有搞明白，當學(xué)到遞歸調(diào)用了，我就去問老師，老是說回去看看，下周告訴我。誰知到老師真的很忙，下周也沒有結(jié)果。后來自己什么吋候明白的也忘記了。剛開始接觸遞歸都會告訴你，遞歸占用資源，使程序復(fù)雜，最好不要使用；還有人說，如果這個人一來就是用遞歸，我肯
2、定不會聘用他。但是我認為這些觀點太片面。遞歸算法的目的降低程序的復(fù)雜度，解放大腦負擔，讓大腦更加專注于問題本身。程序的性能跟遞歸沒有什么關(guān)系，更重要的時算法本身，我們會在稍后講解一下同i種算法同樣是遞歸，性能的差異巨大。設(shè)計模式中，很多模式都存在遞歸。剛開始接觸遞歸的，往往都會在里面打圈圈，自己越繞越暈，覺得遞歸太復(fù)雜。其實看待遞歸的時候，也是要分層面看待，不要把自己的大腦當做是電腦，可以繞很多的圈圈，有人說人的大腦同時能處理7個左右的變量，繞一圈就多幾個變量，能繞幾圈啊。呵呵。找到一個算法，在編寫算法的吋候，只考慮一次遞歸所做的事
3、情，如果遇到到遞歸調(diào)用函數(shù)的時候，把他當做一個函數(shù)整體考慮，他能完成他要完成的事情，要相信他，也要相信自己。我們所在的層面就是算法的層面，或者一次執(zhí)行的層面。如果在算法層面和遞歸調(diào)用層面來回穿插的思考，讀懂遞歸算法將非常困難，遞歸的復(fù)雜度就在于壓棧會導(dǎo)致大量的變量需要存儲，對我們的大腦來說負擔太重，但是對汁算機來說是小意思，相對來說算法層面往往很簡單，所以我們一定要站在算法層面考慮問題，而不是遞歸層面。下面來看我如何一步一步實現(xiàn)漢諾塔：(VS2010C#控制臺程序)[csharp]viewplaincopyprint^C1.clas
4、sProgram2?{3?staticvoidMain(string[]args)4.<6.7.8.9.staticvoidMove(intn?chara,charb，charc)10.{11.if(n<1)return;12.if(n==1)13?{14.MoveTo(a，c);15.}16.else17.{18?19.〃以下三句可能存在問題，只是為了快速思考，先寫上，看著代碼找感覺。20?Move(n-a,b,c);21.MoveTo(a^c);22.Move(n-1,a,b,c);23?}24.}25.25.privatest
5、aticvoidMoveTo(chara,charc)26.{27.thrownewNotlmplementedException();28.}29.}憑著感覺直接寫了個Move方法，第一個參數(shù)為盤子的個數(shù)，將所有盤子從a移動到c°第一個判斷，防止錯誤的參數(shù)。第二個判斷，當n等于1時，也就是一個盤子，直接盤子從a移動到c上。如果多余一個，將個盤子從a移到b,再將最下面一個從a移動到c,最后從b上將n-1個盤子移動到c上。[csharp]viewplaincopyprint^Ch?〃這三句肯定有問題的，只是為了快速把人腦里的想法寫出看
6、，看著來找感覺。1.Move(n?1,a,b,c);//這句要實現(xiàn)將A座n?l的盤子移動到B上。2.MoveTo(a,c);//這句實現(xiàn)將A座最下血的一個盤子移動到C上3.Move(n?1,a,b,c);//這句要實現(xiàn)將移動到B座的盤子在移動到C座上，這就OK了。因為Move這個方法就是要把盤子從a移動到c,所以我們在遞歸調(diào)用時僅僅記住這個函數(shù)的這個功能就行了，這是一個函數(shù)的整體功能。我們分別來講解當N>1的3個步驟:第一步，講個盤子從a移動到b。把盤子全部移動到b位置和c的方法是一樣的，也就是算法是一樣的。只是規(guī)模比原來少1。所以
7、我們可以遞歸調(diào)用Move方法來解決將個盤子從a移動到bo這吋b就像相當于原來的c位置了，那么就這樣調(diào)用Move(n-1,a,c,b).第二步，當個盤子從a移動到bZ后，a上就一個盤子，我們就可以直接將盤子移動到c上面。調(diào)用MoveTo(a,c)實現(xiàn)盤子的移動。在這一步，其實就是相當于移動只有一個盤子的情況，我們還可以遞歸調(diào)算法本身Move(1,a,b,c);這樣調(diào)用也是可以的。在執(zhí)行完成后，a位置上是空的，b位置上有個盤子，c位置上有一個最大的盤子。第三步，在第二步之后，我們只需要將b位置上的盤子都移動到c位置就可以了。這個和第一步
8、類似，只是位置變了。b相當于原來的a位置(因為盤子在b上),a位置相當于原來的b位置，因為移動到c,所以c還是相當于與原來的c位置。語句調(diào)用這樣寫Move(n?1,b,a,c);完善MoveTo力法，輸出結(jié)果就好了。如果是圖形移動，在
