遞迴求最大公因數

遞歸求最大公因數可以使用輾轉相除法，也稱為歐幾里得算法。該算法基於以下原理：兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數。

具體步驟如下：

1. 定義兩個數 a 和 b，假設 a 小於等於 b。
2. 如果 b 等於 0，那麼最大公因數 gcd(a, b) 就等於 a。
3. 否則，把 a 除以 b，得到商 q 和餘數 r。遞歸地求 gcd(r, b)。
4. 將 r 和 q 作為新的 a 和 b，返回遞歸調用 gcd(r, q)。

使用 Python 代碼實現如下：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

在這個函式中，如果 b 為 0，說明已經找到了最大公因數，直接返回 a。否則，遞歸調用 gcd(b, a % b)，即取餘數作為新的 a，繼續求最大公因數。最終，當 b 變為 0 時，函式返回的就是最大公因數。