遞迴分割簡例I

 def div2(d):

    print(d)

    global c

    c +=1

    if len(d)<=1:

        return d

    m = len(d)//2

    d1 = d[:m]

    div2(d1)

    d2 = d[m:]

    div2(d2)

d = [1,3,5, 7, 8, 6, 4, 2]

c=0

div2(d)

print(c)

# result:

# [1, 3, 5, 7, 8, 6, 4, 2]

# [1, 3, 5, 7]

# [1, 3]

# [1]

# [3]

# [5, 7]

# [5]

# [7]

# [8, 6, 4, 2]

# [8, 6]

# [8]

# [6]

# [4, 2]

# [4]

# [2]

# 15




div2 函式是一個遞迴函式，主要作用是將一個列表 d 不斷分割成更小的子列表，直到每個子列表只有一個元素為止。具體流程如下：

函式內部流程

1. 全域變數 c：

   • c 是在函式外部定義的全域變數，用來計算 div2 函式被呼叫的次數。
   • 每當 div2 被呼叫時，c 的值都會加 1，最後的 c 值就代表總共呼叫了多少次 div2 函式。

2. 遞迴分割：

   • 如果列表 d 的長度小於或等於 1（if len(d) <= 1），則表示該子列表已經分割到最小，不需要再分割，因此直接返回該列表作為遞迴的終止條件。
   • 如果 d 的長度大於 1，則將其分為兩部分：
     • d1 是 d 的前半部分（d[:m]）。
     • d2 是 d 的後半部分（d[m:]）。
   • 接著，函式會分別對 d1 和 d2 再次遞迴呼叫 div2，不斷分割直到每個子列表只剩下一個元素。

3. 列印語句：

   • print(d) 的作用是在每次呼叫 div2 時，列印出當前的列表 d，方便觀察每次遞迴的分割過程。

為什麼 c 最終為 15？

以 d = [1, 3, 5, 7, 8, 6, 4, 2] 這個列表為例，包含 8 個元素。這個函式會對整個列表進行遞迴分割，直到每個子列表只有一個元素。以下是遞迴分割的過程：

1. 初始呼叫 [1, 3, 5, 7, 8, 6, 4, 2]，分割成 [1, 3, 5, 7] 和 [8, 6, 4, 2]
2. 呼叫 [1, 3, 5, 7]，分割成 [1, 3] 和 [5, 7]
3. 呼叫 [1, 3]，分割成 [1] 和 [3]（達到基礎情況，不再分割）
4. 呼叫 [5, 7]，分割成 [5] 和 [7]（達到基礎情況）
5. 呼叫 [8, 6, 4, 2]，分割成 [8, 6] 和 [4, 2]
6. 呼叫 [8, 6]，分割成 [8] 和 [6]（達到基礎情況）
7. 呼叫 [4, 2]，分割成 [4] 和 [2]（達到基礎情況）

數一數所有的呼叫次數，包括每次分割和達到基礎情況的呼叫，總共是 15 次，這就是為什麼 c 最後的值是 15。

• div2 函式演示了遞迴分割列表的過程。
• c 計算了所有遞迴呼叫的總次數，在這個例子中為 15 次。