C遞迴程式求最大公因數

在數學中，最大公因數（Greatest Common Divisor, GCD）也稱為最大公約數，是指兩個或更多個整數共有最大的正因子。在電腦科學中，可以使用遞迴程式來找出兩個數字的GCD。

一個簡單的遞迴方法來計算GCD是歐幾里得算法（Euclidean algorithm），它的工作原理是：假設我們有兩個數字a和b，我們可以找到一個數字d使得a % b = d，其中%表示取餘數運算。如果d是0，那麼b就是a和b的GCD；如果不是0，我們可以重複這個過程來找到a和d的GCD，因為a和b的GCD等於b和a % b的GCD。

以下是一個使用Python編寫的遞迴程式來計算兩個數字的GCD的例子：

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

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

這個程式使用遞迴來呼叫自己，直到餘數為0，這時返回的數字就是GCD。當你輸入兩個數字並執行這個程式時，它會輸出這兩個數字的GCD。