最大公因數遞迴c

最大公因數（Greatest Common Divisor, GCD）的遞迴算法可以用來找出兩個整數的最大公因數。一個簡單的遞迴算法是歐幾里得算法（Euclidean algorithm）的遞迴版本。

假設我們有兩個整數 a 和 b，我們想要找到它們的最大公因數。歐幾里得算法的基本思想是，a 和 b 的最大公因數等於 b 和 a 除以 b 的餘數 r 的最大公因數。

遞迴算法如下：

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

這個算法的工作原理是：

1. 如果 b 為 0，那麼 a 就是 a 和 b 的最大公因數，因為 a 能被 a 整除，但不能被 b 整除。
2. 如果 b 不是 0，那麼 a 除以 b 的餘數 r 是 a % b。根據歐幾里得算法，a 和 b 的最大公因數等於 b 和 r 的最大公因數。

因此，我們遞迴地應用這個算法，直到 b 為 0，這時我們返回 a。

請注意，這個算法假設 a >= b，因為 gcd(a, b) 相當於 gcd(b, a % b)，所以 a 總是被用來做除法。如果 a < b，那麼 gcd(a, b) 應該等於 gcd(b, a)。

在實際應用中，通常會使用非遞迴版本或者使用優化的遞迴版本，例如使用記憶化（memoization）來避免重複計算。