遞迴分割簡例 II

 讓我們逐步分析這個程式，以理解如何透過遞迴找到列表中的最大值。

程式結構

這段程式的目標是實現 findMax 函式，透過「分而治之」的方式，在不使用內建的 max 函式下找出列表 d 中的最大值。

def findMax(d):
    if len(d) == 1:
        return d[0]  # 返回單一元素，而非列表
    
    m = len(d) // 2
    lMax = findMax(d[:m])
    rMax = findMax(d[m:])
    
    if lMax > rMax:
        return lMax
    else:
        return rMax

# 測試
d = [1, 3, 5, 7, 8, 6, 4, 2, 21, 13, 15, 17, 18, 16, 14, 12]
print(findMax(d))  # 預期輸出: 21

程式詳解

1. 基礎情況（遞迴的終止條件）

   if len(d) == 1:
       return d[0]
   

   當 d 的長度為 1 時，說明這個子列表已經被分割到最小了（只有一個元素），這時直接返回這個元素即可。這一行是遞迴的「終止條件」，避免遞迴無限進行。

2. 分割列表

   m = len(d) // 2
   

   這行將列表 d 的長度除以 2，並取整數部分來得到中間索引 m。接下來，d 會被分成兩個子列表：

   • d[:m]：包含 d 的前半部分。
   • d[m:]：包含 d 的後半部分。

3. 遞迴呼叫 findMax 函式

   lMax = findMax(d[:m])
   rMax = findMax(d[m:])
   

   程式分別對 d 的前半部分和後半部分再次遞迴呼叫 findMax。每次呼叫 findMax 都會進一步將列表分成更小的部分，直到每部分只剩一個元素。lMax 和 rMax 分別保存前半部分和後半部分的最大值。

4. 比較左右部分的最大值

   if lMax > rMax:
       return lMax
   else:
       return rMax
   

   程式比較 lMax 和 rMax，返回其中較大的值。這一步驟會逐層向上返回每個分支中的最大值，直到得到整個列表的最大值。

遞迴過程示例

以 d = [1, 3, 5, 7, 8, 6, 4, 2, 21, 13, 15, 17, 18, 16, 14, 12] 為例，這個列表經過遞迴分割及比較的過程如下：

1. 列表被分割成 [1, 3, 5, 7, 8, 6, 4, 2] 和 [21, 13, 15, 17, 18, 16, 14, 12]。
2. 對於 [1, 3, 5, 7, 8, 6, 4, 2]，繼續分割成 [1, 3, 5, 7] 和 [8, 6, 4, 2]，如此重複直到每個子列表僅含一個元素。
3. 分割過程結束後，開始向上比較每一層中的最大值：
   • 例如，在 [1, 3, 5, 7] 這一層中，找到的最大值是 7；在 [8, 6, 4, 2] 這一層中，找到的最大值是 8。
   • 接著在更高一層中比較 7 和 8，得到 8。
4. 最後，將左右兩半的最大值 8 和 21 比較，最終返回最大值 21。

執行結果

最終輸出為：

21

這個 findMax 函式使用了「分而治之」的遞迴方法，通過逐層分割並比較左右子列表中的最大值，最終得到整個列表的最大值。