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

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

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

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

結(jié)束

結(jié)束

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

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

第1次彈棧第m次彈棧第k次彈棧第1次壓棧第m次壓棧第k次壓棧2025/6/1153.1遞歸算法時間復雜度函數(shù)調(diào)用結(jié)束，會進行彈棧，稱為彈棧操作，同時釋放函數(shù)的局部變量所占的內(nèi)存。要針對具體的遞歸函數(shù)，來計算該遞歸函數(shù)的時間復雜度。遞歸函數(shù)是一個遞歸過程，從遞歸開始到遞歸結(jié)束，函數(shù)被調(diào)的總數(shù)R(n)是依賴于一個正整數(shù)n的函數(shù)。那么遞歸函數(shù)中基本操作被執(zhí)行的總數(shù)T(n)就依賴遞歸的總數(shù)R(n)和每次遞歸時基本操作被執(zhí)行的總數(shù)。2025/6/1163.1遞歸算法空間復雜度函數(shù)調(diào)用結(jié)束，會進行彈棧，稱為彈棧操作，同時釋放函數(shù)的局部變量所占的內(nèi)存。遞歸會讓棧的長度不斷發(fā)生變化，如果棧的長度較大可能導致棧溢出，使得進程（運行的程序）被操作系統(tǒng)終止。遞歸過程的壓棧操作增加棧的長度、彈棧操作減小棧的長度。遞歸過程中可能交替地進行壓棧操作和彈棧操作，直至棧的長度為0（見例子2）。計算出遞歸過程中，某一時刻（某一次遞歸）棧出現(xiàn)的最大長度和每次遞歸中函數(shù)的局部變量所占的內(nèi)存空間，即計算出棧最大長度以及局部變量所占的全部內(nèi)存空間和所依賴的正整數(shù)的關(guān)系，才可以知道空間復雜度。2025/6/1173.2線性遞歸與非線性遞歸●線性遞歸線性遞歸是指，每次遞歸時，函數(shù)調(diào)用自身一次。如果我們忘記了今天是星期幾，就需要知道昨天是星期幾，如此這般地向前（過去）翻日歷（相當于遞歸里的壓棧，導致棧的長度在增加），等到能翻到某個日歷頁上顯示了星期幾，就結(jié)束翻閱日歷（相當于結(jié)束壓棧），然后再一頁一頁的撕掉日歷（相當于彈棧），日歷上神奇地出現(xiàn)了星期數(shù)，即函數(shù)依次計算出自己的返回值。ALG3_1.py

ch3_1.py

ch3_1.py中，假設(shè)元旦是星期一，輸出這一年的第168天是星期日.2025/6/1183.2線性遞歸與非線性遞歸●線性遞歸遞歸函數(shù)f(n)的遞歸的總次數(shù)：R(n)=n，而每次遞歸的基本操作只有2個基本操作，因此時間復雜度是O(n)。向下方向的弧箭頭表示函數(shù)被調(diào)用，向上方向的直箭頭表示函數(shù)調(diào)用結(jié)束。例子1壓棧操作過程中得到的棧的最大長度是R(n)=n，空間復雜度是O(n)。2025/6/1193.2線性遞歸與非線性遞歸●非線性遞非線性遞歸是指，每次遞歸時函數(shù)調(diào)用自身2次或2次以上。ALG3_2.py例子2遞歸與Fibonacci序列ch3_2.py

Fibonacci數(shù)列的特點是，前2項的值都是1，從第3項開始，每項的值是前兩項值的和。Fibonacci序列如下：1,1,2,3,5,8,13,21,…2025/6/11103.2線性遞歸與非線性遞歸●非線性遞例子2遞歸過程中，每次遞歸時函數(shù)調(diào)用自身2次，使得每次遞歸出現(xiàn)了2個遞歸“分支”，然后選擇一個分支，繼續(xù)遞歸，直到該分支遞歸結(jié)束，再沿著下一分支繼續(xù)遞歸，當2個分支都遞歸結(jié)束，遞歸過程才結(jié)束，而且遞歸過程交替地進行壓棧和彈棧操作，直至棧的長度為0。

2025/6/11113.3問題與子問題將規(guī)模大的問題，使用遞歸算法逐步分解成規(guī)模小的問題，最終解決規(guī)模大的問題。一個問題的子問題就是數(shù)據(jù)規(guī)模比此問題的規(guī)模更小的問題。當一個問題，可以分解成許多子問題時就可以考慮用遞歸算法來解決這個問題。2025/6/11123.3問題與子問題

ALG3_3.py

ch3_3.py2025/6/11133.3問題與子問題

ALG3_4.py例子4反轉(zhuǎn)（倒置）字符序列ch3_4.py

2025/6/11143.4遞歸與迭代遞歸的思想是根據(jù)上一次操作的結(jié)果，確定當前操作的結(jié)果。迭代的思想是，根據(jù)當前操作的結(jié)果，確定下一次操作的結(jié)果。對于解決相同的問題，遞歸代碼簡練，容易理解解決問題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，具有很好的可讀性。由于迭代不涉及方法的遞歸調(diào)用，所以，通常情況下遞歸算法的空間復雜度會大于迭代的復雜度，當遞歸過程的遞歸總數(shù)比較大時，會導致棧溢出。2025/6/11153.4遞歸與迭代

computePI.py例子5計算圓周率的近似值ch3_5.py

2025/6/11163.4遞歸與迭代ALG3_6.py例子6判斷某個數(shù)是否是有序數(shù)組的元素值ch3_6.py

2025/6/11173.4遞歸與迭代ALG3_7.py例子7求兩個正整數(shù)的最大公約數(shù)ch3_7.py

2025/6/11183.5多重遞歸所謂多重遞歸，是指一個遞歸方法調(diào)用另一個或多個遞歸方法，稱該遞歸方法多重遞歸方法。

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

2025/6/11193.5多重遞歸

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

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

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

2025/6/11233.6經(jīng)典遞歸ALG3_9.py例子9輸出楊輝三角形ch3_9.py楊輝三角

2025/6/11243.6經(jīng)典遞歸老鼠走迷宮

老鼠首先向東走，如果走到出口結(jié)束遞歸，否則向南…向西…向北。

2025/6/11253.6經(jīng)典遞歸老鼠走迷宮ALG3_10.py中的move(a,rows,cols,i,j)是老鼠走迷宮的函數(shù)，該函數(shù)是一個遞歸函數(shù)。ALG3_10.py例子10模擬老鼠走迷宮ch3_10.py老鼠走過迷宮后，輸出老鼠走過的路時，用m表示老鼠走過的路，Y表示老鼠到達的出口。

2025/6/11263.6經(jīng)典遞歸漢諾塔（遞歸算法）漢諾塔(HanoiTower)問題是來源于印度的一個古老問題。有名字為A，B，C的三個塔，A塔上有從小到大64個盤子，每次搬運一個盤子，最后要把64個盤子搬運到C塔。在搬運盤子的過程中，可以把盤子暫時放在3個塔中的任何一個上，但不允許大盤放在小盤上面。3個盤子的漢諾塔

2025/6/11273.6經(jīng)典遞歸漢諾塔（遞歸算法）3個盤子的漢諾塔

ALG3_11.py例子11漢諾塔的遞歸算法ch3_11.py2025/6/11283.6經(jīng)典遞歸漢諾塔（迭代算法）

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

一個偶數(shù)通過不斷地右位移可計算出尾部連續(xù)的0的個數(shù)，例如：8的二進制1000右位移3次，得到奇數(shù)，因此知道8的二進制尾部連續(xù)0的個數(shù)是3。這些規(guī)律是通過研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2025/6/11303.6經(jīng)典遞歸漢諾塔（迭代算法）這些規(guī)律是通過研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。更具①至⑤的規(guī)律給出的迭代算法，盡管時間復雜度和例子11中的遞歸算法相同，空間復雜度低于遞歸算法，但簡練性和可讀性遠遠不如遞歸算法。在內(nèi)存允許的范圍內(nèi)，還是遞歸算法更好。ALG3_12.py例子12漢諾塔的迭代算法ch3_12.py

2025/6/1131計算Fibonacci序列的遞歸過程中需要將f(n-1)分支進行完畢，再進行f(n-2)分支。需要注意到的是，在進行f(n-1)分支遞歸時，會完成了f(n-2)分支遞歸，那么再進行f(n-2)分支就是一個重復的遞歸過程。簡而言之，優(yōu)化遞歸就是避免重復子遞歸。優(yōu)化遞歸就是在每次遞歸開始前，首先到某個對象中，通常為散列表對象，也可以是數(shù)組，查找本次遞歸是否已經(jīng)被實施完畢，即是否已經(jīng)有了遞歸結(jié)果，如果散列表對象中已經(jīng)有了本次遞歸的結(jié)果，就直接使用這個結(jié)果，不再浪