C最大公因數遞迴

最大公因數（Greatest Common Divisor, GCD）的遞迴算法可以用來計算兩個數字的最大公因數。一個常用的遞迴算法是歐幾里得算法（Euclidean algorithm），它通過不斷地將較大的數字除以較小的數字，直到得到兩個數字互質為止。

這裡是一個簡單的歐幾里得算法的遞迴實現：

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

# 使用例子
a = int(input("請輸入第一個數字："))
b = int(input("請輸入第二個數字："))
print(f"{a} 和 {b} 的最大公因數是：{gcd(a, b)}")

這個算法的工作原理是：

1. 如果第二個數字 b 為 0，那麼第一個數字 a 就是它們的 GCD，因為 a 能被 a 整除，但不能被 b 整除。
2. 如果 b 不為 0，那麼我們繼續調用 gcd(b, a % b)，即計算 a 和 b 的 GCD 等於 b 和 a 除以 b 的餘數的 GCD。

這個算法是遞迴的，因為它會一直調用自己，直到達到 base case（即 b 為 0）。

請注意，這個算法假設 a ≥ b，如果 a 小於 b，你可能需要交換 a 和 b 的值，或者在調用 gcd 時交換參數的順序。

在實際應用中，為了避免遞迴調用的開銷，通常會使用非遞迴的疊代版本，因為它們通常效率更高。但是，遞迴版本有助於理解算法的邏輯，並且在某些情況下可能更易於閱讀和理解。