遞迴(Python)

以下為此單元簡報。

https://drive.google.com/file/d/1J4vTn-eUJNcYX0hiNp2_wCdDGMvb3Vi0/view?usp=sharing

以下為本單元的教學影片(放置於YouTube上)，以下兩種方式擇一。

(A)以YouTube播放清單方式觀看影片，如下。

https://www.youtube.com/playlist?list=PLOk9WKoJdjHbD6LYSDMQkGLfy0L0_WbtE

(B)以超連結方式觀看個別影片，如下。

Python進階-1-1-遞迴與PyCharm除錯(https://youtu.be/FZmofX_nCJc)

Python進階-1-2-遞迴範例(https://youtu.be/coh0EkJF9Ms)

在撰寫遞迴函式前，先要了解如何自訂函式。

(1)自訂函式

函式用於結構化程式，將相同功能的程式獨立出來，經由函式的呼叫，傳入資料與回傳處理後的結果，程式設計師只要將函式寫好，可以不斷利用此函式做相同動作，可以達成程式碼不重複，要修改此功能，只要更改此函式。

函式的定義、傳回值與呼叫

自訂函式需要包含兩個部分，分別是函式的定義與函式的呼叫。函式的定義是實作函式的功能，輸入參數與回傳處理後的結果；函式的呼叫用於讓自訂函式真正執行。

(1-1)函式的定義與傳回值

以下為函式的定義，函式名稱後接著一對小括號，小括號可以填入要傳入函式的參數，當參數有多個的時候以逗號隔開，函式名稱前面宣告函式回傳的資料型別，函式的範圍為函式名稱後縮行固定長度的空白鍵，當函式需要傳回值使用指令return，表示程式執行的控制權由函式轉換為原呼叫函式，函式的定義與傳回值格式，如下。

函式定義與傳回值的語法

def 函式名稱(參數1, 參數2 , …):

函式的敘述區塊

return 要傳回的變數或值

(1-2)函式的呼叫

程式經由函式呼叫，將資料傳入函式，函式處理後傳回結果給呼叫程式

方法一：無傳回值的呼叫語法，利用函式名稱與參數來呼叫函式。

函式名稱(參數值1,參數值2,…)

方法二：有傳回值的呼叫語法，等號右邊要先做完，利用函式名稱與參數來呼叫函式，最後函式回傳值給變數，變數就紀錄函式呼叫後的回傳值。

變數=函式名稱(參數值1,參數值2,…)

(2)遞迴

遞迴是有趣的程式設計技巧，函式執行過程中呼叫自己，稱作遞迴。而這樣的自己呼叫自己，需要有終止的條件，若沒有終止的條件就會形成無窮遞迴。

(2-1)求解n階乘（n!）

數學上定義n階乘為「n!=n*(n-1)*(n-2)*(n-3)*…*3*2*1」。我們可以分階段看，求解n階乘，可以分解成n乘以(n-1)階乘意即「n!=n*(n-1)!」，求解(n-1)階乘，可以分解成n-1乘以(n-2)階乘意即「(n-1)!=(n-1)*(n-2)!」，求解(n-2)階乘，可以分解成n-2乘以(n-3)階乘意即「(n-2)!=(n-2)*(n-3)!」，依此類推，直到求解3階乘，可以分解成3乘以2階乘意即「3!=3*2!」，求解2階乘，可以分解成2乘以1階乘意即「2!=2*1!」，1!就不用再往下求解直接就是1，這樣一層一層遞迴下去直到求解1!，就終止遞迴，再一層一層往上回推，如下圖。

(2-2)m的n次方

求解m的n次方之值，數學上定義m的n次方為n個m相乘。我們可以分階段看，求解m的n次方，可以分解成m乘以m的n-1次方意即「m^n=m*m^(n-1)」，求解m的n-1次方，可以分解成m乘以m的n-2次方意即「m^(n-1)=m*m^(n-2)，求解m的n-2次方，可以分解成m乘以m的n-3次方意即「m^(n-2)=m*m^(n-3)，依此類推，直到求解m的3次方，可以分解成m乘以m的2次方意即「m^3=m*m^2」，m的2次方，可以分解成m乘以m的1次方意即「m^2=m*m^1」，m^1就不用再往下求解直接就是m，這樣一層一層遞迴下去直到求解m^1，就終止遞迴，再一層一層往上回推，如下圖。

求解F(4)的過程

(1) 求解F(4)先遞迴呼叫求F(3)。

(2) 求解F(3)先遞迴呼叫求F(2)。

(3) 求解F(2)先遞迴呼叫求F(1)。

(4) F(1)值為1，所以回傳F(1)，即回傳1。

(5) 求解F(2)，F(1)已經有解，但需要再遞迴呼叫求F(0)。

(6) F(0)值為1，所以回傳F(0)，即回傳1。

(7) 求解F(2)，F(1)與F(0)已經求得，F(2)=F(1)+F(0)=1+1=2，回傳F(2)，即回傳2。

(8) 求解F(3)，F(2)已經有解，但需要再遞迴呼叫求F(1)。

(9) F(1)值為1，所以回傳F(1)，即回傳1。

(10) 求解F(3)，F(2)與F(1)已經求得，F(3)=F(2)+F(1)=2+1=3，回傳F(3)，即回傳3。

(11) 求解F(4)，F(3)已經有解，但需要再遞迴呼叫求F(2)。

(12) 求解F(2)先遞迴呼叫求F(1)。

(13) F(1)值為1，所以回傳F(1)，即回傳1。

(14) 求解F(2)，F(1)已經有解，但需要再遞迴呼叫求F(0)。

(15) F(0)值為1，所以回傳F(0)，即回傳1。

(16) 求解F(2)，F(1)與F(0)已經求得，F(2)=F(1)+F(0)=1+1=2，回傳F(2)，即回傳2。

求解F(4)，F(3)與F(2)已經求得，F(4)=F(3)+F(2)=3+2=5，如此得到結果。

(2-4) 8queue問題

將西洋棋的8個queen放在8x8的棋盤上，如何擺放讓8個queen彼此互相不衝突，請找出在8x8棋盤上放上8個queen，而彼此相互不衝突的所有解。西洋棋的queen對於同一列、同一行與兩個對角線可以吃掉對方，如下圖，Q表示放置queen在第3列第4行，X表示這些位置不能放其他queen會發生衝突。

輸入說明

本題不需要輸入。

輸出說明

輸出所有可能的解，先輸出目前是第幾個解，接著輸出8個queen在8x8的棋盤上所在位置，每一行一定會有一個queen，請由第1行到第8行順序，依序輸出8個queen所在列的編號，舉例如下，下表中8個queen彼此互相不衝突，以「1 5 8 6 3 7 2 4」表示此8個queen在棋盤由左到右所在的列編號。

輸入範例

無須輸入。

輸出範例

全部共有92個解，輸出後面12個。

81 7 1 3 8 6 4 2 5

82 7 2 4 1 8 5 3 6

83 7 2 6 3 1 4 8 5

84 7 3 1 6 8 5 2 4

85 7 3 8 2 5 1 6 4

86 7 4 2 5 8 1 3 6

87 7 4 2 8 6 1 3 5

88 7 5 3 1 6 8 2 4

89 8 2 4 1 7 5 3 6

90 8 2 5 3 1 7 4 6

91 8 3 1 6 2 5 7 4

92 8 4 1 3 6 2 7 5

解題想法

使用遞迴方式暴力找出所有可能性，需要陣列s儲存8個queen所在的列編號。

(2-5)組合(樂透包牌)

給定n個數字，n個數字都不相同，從n個數字中取出m個數字的所有可能性，輸出的m個數字請按照由小到大輸出，不要重複輸出，保證m小於等於n。

輸入說明

輸入整數n，之後接著輸入n個數字，接著輸入整數m，表示要從n個數字中選取m個。

輸出說明

從n個數字中取出m個數字的所有可能性，輸出的m個數字請按照由小到大輸出，不要重複輸出。。

輸入範例

6

23 41 34 5 17 22

5

輸出範例

5 17 22 23 34

5 17 22 23 41

5 17 22 34 41

5 17 23 34 41

5 22 23 34 41

17 22 23 34 41

解題想法

使用遞迴方式暴力找出所有可能性，需要陣列num儲存輸入的n個數字，陣列step儲存包牌的在陣列num的索引值。遞迴需要兩個參數，一個控制目前選取幾個(currStep)，一個控制目前的起始元素讓選取的元素不重複。

(2-6) 排列

給定n個相異的數字，請列出此n個數字的所有排列可能性。

輸入說明

輸入整數n，之後接著輸入n個數字。

輸出說明

列出n個數字的所有排列可能性。

輸入範例

3

5 4 6

輸出範例

4 5 6

4 6 5

5 4 6

5 6 4

6 4 5

6 5 4

解題想法

使用遞迴方式暴力找出所有排列的可能性，需要陣列num儲存輸入的n個數字，陣列step的元素儲存數字對應的陣列num索引值。遞迴需要一個參數，控制目前排列到第幾個(currStep)。