【Python基礎教學】生成式&演算法&遞迴【part-10】

哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。

本篇將講解生成式（Comprehension）、演算法（Algorithm）、遞迴（Recursion），這些東西都是將來實作Python時非常常見且常用的語法及演算法，總之，你學了這些東西就知道它們到底有多好用了。

生成式（Comprehension）

生成式，又稱為推導式（大陸說法），英文名為 Comprehension。

生成式可以運用在可迭代的物件上，只要撰寫一行程式碼就能完成多行的任務，大幅增加程式碼的簡潔性與可讀性。

在 Python 具有以下幾種生成式：

  • 列表生成式
  • 字典生成式
  • 集合生成式
  • 元組生成式

註：元組 tuple 並沒有生成式，而是用類似生成式的方式產生 tuple。

2024/08/14 補：生成式要從右邊讀到左邊。

列表生成式（List Comprehension）

以下是列表生成式之語法：

1
2
3
4
5
6
7
[運算式 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 進行實作）：

1
2
3
4
5
6
>>> a = []
>>> for i in range(10):
>>>    a.append(i)
    
>>> print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

若我們使用列表生成式，那麼將會節省三行的程式碼：

1
2
3
>>> a = [int(i) for i in range(10)]
>>> print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我們可以從上面看到，當我們使用列表生成式，會將程式碼變得更加簡潔，也更容易讀。這在當我們之後在 APCS 上實作時，第一步的輸入數值我們可以這樣使用。

接下來是一個計算 30 以內可被 3 整除的整數的程式碼：

1
2
3
>>> 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。

1
2
3
4
5
6
7
8
9
10
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 教育學習網

上面的範例示範了兩種例子，一種是不使用列表生成式，使用 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]。
:::

列表生成式（進階範例）

1
2
3
>>> a = 5
>>> [a for _ in range(10)]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

最前面的 i 可換成變數，如上範例中的 a，則接下來生成的數字都會被變數 a 的值固定住。

這有什麼用途呢？可用於生成具有初始值的列表，如下範例：

1
2
>>> [0 for _ in range(10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1
2
>>> [[0] for _ in range(10)]
[[0], [0], [0], [0], [0], [0], [0], [0], [0], [0]]

:::success
註：通常一個 for 迴圈中的迭代變數沒有實際被用到的話，我們都會用 _ 替代 i，表示這個變數從頭到尾都沒被用到。
:::

初始化 3x3 矩陣生成：

1
2
3
>>> matrix = [[0 for _ in range(3)] for _ in range(3)]
>>> print(matrix)
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

為了方便查看矩陣，可寫成以下形式：

1
2
3
[[0, 0, 0], 
 [0, 0, 0], 
 [0, 0, 0]]

3x3 矩陣生成，每個元素都是各行號各列號的總和。

1
2
3
4
5
6
7
8
9
>>> 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）

1
2
3
4
5
{key_expr: value_expr for value in collection}

或

{key_expr: value_expr for value in collection if condition}

以下是字典生成式的一個範例：

1
2
3
4
>>> 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 會幫我們將裡面的內容顯示出來，可以看到每一個鍵，他的值會是這個鍵的長度。

以下是一個用字典生成式生成的平方表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
>>> 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
}
'''

字典生成式（進階範例）

以下程式碼演示如何將兩列表轉字典：

1
2
3
4
5
>>> 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

zip(*iterables) 函數用於將可迭代的物件作為參數，將物件中對應的元素打包成一個個元組，然後回傳由這些元組組成的列表。

iterable -> 一個或多個迭代器

回傳值：迭代器中的元組

總之 zip() 的用途你可以這樣想：可以將多個列表打包在一起，如上範例有 keys、values，則 ‘a’ 跟 1 一組，’b’ 跟 2 一組，以此類推。
:::

以下的方法也可用於互換字典鍵值：

1
2
3
>>> a = {'a' : 1, 'b' : 2, 'c' : 3}
>>> print(dict(zip(a.values(), a.keys())))
{1: 'a', 2: 'b', 3: 'c'}

所以 zip() 函數也具有互換的性質。如果將其用在列表內含元組的形式的話，則 zip() 具有將其行列互換的性質。

以下是用 if 來過濾的字典生成式之範例：

1
2
3
4
>>> 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}

以下是巢狀字典生成式之範例（這個範例非常難，可斟酌學習）：

1
2
3
4
5
6
7
8
9
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)

輸出：

1
2
3
4
5
6
7
8
9
{'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 總共有三個，因為有三位學生，所以如下：

1
2
3
4
5
{
    'Alice' : {'各科' : 成績, ...},
    'Bob' : {'各科' : 成績, ...},
    'Charlie' : {'各科' : 成績, ...}
}

此時我們先用簡單的方式去設計這個程式，如下：

1
2
3
4
5
6
7
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()：

1
2
3
4
5
6
7
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)

輸出結果：

1
2
3
4
5
6
7
8
9
10
11
12
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）

1
2
3
4
5
{expression for item in Sequence}

或

{expression for item in Sequence if conditional}

以下是一個計算 1,2,3 二次方的程式碼，以集合生成式表示：

1
2
3
>>> a = {i**2 for i in (1,2,3)}
>>> a
{1, 4, 9}

或是這樣寫：

1
2
a = {i*i for i in range(1,10)}
print(a)       # {64, 1, 4, 36, 9, 16, 49, 81, 25}

至於為什麼輸出結果會是先從 64 開始呢？我們在前面說過，集合是屬於無序的序列，無序就代表說沒有順序，因此輸出結果會是從 64 開始。

集合生成式（進階範例）

以下為對稱差集的集合生成式之範例程式碼：

1
2
3
4
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 的字母對組合（且字母對不能是相同字母）：

1
2
3
letters = 'abcde'
letter_pairs = {(x, y) for x in letters for y in letters if x != y}
print(letter_pairs)

輸出結果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
{('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）

元組沒有生成式的語法，但是有類似的方式可以生成元組，其語法為：

1
variable = tuple(value for item in iterable)

variable：將型態為 tuple 的資料存入變數叫做 variable 裡面。
value：生成的值。
item：從迭代物件裡取出的項目。
iterable：可迭代的物件。

1
2
a = tuple(i for i in range(10))
print(a)   # (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

也可以使用運算式以及 if 判斷式產生 tuple。

1
2
a = tuple(i*i for i in range(10) if i>5)
print(a)   # (36, 49, 64, 81)

以上範例文字來源：生成式 ( 串列、字典、集合、元組 ) - Python 教學 | STEAM 教育學習網

基本演算法概念介紹

當我們學會 Python 大部分的操作跟一些基礎語法後，就讓我們來接觸演算法的世界。

要講解演算法之前，我們先來簡單說明一下什麼是演算法：

演算法其實就是為了解決一些問題而產生的概念，為了解決這些問題而達到一個目的，而用於解決問題的「方法」就是演算法。

演算法在作者我本人看來其實就是一套公式，只是這套公式會隨著問題的不同而進行變化，總之，要怎麼學會去靈活運用這套「公式」其實才是最重要的。

比如說我們拿一個最簡單的例子來做解釋，以下是一個泡沫排序法的演算過程：

1_GUkhhrPDfgdvvwVFo-il1g

gif source：BUBBLE SORT (Ascendant Algorithm) | by J3 | Jungletronics | Medium

泡沫排序法是最簡單的排序法。其原理基本上就是判斷前後數字大小，如果兩者之間比較，前面的數字比較大，後面數字比較小，那麼就將前面的數字與後面的數字交換，以此類推，以此來達到數字由小到大的排序。

而排序的「過程」其實就是我們所說的演算法，若各位有看過演算法相關的書籍的話，應該都會看到那些書籍裡面通常都會寫：輸入 + 演算法 = 輸出。這個東西其實從上面的演算過程就可看出，排序前我們必須將一個尚未排序的序列「輸入」，輸入進去排序法這個「演算法」去做演算，最終排序好的升序序列即為「輸出」。

不過演算法並非所有的演算法都是最好最有效率的，也有那種效率非常差的演算法，而針對演算法效率的量測，我們就必須談到一個基本的概念：時間複雜度（Time complexity）

時間複雜度（Time complexity）

此處的時間，指的不是程式執行時所計算的秒數，而是從程式執行的第一步到完成，中間的步數。

簡單來說，就是當我們輸入內容的瞬間，到輸出結果的時間。

而時間複雜度的量測方法是採用步驟次數表示程式的執行時間，基本量測單位是一個步驟為單位，由步驟次數量測程式執行所需的時間，我們又將此步驟此數稱時間複雜度。

上文引用自書籍：演算法：圖解邏輯思維 + Python 程式實作 王者歸來 (第三版)

不知道各位有沒有玩過 AI 繪圖，如：stable diffusion，當我們要生成一張圖片時，他有個選項會是 step，這個指的是採樣步驟（Sampling steps），當我們將 step 拉越高時，那麼執行的時間也會跟著拉長，我們可以將這個概念聯想到時間複雜度上面。

在表示時間複雜度時，會使用 Big O(念作order)，下圖是幾種常見的表示方式：

image

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）

遞迴的概念其實非常簡單，並沒有各位想像的這麼複雜，簡單來說，遞迴就是呼叫自己，呼叫自己的函數，如下所示：

1
2
3
def recursion(a):
    print(a)
    return recursion(a-1)

上述是一個無限遞迴，這支程式會一直無限遞減下去，由於沒有設定終止條件，所以他會一直無限的循環這個動作。

另外我們可以看到 recursion 函數的內部，又呼叫了自己一次，這個就是遞迴。

遞迴具有以下兩種特性：

  1. 遞迴函數在每次處理時，都會使問題的範圍縮小。
  2. 必須要有一個終止條件來結束遞迴函數。

遞迴擁有讓程式碼變得簡潔的功能，但當我們在設計遞迴時，很容易不小心就忘記要設定終止條件，於是就讓他一直在那邊減減減減，減到永遠，針對上支程式，我們可以加入條件讓他終止：

1
2
3
4
5
6
7
8
def recursion(a):
    if a < 1:
        return 0
    else:
        recursion(a-1)
    print(a)

recursion(5)

輸出結果如下：

1
2
3
4
5
1
2
3
4
5

說到遞迴，我們需要利用遞迴的概念來說明另一個概念：堆疊（stack），堆疊是什麼我們等下再說，我們以剛才的例子來做解釋：

Python 或其他具有遞迴功能的語言（如：C 語言等），是採用堆疊的方式存儲在遞迴的期間尚未執行的指令，所以當 recursion 函數呼叫自己時，會將當時的 print(a) 指令存放到堆疊裡面，我們將用圖示來表示堆疊的狀態：

recursion_1

圖源：由作者繪製

上圖是第一次遞迴時，此時的 a 值 = 5，我們將會慢慢放入 print() 指令在裡面。

recursion_2

第二次遞迴時，此時的 a 值 = 4。

備註：此時的任何的 print() 指令都還沒有開始執行，只是暫時被存放到堆疊的空間裡面，只有等遞迴結束時才會一一的取出執行。

recursion_3

第三次遞迴時，此時的 a 值 = 3。

recursion_4

第四次遞迴時，此時的 a 值 = 2。

recursion_5

第五次遞迴時，此時的 a 值 = 1。

接下來重點來了，務必記住，堆疊是「後進先出（last in first out -> 簡寫：LIFO）」，確實，我們可以從這幾張圖看到具有後進先出的情形，而當遞迴結束後，會從堆疊一個一個取出來，首先從最上層開始的 print(1)，到最下層的 print(5)，因此輸出結果形成了：

1
2
3
4
5
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。

有關上述的數學沒有問題的話，我們可以進一步寫成這個公式（高一下：數列章節中所教的遞迴關係）：

image

以下是我們在高中階段數學課上所熟悉的遞迴關係式（等差數列）：

image

我們可以利用遞迴關係式來對遞迴進行解題，在程式語言上會比較容易設計及理解，不過，首先讓我們隨意代入一個數值進去上面的遞迴關係式（階層的），比如說 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。

接下來就讓我們實際應用到程式語言上面囉：

1
2
3
4
5
def factorial_recur(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

費氏數列（Fibonacci Sequence）

費氏數列（Fibonacci Sequence），又稱費波那契數列，是在數學歷史上最為經典的數列，同時也是在程式語言中闡述遞迴觀念時，時常會被拿出來當作範例的例子。

費氏數列指的是一個數列中，每一項都等於他的前兩項的和，也就是說第 n 項等於第 n-1 項以及第 n-2 項的和。

image

這是費氏數列的遞迴關係式，同樣地，我們一樣依照遞迴關係式來撰寫遞迴程式：

1
2
3
4
5
6
7
def Fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

學會使用遞迴後，會發現這種表現方式其實非常簡單也非常易懂，遞迴並沒有你想像的這麼複雜（註：現在還算是比較基礎的數學運算而已喔）。

所以，讓我們學習如何使用迴圈來重現費氏數列：

1
2
3
4
5
6
7
8
9
10
11
12
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）

分成：

  • 列表生成式
  • 字典生成式
  • 集合生成式
  • 元組生成式

其他生成式可以不會，但列表生成式你不能不會！

以下是各大生成式的語法格式，依照以上的順序編排：

1
2
3
4
5
6
7
[運算式 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]
1
2
3
4
5
{key_expr: value_expr for value in collection}

或

{key_expr: value_expr for value in collection if condition}
1
2
3
4
5
{expression for item in Sequence}

或

{expression for item in Sequence if conditional}
1
variable = tuple(value for item in iterable)

演算法理論（Algorithm theory）

演算法（Algorithm）：從輸入開始到輸入結束的過程。

以下是在演算法輸出的過程中，所需理解的一些名詞：

  • 時間複雜度（Time Complexity）：指的是演算法過程中所執行的步驟數。
  • 空間複雜度（Space Complexity）：指的是演算法中「暫時儲存中間數據所需的空間」，空間指的是記憶體內的空間，也可以稱為空間成本。演算法在執行過程中可能需要空間存放資料，消耗記憶體。

遞迴（Recursion）

簡單說就是一個函數內部再呼叫自己。

1
2
def recursion(a):
    recursion(a-1)

這是無限遞迴，不斷遞迴下去。

常見例子：階乘（Factorial）、費氏數列（Fibonacci Sequence）等。

參考資料

Day01：時間複雜度 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

Day02：空間複雜度 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

[演算法] 時間複雜度與空間複雜度 | Medium

Python 推導式 | 菜鳥教程

生成式 ( 串列、字典、集合、元組 ) - Python 教學 | STEAM 教育學習網

BUBBLE SORT (Ascendant Algorithm) | by J3 | Jungletronics | Medium

Python 初學第八講 — 遞迴. 遞迴 Recursion：將大問題切成小問題 | by Yu-Hsuan Chou | ccClub | Medium

Day18 - 當我們「鏈」在一起，認識zip()函數 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

Python zip() 函数 | 菜鸟教程

2. Built-in Functions — Python 3.3.7 documentation