C 語言遞迴求最大公約數 (GCD) 完整指南

掌握三種遞迴實作最大公約數的方法：經典歐幾里得演算法 (模數)、減法遞迴、以及二進制 GCD 演算法，包含完整程式碼、複雜度分析與優化技巧。

最大公約數數學定義

兩個整數 a、b (不全為 0) 的最大公約數，記為 gcd(a, b)，是能同時整除 a 和 b 的最大正整數。

核心性質 (歐幾里得定理)

gcd(a, b) = gcd(b, a mod b)   (b ≠ 0)
gcd(a, 0) = |a|

方法一：歐幾里得演算法 (模數遞迴) - 推薦

演算法邏輯

• 若 b = 0，回傳 |a|
• 否則回傳 gcd(b, a % b)

完整程式碼

#include <stdio.h>
#include <stdlib.h>  // for abs()

// 遞迴實作：歐幾里得演算法
int gcd_euclidean(int a, int b) {
    // 處理負數：取絕對值
    a = abs(a);
    b = abs(b);
    
    if (b == 0) {
        return a;  // 基礎案例
    }
    return gcd_euclidean(b, a % b);  // 遞迴呼叫
}

// 主程式測試
int main() {
    int m, n;
    
    printf("請輸入兩個整數 (以空格分隔)：");
    if (scanf("%d %d", &m, &n) != 2) {
        printf("輸入格式錯誤\n");
        return 1;
    }
    
    int result = gcd_euclidean(m, n);
    printf("gcd(%d, %d) = %d\n", m, n, result);
    
    return 0;
}

執行範例

請輸入兩個整數 (以空格分隔)：48 18
gcd(48, 18) = 6

請輸入兩個整數 (以空格分隔)：-24 36
gcd(-24, 36) = 12

請輸入兩個整數 (以空格分隔)：17 5
gcd(17, 5) = 1

遞迴追蹤範例 (gcd(48, 18))

gcd(48, 18)
→ gcd(18, 48%18=12)
  → gcd(12, 18%12=6)
    → gcd(6, 12%6=0)
      → return 6
    → return 6
  → return 6
→ return 6

方法二：減法遞迴 (原始題目版本)

演算法邏輯

• 若 a = b，回傳 a
• 若 a > b，回傳 gcd(a-b, b)
• 若 a < b，回傳 gcd(a, b-a)

修正後完整程式碼

#include <stdio.h>
#include <stdlib.h>

int gcd_subtraction(int a, int b) {
    a = abs(a);
    b = abs(b);
    
    if (a == b) {
        return a;  // 基礎案例：相等時即為 GCD
    } else if (a > b) {
        return gcd_subtraction(a - b, b);  // 較大減較小
    } else {
        return gcd_subtraction(a, b - a);  // 較大減較小
    }
}

效能比較

方法三：二進制 GCD 演算法 (Stein 演算法) - 最快

演算法原理

• 利用位元運算取代除法/模數運算
• 適用於無硬體除法指令的處理器
• 現代 CPU 仍具優勢 (位元運算比除法快)

遞迴實作

int gcd_binary(int a, int b) {
    a = abs(a);
    b = abs(b);
    
    if (a == 0) return b;
    if (b == 0) return a;
    if (a == b) return a;
    
    // 都是偶數
    if ((a & 1) == 0 && (b & 1) == 0) {
        return gcd_binary(a >> 1, b >> 1) << 1;
    }
    // a 偶數，b 奇數
    else if ((a & 1) == 0) {
        return gcd_binary(a >> 1, b);
    }
    // a 奇數，b 偶數
    else if ((b & 1) == 0) {
        return gcd_binary(a, b >> 1);
    }
    // 都是奇數，減去較小者
    else if (a > b) {
        return gcd_binary((a - b) >> 1, b);
    }
    else {
        return gcd_binary((b - a) >> 1, a);
    }
}

迭代版本 (避免堆疊溢位)

int gcd_binary_iterative(int a, int b) {
    a = abs(a);
    b = abs(b);
    
    if (a == 0) return b;
    if (b == 0) return a;
    
    // 找出共同的 2 的因子
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    
    // 移除 a 中的 2 因子
    while ((a & 1) == 0) {
        a >>= 1;
    }
    
    do {
        // 移除 b 中的 2 因子
        while ((b & 1) == 0) {
            b >>= 1;
        }
        
        // 現在 a 和 b 都是奇數
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        b = b - a;  // b >= a，所以 b-a >= 0
    } while (b != 0);
    
    return a << shift;
}

迭代版歐幾里得演算法 (生產環境推薦)

int gcd_iterative(int a, int b) {
    a = abs(a);
    b = abs(b);
    
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

遞迴 vs 迭代比較

擴展：多個數的 GCD

int gcd_array(int arr[], int n) {
    if (n <= 0) return 0;
    int result = abs(arr[0]);
    for (int i = 1; i < n; i++) {
        result = gcd_iterative(result, arr[i]);
        if (result == 1) break;  // 提前結束：互質
    }
    return result;
}

// 使用範例
int numbers[] = {48, 18, 24, 36};
int gcd_all = gcd_array(numbers, 4);  // 結果：6

最小公倍數 (LCM) 關聯計算

// LCM(a, b) = |a * b| / GCD(a, b)
// 注意溢位：使用 long long 或先除後乘
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return llabs(a) / gcd_iterative(a, b) * llabs(b);
}

完整測試程式

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int gcd_euclidean(int a, int b);
int gcd_subtraction(int a, int b);
int gcd_binary(int a, int b);
int gcd_iterative(int a, int b);

void test_performance() {
    struct timespec start, end;
    long long iterations = 1000000;
    int a = 12345678, b = 87654321;
    
    printf("效能測試 (%lld 次迭代)：\n", iterations);
    
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (long long i = 0; i < iterations; i++) gcd_euclidean(a, b);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("歐幾里得遞迴：%.3f ms\n", 
           (end.tv_sec - start.tv_sec) * 1000.0 + (end.tv_nsec - start.tv_nsec) / 1e6);
    
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (long long i = 0; i < iterations; i++) gcd_iterative(a, b);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("歐幾里得迭代：%.3f ms\n", 
           (end.tv_sec - start.tv_sec) * 1000.0 + (end.tv_nsec - start.tv_nsec) / 1e6);
    
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (long long i = 0; i < iterations; i++) gcd_binary(a, b);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("二進制遞迴：%.3f ms\n", 
           (end.tv_sec - start.tv_sec) * 1000.0 + (end.tv_nsec - start.tv_nsec) / 1e6);
}

int main() {
    // 功能測試
    int test_cases[][2] = {
        {48, 18}, {100, 25}, {17, 5}, {0, 5}, {-24, 36}, {1000000, 1}
    };
    
    printf("功能驗證：\n");
    for (int i = 0; i < 6; i++) {
        int a = test_cases[i][0], b = test_cases[i][1];
        printf("gcd(%d, %d) = %d (迭代), %d (二進制)\n", 
               a, b, gcd_iterative(a, b), gcd_binary(a, b));
    }
    
    printf("\n");
    test_performance();
    return 0;
}

總結建議

1. 學習/教學：使用歐幾里得遞迴版，邏輯清晰、易理解
2. 生產環境：使用迭代版歐幾里得，無堆疊風險、效能最佳
3. 嵌入式/無除法指令：使用二進制 GCD (Stein)
4. 避免使用：減法遞迴 (效能極差、易堆疊溢位)
5. 處理負數：一律先取絕對值 abs()
6. 處理零值：gcd(a, 0) = |a|，gcd(0, 0) 通常定義為 0