最大公因數遞迴

最大公因數（Greatest Common Divisor, GCD）的遞迴算法可以用來找出兩個正整數的最大公因數。這個算法是基於歐幾里得算法（Euclidean algorithm）的原理，該算法可以用來找出兩個數的GCD，而不需要將它們分解。

以下是最大公因數的遞迴算法的Python實現：

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

# 使用示例
a = int(input("請輸入第一個數："))
b = int(input("請輸入第二個數："))
print("最大公因數是：", gcd(a, b))

這個算法的工作原理是：如果b是0，那麼a就是a和b的最大公因數；如果不是，那麼繼續調用自身，用b和a % b來尋找a和b的最大公因數。

這個算法是遞迴的，因為它會一直調用自身，直到達到基線條件（base case），即b == 0。在這個時候，算法會返回a作為最大公因數。