【Python基礎教學】生成式&演算法&遞迴【part-10】
===
目錄（Table of Contents）
[TOC]
---
哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。
本篇將講解生成式（Comprehension）、演算法（Algorithm）、遞迴（Recursion），這些東西都是將來實作Python時非常常見且常用的語法及演算法，總之，你學了這些東西就知道它們到底有多好用了。
生成式（Comprehension）
---
生成式，又稱為推導式，英文名為 Comprehension。
> 生成式可以運用在可迭代的物件上，只要撰寫一行程式碼就能完成多行的任務，大幅增加程式碼的簡潔性與可讀性。
在 Python 具有以下幾種生成式：
* 列表生成式
* 字典生成式
* 集合生成式
* 元組生成式
> 註：元組 tuple 並沒有生成式，而是用類似生成式的方式產生 tuple。
2024/08/14 補：生成式要從右邊讀到左邊。
### 列表生成式（List Comprehension）
---
以下是列表生成式之語法：
```python=
[運算式 for 變數 in 列表]
[out_exp_res for out_exp in input_list]
或
[運算式 for 變數 in 列表 if 條件]
[out_exp_res for out_exp in input_list if condition]
```
**out_exp_res**：列表產生元素運算式，可以是有回傳值的函數。
**for out_exp in input_list**：迭代 input_list 將 out_exp 傳入到 out_exp_res 運算式中。
**if condition**：條件語句，可以篩選列表中不符合條件的值。
簡單來說，列表生成式就是在列表的中括號內部對可迭代的物件進行迭代，這樣做能夠省去三行代碼去創建列表，以下是兩個比較範例（以下兩範例皆於 Python IDLE Shell 進行實作）：
```python=
>>> a = []
>>> for i in range(10):
>>> a.append(i)
>>> print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
若我們使用列表生成式，那麼將會節省三行的程式碼：
```python=
>>> a = [int(i) for i in range(10)]
>>> print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
我們可以從上面看到，當我們使用列表生成式，會將程式碼變得更加簡潔，也更容易讀。這在當我們之後在 APCS 上實作時，第一步的輸入數值我們可以這樣使用。
接下來是一個計算 30 以內可被 3 整除的整數的程式碼：
```python=
>>> a = [int(i) for i in range(30) if i % 3 == 0]
>>> print(a)
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
```
> 如果將 if 放在 for 的前方，就必須加上 else（三元運算式（條件運算式）），下方的例子，會將偶數的項目保留，奇數項目替換成 100。
```python=
a = []
for i in range(1,10):
if i%2 == 0:
a.append(i) # 取出偶數放入變數 a
else:
a.append(100) # 如果是奇數，將 100 放入變數 a
print(a) # [100, 2, 100, 4, 100, 6, 100, 8, 100]
a = [i if i%2==0 else 100 for i in range(1, 10)]
print(a) # [100, 2, 100, 4, 100, 6, 100, 8, 100]
```
範例來自：[生成式 ( 串列、字典、集合、元組 ) - Python 教學 | STEAM 教育學習網](https://steam.oxxostudio.tw/category/python/basic/comprehension.html)
上面的範例示範了兩種例子，一種是不使用列表生成式，使用 for 迴圈與 if 條件式的應用；一種是使用列表生成式內部的條件式與 for 迴圈進行迭代。
與我們剛剛範例寫法不同的是，這個範例在最下方將 if 移到 for 的前面，在這種狀況下我們必須加上 else。
好，那這樣寫是什麼意思呢？簡單來說就是當我們 if 判斷變數 i 是否能夠整除 2 時，那麼就保留那個 i 值，否則（不整除 2），那麼就將 i 值變成 100。
經過上下對照，我們可以發現如果可以只用一行解決，那我們就用一行解決，盡可能簡化我們的程式碼。
:::success
這樣理解就懂！
列表生成式（基本型）：[i for i in range(10)]，最前面的 i 可以加上 int()、str() 等函數轉變資料型態，做靈活應用。※式子最終生成 [0,1,2,3,4,5,6,7,8,9]。
列表生成式（單一條件型）：[i for i in range(10) if i%2==0]，注意這邊 if 放最後面，表示 i%2 == 0 的數字才會生成出來。※式子最終生成 [0,2,4,6,8]。
列表生成式（if-else 型）：[i if i%2==0 else -1 for i in range(10)]，注意這邊 if 放最前面（但是在 i 後面），放前面的 if，後面必定接 else，不接就會出錯。表示 i%2 == 0 的數字才會被生成出來，但 i%2 != 0 的數字就指定生成為 -1。※式子最終生成 [0, -1, 2, -1, 4, -1, 6, -1, 8, -1]。
:::
### 列表生成式（進階範例）
---
```python=
>>> a = 5
>>> [a for _ in range(10)]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
```
最前面的 i 可換成變數，如上範例中的 a，則接下來生成的數字都會被變數 a 的值固定住。
這有什麼用途呢？可用於生成具有初始值的列表，如下範例：
```python=
>>> [0 for _ in range(10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```
```python=
>>> [[0] for _ in range(10)]
[[0], [0], [0], [0], [0], [0], [0], [0], [0], [0]]
```
:::success
註：通常一個 for 迴圈中的迭代變數沒有實際被用到的話，我們都會用 _ 替代 i，表示這個變數從頭到尾都沒被用到。
:::
初始化 3x3 矩陣生成：
```python=
>>> matrix = [[0 for _ in range(3)] for _ in range(3)]
>>> print(matrix)
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
```
為了方便查看矩陣，可寫成以下形式：
```python=
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
```
3x3 矩陣生成，每個元素都是各行號各列號的總和。
```python=
>>> matrix = [[i + j for j in range(3)] for i in range(3)]
>>> print(matrix)
[[0, 1, 2], [1, 2, 3], [2, 3, 4]]
'''
[[0, 1, 2],
[1, 2, 3],
[2, 3, 4]]
'''
```
### 字典生成式（Dictionary Comprehension）
---
```python=
{key_expr: value_expr for value in collection}
或
{key_expr: value_expr for value in collection if condition}
```
以下是字典生成式的一個範例：
```python=
>>> a1 = ["Hello", "I", "am", "IT_man"]
>>> a2 = {key:len(key) for key in a1}
>>> a2
{'Hello': 5, 'I': 1, 'am': 2, 'IT_man': 6}
```
首先第一行我們宣告一個變數，裡面的元素全都是字串。
第二行我們就使用了字典生成式，那麼這個 key 並不是絕對、唯一的，你也可以取 i 作為 key。而在後面我們一樣可以像列表生成式一樣使用 for 迴圈迭代。
而第二行的 key 冒號後面，有個 len(key)，代表說我們的值會被賦予 len(key) 函數 return 後的數值，也就是裡面的長度。而後面則是將列表 a1 進行迭代，a1 將會被作為鍵（key），前面的 len(key) 就是將鍵輸入進去，輸出他的長度出來。
第三行寫 a2，Python 會幫我們將裡面的內容顯示出來，可以看到每一個鍵，他的值會是這個鍵的長度。
以下是一個用字典生成式生成的平方表：
```python=
>>> square_dict = {i: i**2 for i in range(1, 20)}
>>> square_dict
{1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100, 11: 121, 12: 144, 13: 169, 14: 196, 15: 225, 16: 256, 17: 289, 18: 324, 19: 361}
'''
{
1: 1,
2: 4,
3: 9,
4: 16,
5: 25,
6: 36,
7: 49,
8: 64,
9: 81,
10: 100,
11: 121,
12: 144,
13: 169,
14: 196,
15: 225,
16: 256,
17: 289,
18: 324,
19: 361
}
'''
```
### 字典生成式（進階範例）
---
以下程式碼演示如何將兩列表轉字典：
```python=
>>> keys = ['a', 'b', 'c']
>>> values = [1, 2, 3]
>>> dictionary = {k: v for k, v in zip(keys, values)}
>>> print(dictionary)
{'a': 1, 'b': 2, 'c': 3}
```
:::success
zip(*iterables)
Make an iterator that aggregates elements from each of the iterables.
Returns an iterator of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables. The iterator stops when the shortest input iterable is exhausted. With a single iterable argument, it returns an iterator of 1-tuples. With no arguments, it returns an empty iterator.
source : [2. Built-in Functions — Python 3.3.7 documentation](https://docs.python.org/3.3/library/functions.html#zip)
> zip(*iterables) 函數用於將可迭代的物件作為參數，將物件中對應的元素打包成一個個元組，然後回傳由這些元組組成的列表。
iterable -> 一個或多個迭代器
回傳值：迭代器中的元組
總之 zip() 的用途你可以這樣想：可以將多個列表打包在一起，如上範例有 keys、values，則 'a' 跟 1 一組，'b' 跟 2 一組，以此類推。
:::
以下的方法也可用於互換字典鍵值：
```python=
>>> a = {'a' : 1, 'b' : 2, 'c' : 3}
>>> print(dict(zip(a.values(), a.keys())))
{1: 'a', 2: 'b', 3: 'c'}
```
所以 zip() 函數也具有互換的性質。***如果將其用在列表內含元組的形式的話，則 zip() 具有將其行列互換的性質。***
以下是用 if 來過濾的字典生成式之範例：
```python=
>>> original_dict = {'apple': 5, 'banana': 3, 'orange': 10, 'kiwi': 2}
>>> filtered_dict = {k: v for k, v in original_dict.items() if v > 3}
>>> print(filtered_dict)
{'apple': 5, 'orange': 10}
```
以下是巢狀字典生成式之範例（這個範例非常難，可斟酌學習）：
```python=
students = ['Alice', 'Bob', 'Charlie']
subjects = ['Math', 'Science', 'English']
all_grades = [
[85, 90, 88], # Alice
[78, 83, 82], # Bob
[92, 88, 91] # Charlie
]
grades = {student: {subject: grade for subject, grade in zip(subjects, grades)} for student, grades in zip(students, all_grades)}
print(grades)
```
輸出：
```python=
{'Alice': {'Math': 85, 'Science': 90, 'English': 88}, 'Bob': {'Math': 78, 'Science': 83, 'English': 82}, 'Charlie': {'Math': 92, 'Science': 88, 'English': 91}}
整理如下：
{
'Alice': {'Math': 85, 'Science': 90, 'English': 88},
'Bob': {'Math': 78, 'Science': 83, 'English': 82},
'Charlie': {'Math': 92, 'Science': 88, 'English': 91}
}
```
範例解釋：
這個範例難的地方在於設計字典生成式的部分。
首先我們必須要釐清一下這個架構：{"學生名稱" : {"各科" : 成績, ...}}，然後這樣子的 item 總共有三個，因為有三位學生，所以如下：
```=
{
'Alice' : {'各科' : 成績, ...},
'Bob' : {'各科' : 成績, ...},
'Charlie' : {'各科' : 成績, ...}
}
```
此時我們先用簡單的方式去設計這個程式，如下：
```python=
grades = {}
for student, grades_list in zip(students, all_grades):
subject_grades = {}
for subject, grade in zip(subjects, grades_list):
subject_grades[subject] = grade
grades[student] = subject_grades
```
這邊是一個技巧，先用簡單易讀的方式把程式碼寫出來，之後再思考怎麼把它結合成一行的形式。註：這個程式輸出結果與前面用一行的方式是相同的唷。
為了更好理解程式碼的運作方式，可加入 print()：
```python=
for student, grades_list in zip(students, all_grades):
subject_grades = {}
for subject, grade in zip(subjects, grades_list):
subject_grades[subject] = grade
print("subject_grades =",subject_grades)
grades[student] = subject_grades
print("grades =",grades)
```
輸出結果：
```python=
subject_grades = {'Math': 85}
subject_grades = {'Math': 85, 'Science': 90}
subject_grades = {'Math': 85, 'Science': 90, 'English': 88}
grades = {'Alice': {'Math': 85, 'Science': 90, 'English': 88}}
subject_grades = {'Math': 78}
subject_grades = {'Math': 78, 'Science': 83}
subject_grades = {'Math': 78, 'Science': 83, 'English': 82}
grades = {'Alice': {'Math': 85, 'Science': 90, 'English': 88}, 'Bob': {'Math': 78, 'Science': 83, 'English': 82}}
subject_grades = {'Math': 92}
subject_grades = {'Math': 92, 'Science': 88}
subject_grades = {'Math': 92, 'Science': 88, 'English': 91}
grades = {'Alice': {'Math': 85, 'Science': 90, 'English': 88}, 'Bob': {'Math': 78, 'Science': 83, 'English': 82}, 'Charlie': {'Math': 92, 'Science': 88, 'English': 91}}
```
可以發現每次 for 迴圈（第二層 for）迭代的時候，subject_grades[subject] 會依次列出每位學生的各項成績，三項印完後就直接跳到下一個 grades[student] = subject_grades，更新值為 subject_grades。
***（字典的賦值會增加或更新鍵值對）***
所以在第一次的迴圈下，grades[student] 的鍵為 'Alice'，然後更新值為 subject_grades，而這個值是一個字典 {'Math': 85, 'Science': 90, 'English': 88}，故鍵值對：'Alice' : {'Math': 85, 'Science': 90, 'English': 88}。
接下來進行第二次的迴圈，跟上面一樣的步驟。這邊注意每次迴圈的開始都會讓 subject_grades = {}，也就是讓他變空字典，然後繼續讀取下一位學生的資料。
最後，再把它濃縮成一行：`grades = {student: {subject: grade for subject, grade in zip(subjects, grades)} for student, grades in zip(students, all_grades)}`
### 集合生成式（Set Comprehension）
---
```python=
{expression for item in Sequence}
或
{expression for item in Sequence if conditional}
```
以下是一個計算 1,2,3 二次方的程式碼，以集合生成式表示：
```python=
>>> a = {i**2 for i in (1,2,3)}
>>> a
{1, 4, 9}
```
或是這樣寫：
```python=
a = {i*i for i in range(1,10)}
print(a) # {64, 1, 4, 36, 9, 16, 49, 81, 25}
```
至於為什麼輸出結果會是先從 64 開始呢？我們在前面說過，集合是屬於無序的序列，無序就代表說沒有順序，因此輸出結果會是從 64 開始。
### 集合生成式（進階範例）
---
以下為對稱差集的集合生成式之範例程式碼：
```python=
set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7}
symmetric_difference_even = {x for x in set1 ^ set2 if x % 2 == 0}
print(symmetric_difference_even) # {2,6}
```
對稱差集就把它想成是有交集的地方都忽略、刪掉就行，比如說上面的例子，對稱差集為 {1,2,3,6,7}。
而在這個對稱差集中只求偶數，所以剩下 {2,6}。
註：`^` 運算子用於對稱差集。
以下為生成所有長度為 2 的字母對組合（且字母對不能是相同字母）：
```python=
letters = 'abcde'
letter_pairs = {(x, y) for x in letters for y in letters if x != y}
print(letter_pairs)
```
輸出結果：
```python=
{('b', 'a'), ('e', 'd'), ('c', 'a'), ('a', 'd'), ('d', 'a'), ('b', 'd'), ('e', 'c'), ('c', 'd'), ('e', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b'), ('a', 'e'), ('b', 'e'), ('d', 'c'), ('c', 'e'), ('c', 'b'), ('d', 'e'), ('d', 'b'), ('e', 'a')}
整理如下：
{
('b', 'a'),
('e', 'd'),
('c', 'a'),
('a', 'd'),
('d', 'a'),
('b', 'd'),
('e', 'c'),
('c', 'd'),
('e', 'b'),
('a', 'c'),
('b', 'c'),
('a', 'b'),
('a', 'e'),
('b', 'e'),
('d', 'c'),
('c', 'e'),
('c', 'b'),
('d', 'e'),
('d', 'b'),
('e', 'a')
}
```
以上輸出的結果共有 20 種組合，因為共有 5 個英文字母，而要生成所有可能長度為 2 的英文字母組合對，並且兩字母間不能相同（因為集合的性質為無序、不重複）。
首先第一個字母可以為任意的字母，共 5 種選擇，第二個字母必定不能跟第一個相同，共 4 種選擇，所以透過乘法原理求得 5 * 4 = 20 種組合。
### 元組生成式（Tuple Comprehension）
---
> 元組沒有生成式的語法，但是有類似的方式可以生成元組，其語法為：
```python=
variable = tuple(value for item in iterable)
```
> variable：將型態為 tuple 的資料存入變數叫做 variable 裡面。
> value：生成的值。
> item：從迭代物件裡取出的項目。
> iterable：可迭代的物件。
```python=
a = tuple(i for i in range(10))
print(a) # (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
```
> 也可以使用運算式以及 if 判斷式產生 tuple。
```python=
a = tuple(i*i for i in range(10) if i>5)
print(a) # (36, 49, 64, 81)
```
以上範例文字來源：[生成式 ( 串列、字典、集合、元組 ) - Python 教學 | STEAM 教育學習網](https://steam.oxxostudio.tw/category/python/basic/comprehension.html)
基本演算法概念介紹
---
當我們學會 Python 大部分的操作跟一些基礎語法後，就讓我們來接觸演算法的世界。
要講解演算法之前，我們先來簡單說明一下什麼是演算法：
演算法其實就是為了解決一些問題而產生的概念，為了解決這些問題而達到一個目的，而用於解決問題的「方法」就是演算法。
演算法在作者我本人看來其實就是一套公式，只是這套公式會隨著問題的不同而進行變化，總之，要怎麼學會去靈活運用這套「公式」其實才是最重要的。
比如說我們拿一個最簡單的例子來做解釋，以下是一個泡沫排序法的演算過程：
gif source：[BUBBLE SORT (Ascendant Algorithm) | by J3 | Jungletronics | Medium](https://medium.com/jungletronics/bubble-sort-ascendant-algorithm-5a3cf7b530f7)
泡沫排序法是最簡單的排序法。其原理基本上就是判斷前後數字大小，如果兩者之間比較，前面的數字比較大，後面數字比較小，那麼就將前面的數字與後面的數字交換，以此類推，以此來達到數字由小到大的排序。
而排序的「過程」其實就是我們所說的演算法，若各位有看過演算法相關的書籍的話，應該都會看到那些書籍裡面通常都會寫：輸入 + 演算法 = 輸出。這個東西其實從上面的演算過程就可看出，排序前我們必須將一個尚未排序的序列「輸入」，輸入進去排序法這個「演算法」去做演算，最終排序好的升序序列即為「輸出」。
不過演算法並非所有的演算法都是最好最有效率的，也有那種效率非常差的演算法，而針對演算法效率的量測，我們就必須談到一個基本的概念：時間複雜度（Time complexity）
### 時間複雜度（Time complexity）
---
> 此處的時間，指的不是程式執行時所計算的秒數，而是從程式執行的第一步到完成，中間的步數。
簡單來說，就是當我們輸入內容的瞬間，到輸出結果的時間。
> 而時間複雜度的量測方法是採用**步驟次數**表示程式的執行時間，基本量測單位是一個步驟為單位，由步驟次數量測程式執行所需的時間，我們又將此步驟此數稱時間複雜度。
上文引用自書籍：**演算法：圖解邏輯思維 + Python 程式實作 王者歸來 (第三版)**
不知道各位有沒有玩過 AI 繪圖，如：stable diffusion，當我們要生成一張圖片時，他有個選項會是 step，這個指的是採樣步驟（Sampling steps），當我們將 step 拉越高時，那麼執行的時間也會跟著拉長，我們可以將這個概念聯想到時間複雜度上面。
> 在表示時間複雜度時，會使用 Big O(念作order)，下圖是幾種常見的表示方式：
O(1)：陣列讀取
O(n)：無序陣列的搜尋
O(log n)：二分搜尋
O(n log n)：合併排序，最快的比較排序
O(n²)：泡沫排序、插入排序
O(2^n)：費波那契數列
執行效率：
> O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n^2) < O(n^3) < O(2^n) < O(n!)
2^n -> 代表平方根 n。
至於總執行時間，我們會以 T(n) 作為表示，
> Big O 通常只看最高次方項，並且忽略掉項次前的係數，例如 Big O(2n² + n)，會簡化成 O(n²)＝T(n)。
O(1) -> 時間固定成長（也稱常數成長：Constant Run Time），無論資料量多大多小，演算法執行的次數不變。
O(n) -> 時間線性成長（Linear Run Time），會依照輸入的資料量（n）增加，成等比例成長（成正比圖形、斜直線）。
O(log n) —> 時間對數成長（Logarithmic Run Time），表示演算法的執行時間隨著資料量增加「成對數成長」。
O(n²) —> 時間指數成長（Exponential Run Time），表示演算法執行的時間，會依照輸入的資料量增加，成指數成長。
...
以此類推，反正就是框框裡面有什麼，就是成什麼成長，效率高的演算法，通常落在 n ~ n² 的區間，而 log n 的代表就是二分搜尋演算法，之後我們再來進行教學。
### 空間複雜度（Space Complexity）
---
程式演算法在執行時需要兩種空間如下：
1. 程式輸入 / 輸出所需的空間
2. 程式執行過程，需要暫時儲存中間數據所需的空間
> 程式輸入與輸出是必須的，所以不用計算，而空間複雜度（Space Complexity）指的是執行演算法中「暫時儲存中間數據所需的空間」，空間指的是記憶體內的空間，也可以稱為空間成本。
上文引用自書籍：**演算法：圖解邏輯思維 + Python 程式實作 王者歸來 (第三版)**
而空間複雜度的表示法如同時間複雜度，都以 Big O 表示，前面有說明過，時間複雜度是以執行完成步數（step）為主，不考慮空間（記憶體）；空間複雜度是以空間為主，不考慮完成時間。
總之，空間複雜度（Space Complexity）就是在當電腦執行演算法時，所需要消耗的記憶體空間來做計算。
O(1) —> 固定資料量：程式執行後，變數 i 的資料數量大小，永遠不會進行改變。
O(n) -> 空間線性成長：程式執行後，陣列 arr 的資料數量大小，會等比例成長。
遞迴（recursion）
---
遞迴的概念其實非常簡單，並沒有各位想像的這麼複雜，簡單來說，遞迴就是呼叫自己，呼叫自己的函數，如下所示：
```python=
def recursion(a):
print(a)
return recursion(a-1)
```
上述是一個無限遞迴，這支程式會一直無限遞減下去，由於沒有設定終止條件，所以他會一直無限的循環這個動作。
另外我們可以看到 recursion 函數的內部，又呼叫了自己一次，這個就是遞迴。
遞迴具有以下兩種特性：
1. 遞迴函數在每次處理時，都會使問題的範圍縮小。
2. 必須要有一個終止條件來結束遞迴函數。
遞迴擁有讓程式碼變得簡潔的功能，但當我們在設計遞迴時，很容易不小心就忘記要設定終止條件，於是就讓他一直在那邊減減減減，減到永遠，針對上支程式，我們可以加入條件讓他終止：
```python=
def recursion(a):
if a < 1:
return 0
else:
recursion(a-1)
print(a)
recursion(5)
```
輸出結果如下：
```python=
1
2
3
4
5
```
說到遞迴，我們需要利用遞迴的概念來說明另一個概念：堆疊（stack），堆疊是什麼我們等下再說，我們以剛才的例子來做解釋：
Python 或其他具有遞迴功能的語言（如：C 語言等），是採用堆疊的方式存儲在遞迴的期間尚未執行的指令，所以當 recursion 函數呼叫自己時，會將當時的 print(a) 指令存放到堆疊裡面，我們將用圖示來表示堆疊的狀態：
圖源：由作者繪製
上圖是第一次遞迴時，此時的 a 值 = 5，我們將會慢慢放入 print() 指令在裡面。
第二次遞迴時，此時的 a 值 = 4。
備註：此時的任何的 print() 指令都還沒有開始執行，只是暫時被存放到堆疊的空間裡面，只有等遞迴結束時才會一一的取出執行。
第三次遞迴時，此時的 a 值 = 3。
第四次遞迴時，此時的 a 值 = 2。
第五次遞迴時，此時的 a 值 = 1。
接下來重點來了，務必記住，堆疊是「**後進先出（last in first out -> 簡寫：LIFO）**」，確實，我們可以從這幾張圖看到具有後進先出的情形，而當遞迴結束後，會從堆疊一個一個取出來，首先從最上層開始的 print(1)，到最下層的 print(5)，因此輸出結果形成了：
```python=
1
2
3
4
5
```
至於堆疊的部分，在當我們將資料放入堆疊裡面時，計算機術語稱為「堆入（push）」。而當直譯程式實際遞歸處理的過程，就是將資料從堆疊出取出，這個動作在計算機術語稱為「取出（pop）」。
總之，我希望各位能夠對於遞迴這個觀念深度了解，因為這在 APCS 觀念題跟實作題上都非常常見。
### 階乘（Factorial）
---
階乘，是在高中數學中常見的數學問題，以 n! 表示為 n 階，這代表說從 1 開始，連續乘，乘到 n 為止。
`n! = 1 * 2 * 3 * 4 * ... * n`
以下是階乘寫成函數的樣子：
`factorial(n) = 1 * 2 * ... * (n-1) * n = n * factorial(n-1)`
`factorial(n-1) = 1 * 2 * ... * (n-1)` 這個式子再乘上一個 n，就變成 `factorial(n)` 的形式了。
若對於線性代數沒有很熟的同學，我只能說一句：請加油，XD。
有關上述的數學沒有問題的話，我們可以進一步寫成這個公式（高一下：數列章節中所教的遞迴關係）：
以下是我們在高中階段數學課上所熟悉的遞迴關係式（等差數列）：
我們可以利用遞迴關係式來對遞迴進行解題，在程式語言上會比較容易設計及理解，不過，首先讓我們隨意代入一個數值進去上面的遞迴關係式（階層的），比如說 n = 5，就會變成這樣：
**factorial(5) = 5 * factorial(4)**
我們進入下一層（factorial(4)）：**factorial(4) = 4 * factorial(3)**
**factorial(3) = 3 * factorial(2)**
**factorial(2) = 2 * factorial(1)**
**factorial(1) = 1 * factorial(0)** 註：factorial(0) = 1，所以遞迴到此為止。
從 factorial(5) 的遞迴開始推到 factorial(1) 的過程，我們稱為遞推。
接下來我們要做的事情叫做遞歸，從 factorial(1) 得到的數值一個一個往上代回去給 factorial(5)：
**factorial(1) = 1 -> 回到 factorial(2)，factorial(2) = 2 * 1。**
**factorial(2) = 2 -> 回到 factorial(3)，factorial(3) = 3 * 2。**
**factorial(3) = 6 -> 回到 factorial(4)，factorial(4) = 4 * 6。**
**factorial(4) = 24 -> 回到 factorial(5)，factorial(5) = 5 * 24。**
最後得到 factorial(5) = 5 * 24 = 120，階乘 5 的數值就是 120。
透過數學式我們得到了遞迴關係，在當 n >= 1 的時候，關係式是 n*factorial(n-1)，而 n = 0 的時候，factorial(0) = 1。
接下來就讓我們實際應用到程式語言上面囉：
```python=
def factorial_recur(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
```
### 費氏數列（Fibonacci Sequence）
---
費氏數列（Fibonacci Sequence），又稱費波那契數列，是在數學歷史上最為經典的數列，同時也是在程式語言中闡述遞迴觀念時，時常會被拿出來當作範例的例子。
費氏數列指的是一個數列中，每一項都等於他的前兩項的和，也就是說第 n 項等於第 n-1 項以及第 n-2 項的和。
這是費氏數列的遞迴關係式，同樣地，我們一樣依照遞迴關係式來撰寫遞迴程式：
```python=
def Fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return Fib(n-1) + Fib(n-2)
```
學會使用遞迴後，會發現這種表現方式其實非常簡單也非常易懂，遞迴並沒有你想像的這麼複雜（註：現在還算是比較基礎的數學運算而已喔）。
所以，讓我們學習如何使用迴圈來重現費氏數列：
```python=
def fib_loop(n):
if n == 1 or n == 2:
return 1
else:
fib1 = 1
fib2 = 1
fib3 = 0
for i in range(2, n):
fib3 = fib1 + fib2
fib1 = fib2
fib2 = fib3
return fib3
```
ok，由於篇幅關係，本篇教學就先到此為止，以下是一些參考資料～
總結
---
### 生成式（Comprehension）
---
分成：
* 列表生成式
* 字典生成式
* 集合生成式
* 元組生成式
其他生成式可以不會，但列表生成式你不能不會！
以下是各大生成式的語法格式，依照以上的順序編排：
```python=
[運算式 for 變數 in 列表]
[out_exp_res for out_exp in input_list]
或
[運算式 for 變數 in 列表 if 條件]
[out_exp_res for out_exp in input_list if condition]
```
```python=
{key_expr: value_expr for value in collection}
或
{key_expr: value_expr for value in collection if condition}
```
```python=
{expression for item in Sequence}
或
{expression for item in Sequence if conditional}
```
```python=
variable = tuple(value for item in iterable)
```
### 演算法理論（Algorithm theory）
---
演算法（Algorithm）：從輸入開始到輸入結束的過程。
以下是在演算法輸出的過程中，所需理解的一些名詞：
* 時間複雜度（Time Complexity）：指的是演算法過程中所執行的步驟數。
* 空間複雜度（Space Complexity）：指的是演算法中「暫時儲存中間數據所需的空間」，空間指的是記憶體內的空間，也可以稱為空間成本。演算法在執行過程中可能需要空間存放資料，消耗記憶體。
### 遞迴（Recursion）
---
簡單說就是一個函數內部再呼叫自己。
```python=
def recursion(a):
recursion(a-1)
```
這是無限遞迴，不斷遞迴下去。
常見例子：階乘（Factorial）、費氏數列（Fibonacci Sequence）等。
參考資料
===
[Day01：時間複雜度 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10259142)
[Day02：空間複雜度 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10259229)
[[演算法] 時間複雜度與空間複雜度 | Medium](https://medium.com/@danny_hu/algorithm-time-complexity-and-space-complexity-7047dc37bd32)
[Python 推導式 | 菜鳥教程](https://www.runoob.com/python3/python-comprehensions.html)
[生成式 ( 串列、字典、集合、元組 ) - Python 教學 | STEAM 教育學習網](https://steam.oxxostudio.tw/category/python/basic/comprehension.html)
[BUBBLE SORT (Ascendant Algorithm) | by J3 | Jungletronics | Medium](https://medium.com/jungletronics/bubble-sort-ascendant-algorithm-5a3cf7b530f7)
[Python 初學第八講 — 遞迴. 遞迴 Recursion：將大問題切成小問題 | by Yu-Hsuan Chou | ccClub | Medium](https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-11ed5d300d3d)
[Day18 - 當我們「鏈」在一起，認識zip()函數 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10218029)
[Python zip() 函数 | 菜鸟教程](https://www.runoob.com/python/python-func-zip.html)
[2. Built-in Functions — Python 3.3.7 documentation](https://docs.python.org/3.3/library/functions.html#zip)
Sign in with Wallet
Connect another wallet