數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第3章 遞歸算法

第3章遞歸算法2024/11/91主要內(nèi)容● 遞歸算法● 遞歸的復(fù)雜度● 問(wèn)題與子問(wèn)題● 遞歸與迭代● 多重遞歸● 經(jīng)典遞歸● 優(yōu)化遞歸遞歸算法是非常最重的算法，是很多算法的基礎(chǔ)算法。遞歸算法不僅能使得代碼優(yōu)美簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。和排序算法不同，許多經(jīng)典的排序算法已經(jīng)是玲瓏剔透、日臻完善，在許多應(yīng)用中只要選擇一種排序算法直接使用即可（見(jiàn)第4章和第12章），而對(duì)于遞歸算法，真正理解遞歸算法內(nèi)部運(yùn)作機(jī)制的細(xì)節(jié)、才能真對(duì)實(shí)際問(wèn)題正確的使用遞歸算法或?qū)懗稣_的遞歸算法。3.1遞歸算法遞歸算法是指一個(gè)方法在執(zhí)行過(guò)程中又調(diào)用了自身、形成了遞歸調(diào)用，這樣的方法被稱(chēng)為遞歸方法或遞歸算法。2024/11/92

2024/11/933.1遞歸算法遞歸過(guò)程中的壓棧、彈棧方法f遞歸過(guò)程是，第k次調(diào)用f需要等待第k+1次調(diào)用f結(jié)束執(zhí)行過(guò)程后才能結(jié)束執(zhí)行過(guò)程。那么第R(n)次（最后一次）調(diào)用f結(jié)束執(zhí)行過(guò)程后，就會(huì)依次使得第k次調(diào)用結(jié)束執(zhí)行過(guò)程。方法被調(diào)用時(shí)，方法的（入口）地址會(huì)被壓入棧（棧是一種先進(jìn)后出的結(jié)構(gòu)）中，稱(chēng)為壓棧操作，同時(shí)方法的局部變量被分配內(nèi)存空間。

……調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用結(jié)束

結(jié)束

結(jié)束

結(jié)束結(jié)束

圖3.1遞歸執(zhí)行過(guò)程第1次調(diào)用第R(n)次調(diào)用2024/11/943.1遞歸算法遞歸過(guò)程中的壓棧、彈棧方法調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱(chēng)為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。遞歸過(guò)程的壓棧操作可以讓棧的長(zhǎng)度不斷增加，而彈棧操作會(huì)讓棧的長(zhǎng)度變小，最終使棧的長(zhǎng)度為0?！?/p>

第1次彈棧第m次彈棧第k次彈棧第1次壓棧第m次壓棧第k次壓棧2024/11/953.1遞歸算法時(shí)間復(fù)雜度方法調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱(chēng)為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。要針對(duì)具體的遞歸方法，來(lái)計(jì)算該遞歸方法的時(shí)間復(fù)雜度。遞歸方法是一個(gè)遞歸過(guò)程，從遞歸開(kāi)始到遞歸結(jié)束，方法被調(diào)的總數(shù)R(n)是依賴(lài)于一個(gè)正整數(shù)n的函數(shù)。那么遞歸方法中基本操作被執(zhí)行的總數(shù)T(n)就依賴(lài)遞歸的總數(shù)R(n)和每次遞歸時(shí)基本操作被執(zhí)行的總數(shù)。2024/11/963.1遞歸算法空間復(fù)雜度方法調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱(chēng)為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。遞歸會(huì)讓棧的長(zhǎng)度不斷發(fā)生變化，如果棧的長(zhǎng)度較大可能導(dǎo)致棧溢出，使得進(jìn)程（運(yùn)行的程序）被操作系統(tǒng)終止。遞歸過(guò)程的壓棧操作增加棧的長(zhǎng)度、彈棧操作減小棧的長(zhǎng)度。遞歸過(guò)程中可能交替地進(jìn)行壓棧操作和彈棧操作，直至棧的長(zhǎng)度為0（見(jiàn)例子2）。計(jì)算出遞歸過(guò)程中，某一時(shí)刻（某一次遞歸）棧出現(xiàn)的最大長(zhǎng)度和每次遞歸中方法的局部變量所占的內(nèi)存空間，即計(jì)算出棧最大長(zhǎng)度以及局部變量所占的全部?jī)?nèi)存空間和所依賴(lài)的正整數(shù)的關(guān)系，才可以知道空間復(fù)雜度。2024/11/973.2線性遞歸與非線性遞歸●線性遞歸線性遞歸是指，每次遞歸時(shí)，方法調(diào)用自身一次。

如果我們忘記了今天是星期幾，就需要知道昨天是星期幾，如此這般地向前（過(guò)去）翻日歷（相當(dāng)于遞歸里的壓棧，導(dǎo)致棧的長(zhǎng)度在增加），等到能翻到某個(gè)日歷頁(yè)上顯示了星期幾，就結(jié)束翻閱日歷（相當(dāng)于結(jié)束壓棧），然后再一頁(yè)一頁(yè)的撕掉日歷（相當(dāng)于彈棧），日歷上神奇地出現(xiàn)了星期數(shù)，即方法依次計(jì)算出自己的返回值。Week.java例子1Example3_1.java2024/11/983.2線性遞歸與非線性遞歸●線性遞歸遞歸方法f(intn)的遞歸的總次數(shù)：R(n)=n，而每次遞歸的基本操作只有2個(gè)基本操作，因此時(shí)間復(fù)雜度是O(n)。向下方向的弧箭頭表示方法被調(diào)用，向上方向的直箭頭表示方法調(diào)用結(jié)束。例子1壓棧操作過(guò)程中得到的棧的最大長(zhǎng)度是R(n)=n，空間復(fù)雜度是O(n)。2024/11/993.2線性遞歸與非線性遞歸●非線性遞非線性遞歸是指，每次遞歸時(shí)方法，調(diào)用自身2次或2次以上。

Fibonacci.java例子2Example3_2.java2024/11/9103.2線性遞歸與非線性遞歸●非線性遞例子2遞歸過(guò)程中，每次遞歸時(shí)方法調(diào)用自身2次，使得每次遞歸出現(xiàn)了2個(gè)遞歸“分支”，然后選擇一個(gè)分支，繼續(xù)遞歸，直到該分支遞歸結(jié)束，再沿著下一分支繼續(xù)遞歸，當(dāng)2個(gè)分支都遞歸結(jié)束，遞歸過(guò)程才結(jié)束，而且遞歸過(guò)程交替地進(jìn)行壓棧和彈棧操作，直至棧的長(zhǎng)度為0。

2024/11/9113.3問(wèn)題與子問(wèn)題將規(guī)模大的問(wèn)題，使用遞歸算法逐步分解成規(guī)模小的問(wèn)題，最終解決規(guī)模大的問(wèn)題。一個(gè)問(wèn)題的子問(wèn)題就是數(shù)據(jù)規(guī)模比此問(wèn)題的規(guī)模更小的問(wèn)題。當(dāng)一個(gè)問(wèn)題，可以分解成許多子問(wèn)題時(shí)就可以考慮用遞歸算法來(lái)解決這個(gè)問(wèn)題。2024/11/9123.3問(wèn)題與子問(wèn)題

SumMulti.java例子3Example3_3.java2024/11/9133.3問(wèn)題與子問(wèn)題

Reverse.java例子4Example3_4.javaMaxInArray.java2024/11/9143.4遞歸與迭代遞歸的思想是根據(jù)上一次操作的結(jié)果，確定當(dāng)前操作的結(jié)果。迭代的思想是，根據(jù)當(dāng)前操作的結(jié)果，確定下一次操作的結(jié)果。對(duì)于解決相同的問(wèn)題，遞歸代碼簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，具有很好的可讀性。由于迭代不涉及方法的遞歸調(diào)用，所以，通常情況下遞歸算法的空間復(fù)雜度會(huì)大于迭代的復(fù)雜度，當(dāng)遞歸過(guò)程的遞歸總數(shù)比較大時(shí)，會(huì)導(dǎo)致棧溢出。2024/11/9153.4遞歸與迭代例子5中ComputePI類(lèi)中的recursionMethod(intn)方法和iterationMethod(intn)都是通過(guò)計(jì)算級(jí)數(shù)的近似值返回圓周率的近似值，recursionMethod(intn)使用的是遞歸，iterationMethod(intn)使用的是迭代。ComputePI.java例子5Example3_5.java2024/11/9163.4遞歸與迭代

SearchNumber.java例子6Example3_6.java

2024/11/9173.4遞歸與迭代Euclidean.java例子7Example3_7.java

2024/11/9183.5多重遞歸所謂多重遞歸，是指一個(gè)遞歸方法調(diào)用另一個(gè)或多個(gè)遞歸方法，稱(chēng)該遞歸方法多重遞歸方法。

不要求輸出含有偶數(shù)多個(gè)6的數(shù)。

2024/11/9193.5多重遞歸

2024/11/9203.6經(jīng)典遞歸選擇三個(gè)經(jīng)典的遞歸：楊輝三角形、老鼠走迷宮和漢諾塔，進(jìn)一步體會(huì)遞歸算法不僅能使得代碼優(yōu)美簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。特別是漢諾塔遞歸，通過(guò)其遞歸算法，洞悉其數(shù)據(jù)規(guī)律，給出相應(yīng)的迭代算法。經(jīng)典的遞歸：楊輝三角形，老鼠走迷宮，漢諾塔2024/11/9213.6經(jīng)典遞歸楊輝三角

最早出現(xiàn)于中國(guó)南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國(guó)數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱(chēng)帕斯卡三角形。

2024/11/9223.6經(jīng)典遞歸楊輝三角最早出現(xiàn)于中國(guó)南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國(guó)數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱(chēng)帕斯卡三角形。

2024/11/9233.6經(jīng)典遞歸PascalTriangle.java例子9Example3_9.java楊輝三角

YanhuiTriangle.java

2024/11/9243.6經(jīng)典遞歸老鼠走迷宮老鼠首先向東走，如果走到出口結(jié)束遞歸，否則向南…向西…向北。

2024/11/9253.6經(jīng)典遞歸老鼠走迷宮例子10的主類(lèi)Example3_10使用move(int[][]a,inti,intj)方法走迷宮。其中，用int型二維數(shù)組模擬迷宮，二維數(shù)組元素值是1表示墻，0表示路，2表示出口。老鼠走過(guò)迷宮后，輸出老鼠走過(guò)的路時(shí)，用☆表示老鼠走過(guò)的路，■表示墻，★表示出口，□表示老鼠未走過(guò)的路。Mouse.java例子10Example3_10.java2024/11/9263.6經(jīng)典遞歸漢諾塔（遞歸算法）漢諾塔(HanoiTower)問(wèn)題是來(lái)源于印度的一個(gè)古老問(wèn)題。有名字為A，B，C的三個(gè)塔，A塔上有從小到大64個(gè)盤(pán)子，每次搬運(yùn)一個(gè)盤(pán)子，最后要把64個(gè)盤(pán)子搬運(yùn)到C塔。在搬運(yùn)盤(pán)子的過(guò)程中，可以把盤(pán)子暫時(shí)放在3個(gè)塔中的任何一個(gè)上，但不允許大盤(pán)放在小盤(pán)上面。3個(gè)盤(pán)子的漢諾塔

2024/11/9273.6經(jīng)典遞歸漢諾塔（遞歸算法）3個(gè)盤(pán)子的漢諾塔

HannoiTower.java例子11Example3_11.java2024/11/9283.6經(jīng)典遞歸漢諾塔（迭代算法）

這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開(kāi)始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2024/11/9293.6經(jīng)典遞歸漢諾塔（迭代算法）

一個(gè)偶數(shù)通過(guò)不斷地右位移可計(jì)算出尾部連續(xù)的0的個(gè)數(shù)，例如：8的二進(jìn)制1000右位移3次，得到奇數(shù)，因此知道8的二進(jìn)制尾部連續(xù)0的個(gè)數(shù)是3。這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開(kāi)始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2024/11/9303.6經(jīng)典遞歸漢諾塔（迭代算法）這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開(kāi)始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。

HanoiTowerIterator.java例子12ZeroCount.javaExample3_12.java2024/11/931計(jì)算Fibonacci序列的遞歸過(guò)程中需要將f(n-1)分支進(jìn)行完畢，再進(jìn)行f(n-2)分支。需要注意到的是，在進(jìn)行f(n-1)分支遞歸時(shí)，會(huì)完成了f(n-2)分支遞歸，那么再進(jìn)行f(n-2)分支就是一個(gè)重復(fù)的遞歸過(guò)程。簡(jiǎn)而言之，優(yōu)化遞歸就是避免重復(fù)子遞歸。優(yōu)化遞歸就是在每次遞歸開(kāi)始前，首先到某個(gè)對(duì)象中，通常為散列表對(duì)象，也可以是數(shù)組，查找本次遞歸是否已經(jīng)被實(shí)施完畢，即是否已經(jīng)有了遞歸結(jié)果，如果散列表對(duì)象中已經(jīng)有了本次遞歸的結(jié)果，就直接使用這個(gè)結(jié)果，不再浪費(fèi)時(shí)間進(jìn)行本次遞歸，否則就進(jìn)行本次遞歸，并將遞歸結(jié)果保存到散列表對(duì)象。3.7優(yōu)化遞歸2024/11/9323.7優(yōu)化遞歸

OptimizeFibona