第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。…………

第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)分支就是一個重復的遞歸過程。簡而言之，優化遞歸就是避免重復子遞歸。優化遞歸就是在每次遞歸開始前，首先到某個對象中，通常為散列表對象，也可以是數組，查找本次遞歸是否已經被實施完畢，即是否已經有了遞歸結果，如果散列表對象中已經有了本次遞歸的結果，就直接使用這個結果，不再浪