遞歸算法的認識

目錄摘要……………………引言……………………3、正文……………………3.1遞歸算法的特點…………………3.2遞歸算法的要求……………………3.3遞歸算法的過程……………………3.4實例分析……………3.41問題的提出……………………3.42問題的分析……………………3.43遞歸過程………總結…………………參考文獻……………關于遞歸算法的認識【摘要】：遞歸思想是計算機科學的一個重要思想,遞歸方法是程序設計中的有效方法,它為程序設計者打開了一個全新的程序設計思路。采用遞歸思想編程,可以將一些貌似復雜的問題簡單化,編寫的程序更加簡潔明了?！娟P鍵詞】遞歸算法遞推遞歸出口引言：遞歸算法都是通過自己調用自己，將求解問題轉化成性質相同的子問題，最終達到求解的目的。在計算機程序設計中,遞歸算法對解決有些問題是十分有效的,它往往使算法的描述簡潔而且易于理解,當使用非遞歸方法難于解決問題時,嘗試用遞歸方法也許會給你帶來意想不到的驚喜。著名的漢諾塔(Hanoi)問題,八皇后問題就是通過遞歸算法的思想來求解的。正文：遞歸算法是一種直接或者間接地調用自身算法的過程。在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。遞歸調用是一種特殊的嵌套調用，是某個函數(shù)調用自己，而不是另外一個函數(shù)。遞歸調用一種解決方案，一種是邏輯思想，將一個大工作分為逐漸減小的小工作，比如說一個和尚要搬50塊石頭，他想，只要先搬走49塊，那剩下的一塊就能搬完了，然后考慮那49塊，只要先搬走48塊，那剩下的一塊就能搬完了……，遞歸是一種思想，只不過在程序中，就是依靠函數(shù)嵌套這個特性來實現(xiàn)了。遞歸算法的特點遞歸算法是一種直接或者間接地調用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。遞歸算法解決問題的特點；遞歸就是在過程或函數(shù)里調用自身。在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。（3）遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。一般不提倡用遞歸算法設計程序。(4)在遞歸調用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。遞歸算法要求遞歸算法所體現(xiàn)的“重復”一般有三個要求：一是每次調用在規(guī)模上都有所縮小(通常是減半)；二是相鄰兩次重復之間有緊密的聯(lián)系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規(guī)模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環(huán)而不能正常結束。遞歸過程遞歸過程是直接調用自己或通過一系列的過程調用語句直接調用自己的過程。在一個過程的運行期間調用另一個過程時，在執(zhí)行被調用過程之前，系統(tǒng)要先把所有的實在參數(shù)返回地址等信息傳遞給被調用的過程保存，為被調用過程的局部變量分配存儲空間，將控制轉移到被調用入口。然后從被調用過程返回調用過程要保存被調用過程的計算結果，釋放被調用過程的數(shù)據區(qū)，依照被調用保存的返回地址將控制轉移到調用過程，該過程服從后調用先返回的原則。下面我們通過棋子移動問題來理解下遞歸算法：問題的提出：棋子移動問題：有2n個棋子（n>=4)排成一行，白子用0代表，黑子用1代表，n=5的初始狀態(tài)為00000111111--（右邊至少有兩個空位）移動的規(guī)則是：每次必須同時移動相鄰兩個棋子，顏色不限，移動方向不限；每次移動必須跳過若干個棋子。要求最后成為0101010101問題分析：n=400001111--第一步000--11101（4,5）->(9,10）第二步0001011--1（8,9）->(4,5）第三步0--1011001（2,3）->(8,9）第四步010101--01（7,8）->(2,3）第五步--01010101（1,2）->(7,8）n=50000011111--第一步0000--111101（5,6）->(11,12）第二步00001111--01（9,10）->(5,6）這是前8枚棋子為n=4的情況，移法如n=4的棋子移動過程。n=6000000111111--第一步00000--1111101（6,7）->(13,14）第二步0000011111--01（11,12）->(6,7）這是前10枚棋子為n=5的情況，移法如n=5的棋子移動過程。n=4是遞歸的出口，在退出時做5個移動操作：move（4,5）->(9,10）move（8,9）->(4,5）move（2,3）->(8,9）move（7,8）->(2,3）move（1,2）->(7,8）如果2n個棋子的移動用chess（n）表示，則遞歸關系是move（n，n+1）->(2n+1,2n+2）；move（2n-1,2n）->(n，n+1）；callchess（n—1）；遞歸過程如下：procedurechess(n);beginIfn=4thenbeginmove（4,5）->(9,10）move（8,9）->(4,5）move（2,3）->(8,9）move（7,8）->(2,3）move（1,2）->(7,8）endelsebeginmove（n，n+1）->(2n+1,2n+2）；move（2n-1,2n）->(n，n+1）；callchess（n—1）；end;endp;在求解上面棋子移動的問題中，首先我們是先從n=4開始的，然后n=5，我們發(fā)現(xiàn)在求解n=5的時候，可以會用到n=4的過程。在求解2n個棋子移動的問題，我們發(fā)現(xiàn)，2n個棋子移動的問題可以轉化成2n-1個棋子移動過程的函數(shù)。以此類推就可以簡化成8個棋子移動的過程。以此8個棋子的移動過程就是該問題的遞歸出口?？偨Y：在求解規(guī)模為N的問題，我們要設法將它分解為規(guī)模較小的子問題，然后從這些子問題的解構造整個問題的解，并且這些子問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的子問題，并從這些更小的子問題的解構造出較大規(guī)模問題的解。在求解遞歸問題的時候，我們最主要的就是找到遞歸關系式和遞歸的出口，這樣我們就可以把遞歸算法很好的應用。遞歸算法結構清晰，并且易于理解。對于一個復雜的問題，把原問題分解為若干個相對簡單類同的子問題，繼續(xù)下去直到子問題簡單到能夠直接求解，也就是說到了遞推的出口，這樣原問題就可以由遞推得解。在做遞歸算法的時候，一定要把握住