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

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

……調用調用調用調用調用結束

結束

結束

結束結束

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

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

ch3_1.py

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

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

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

ALG3_3.py

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

ALG3_4.py例子4反轉（倒置）字符序列ch3_4.py

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

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

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

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

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

不要求輸出含有偶數多個6的數。

2025/6/11193.5多重遞歸

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

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

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

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

2025/6/11243.6經典遞歸老鼠走迷宮

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

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

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

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

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

這些規律是通過研究漢諾塔的遞歸算法發現的。就像本章一開始說的，遞歸可以發現數據的內部的邏輯規律。2025/6/11293.6經典遞歸漢諾塔（迭代算法）

一個偶數通過不斷地右位移可計算出尾部連續的0的個數，例如：8的二進制1000右位移3次，得到奇數，因此知道8的二進制尾部連續0的個數是3。這些規律是通過研究漢諾塔的遞歸算法發現的。就像本章一開始說的，遞歸可以發現數據的內部的邏輯規律。2025/6/11303.6經典遞歸漢諾塔（迭代算法）這些規律是通過研究漢諾塔的遞歸算法發現的。就像本章一開始說的，遞歸可以發現數據的內部的邏輯規律。更具①至⑤的規律給出的迭代算法，盡管時間復雜度和例子11中的遞歸算法相同，空間復雜度低于遞歸算法，但簡練性和可讀性遠遠不如遞歸算法。在內存允許的范圍內，還是遞歸算法更好。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)分支就是一個重復的遞歸過程。簡而言之，優化遞歸就是避免重復子遞歸。優化遞歸就是在每次遞歸開始前，首先到某個對象中，通常為散列表對象，也可以是數組，查找本次遞歸是否已經被實施完畢，即是否已經有了遞歸結果，如果散列表對象中已經有了本次遞歸的結果，就直接使用這個結果，不再浪費時間進行本次遞歸，否則就進行本次遞歸，并將遞歸結果保存到散列表對象。3.7優化遞歸2025/6/11323.7優化遞歸ALG3_13.py例子13優化Fibonacci數列的遞歸算法ch3_13.py

2025/6/11333.7優化遞歸ALG3_14.py例子14優化楊輝三角形的遞歸算法ch3_14.py

也可以使用函數緩存技術來優化遞歸，但函數緩存對函數的參數類型有較嚴格的限制，細節見第12章的12.8節。第4章數組2025/6/1134

數組是Python中非常基礎的一種順序存儲的數據結構，也被稱為順序表，首先介紹順序表，然后介紹數組。順序表的特點；

array類；數組與圍圈留一問題；數組與參數存值；數組與穩定排序；二分法與數組；數組的相等；數組與洗牌。4.1順序表的特點2025/6/1135順序表也是線性表的一種具體體現，順序表節點形成的邏輯結構是線性結構、節點的存儲結構是順序存儲，即節點的物理地址是依次相鄰的。注意：由于順序表使用數組實現順序存儲，因此也稱順序表的節點為元素。2025/6/11364.1順序表的特點順序表使用數組來實現，順序表的節點的物理地址是依次相鄰的，因此可以隨機訪問任何一個節點，不必從頭節點計數查找其它節點。1查詢節點

2025/6/11374.1順序表的特點

3刪除節點

4.2array類2025/6/1138Python的array模塊（數組模塊）提供了array類，該array類可為用戶程序實現動態數組（屬于順序表結構）。array模塊的array類同時也提供了操作數組的方法，例如添加元素、插入元素、刪除元素等方法（Python中把獨立的算法稱作函數，把和類有關的算法稱作方法）。2025/6/11394.2array類1.創建數組注意：無法動態指定數組的大小，即元素的個數。

使用array模塊的array類的構造函數array(typecode,initalize)創建數組時需要指定數組的元素的類型和初始元素，即指定typecode的具體類型和initalize的具體值。

2025/6/11404.2array類2.數組的使用3.數組的長度數組通過索引來訪問元素，索引從0開始，例如：

使用Python提供的內置len()函數來獲取數組的長度。例如：2025/6/11414.2array類4.數組的引用array數組屬于引用型變量。如果兩個array數組具有相同的引用，他們就有完全相同的元素。2025/6/11424.2array類5.數組的復制可以用已有的數組arr得到一個新的數組arr_new，新數組arr_new和arr的元素值相同，但二者是兩個不同的數組。2025/6/11434.2array類6.array類的常用方法（1）append(value)：在數組末尾添加一個新元素2025/6/11444.2array類6.array類的常用方法（2）extend(iterable)：在數組末尾添加一個可迭代對象中的所有元素（3）insert(index,value)：在指定索引位置插入一個值為value的新元素2025/6/11454.2array類6.array類的常用方法（4）remove(value)：移除數組中的第一個匹配指定值value的元素（5）pop(index)：移除指定元素并返回該元素的值，如果不指定index的值，即pop()移除尾元素并返回尾元素的值。2025/6/11464.2array類6.array類的常用方法index(value)：從索引開始0開始至數組最后一個索引查找第一個匹配指定值value的元素的索引（如果沒有找到返回-1）；index(value,start)從索引start開始至數組最后一個索引查找第一個匹配指定值value的元素的索引（如果沒有找到返回-1）。2025/6/11474.2array類6.array類的常用方法（7）count(value)：返回數組中指定值value出現的次數。（8）reverse()：將數組的元素值反轉。（9）tolist()：返回和數組有相同元素值的列表。2025/6/11484.2array類7.array數組的類型array模塊中的數組類型可以是基本的類型，即類型可以是以下幾種：'b'：有符號字節(signedchar)'B'：無符號字節(unsignedchar)'u'：Unicode字符(Py_UNICODE)'h'：有符號短整數(signedshort)'H'：無符號短整數(unsignedshort)'i'：有符號整數(signedint)'I'：無符號整數(unsignedint)'l'：有符號長整數(signedlong)'L'：無符號長整數(unsignedlong)'f'：單精度浮點數(float)'d'：雙精度浮點數(double)array模塊中的數組類型不支持對象，即不能在array數組中直接存儲Python對象，如字符串、列表、字典等。4.3數組與圍圈留一問題

圍圈留一是一個古老的問題（也稱約瑟夫問題）：若干個人圍成一圈，從某個人開始順時針（或逆時針）數到第3個人，該人從圈中退出，然后繼續順時針（或逆時針）數到第3個人，該人從圈中退出，以此類推，程序輸出圈中最后剩下的一個人。2025/6/11492025/6/11504.3數組與圍圈留一問題例子1圍圈留一問題可以簡化為向左旋轉數組（向右），旋轉數組兩次即可確定出退出圈中的人，即此時數組首元素（末尾元素）中的號碼就應該是要退出圈中的人。ch4_1.py

4.4數組與參數存值如果兩個數組的引用相同，那么這兩個數組的元素就完全相同，因此一個函數可以將某些數據存放在數組參數中，那么函數執行完畢，保存在數組元素中的值一直還存在、不會消失。2025/6/11512025/6/11524.4數組與參數存值例子2數組存放三角形面積ch4_2.pyALG4_2.pyALG4_2.py中的函數judge_triangle(a,b,c,area)，當a，b，c構成等邊三角形時返回3，將三角形面積存放在數組area的元素中；當構成等腰（不是等邊）三角形時返回2，將三角形面積存放在數組area的元素中；當構成普通（不是等邊，也不是等腰）三角形時返回1，將三角形面積存放在數組area的元素中；當不構成三角形時返回0，將nan（notanumber）存放在數組area的元素中.2025/6/11534.4數組與參數存值例子2出現次數最多的字母ch4_3.pyALG4_3.pyALG4_3.py中的find_max_count_letters(english,saveCount)函數返回english中出現次數最多的字母之一，并將這個字母出現的次數和他在english中的索引存放到參數指定的saveCount數組的元素中。4.5數組與穩定排序2025/6/1154

2025/6/11554.5數組與穩定排序1.sorted(arr)函數sorted(arr)函數不會修改原始數組arr，而是創建一個新的數組來保存排序結果,并返回新數組的引用。向sorted(arr,reverse=True或False)傳遞第二個參數的值是reverse=True，讓sorted()函數按降序排序。2025/6/11564.5數組與穩定排序2.比較函數與排序sortd(arr,key=比較函數)：讓數組arr的元素值按著“比較函數”的返回值進行排序。讓整數按個位數字的大小排序2025/6/11574.5數組與穩定排序3.Lambda表達式與排序2025/6/11584.5數組與穩定排序3.Lambda表達式與排序sortd(arr,key=Lambda)：讓數組的元素值按著Lambd