如何使用递归实现并打印两个数的最大公约数（GCD）？

问题描述 #

我正尝试编写递归代码计算两个数的最大公约数（GCD），目前能打印出所有公约数，但无法正确输出GCD。

能打印所有公约数的代码如下：

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2)? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           printf("%d ", x);
        }
        gcd(num1, num2, i + 1);
    }
    
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

尝试修改代码打印GCD时，得到随机输出（大概率是未初始化的内存垃圾值），当前代码如下：

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2)? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           
        }
        gcd(num1, num2, i + 1);
    }
   printf("%d ", x);
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

错误原因 #

1. 变量未初始化：当i不是两个数的公约数时，x没有被赋值，此时打印x会输出栈内存中的随机垃圾值。
2. 递归逻辑错误：当前代码从1开始向上遍历，递归返回时才打印每个栈帧的x，最终输出的是一系列值（包括未初始化的垃圾值），而非最大的那个公约数。

修正方案 #

方案一：从大到小遍历，找到即输出 #

从较小数开始向下遍历，第一个能同时整除两个数的就是最大公约数，找到后直接终止递归：

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    // 找到最大公约数，打印后终止递归
    if (num1 % i == 0 && num2 % i == 0) {
        printf("GCD: %d", i);
        return;
    }
    // 未找到则继续向下遍历
    gcd(num1, num2, i - 1);
}

int main() {
    int num1, num2;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    int small = (num1 < num2)? num1 : num2;
    gcd(num1, num2, small);
    return 0;
}

方案二：使用欧几里得算法递归实现（更高效） #

经典欧几里得算法通过取余操作快速缩小问题规模，递归逻辑简洁高效：

#include <stdio.h>

int gcd(int num1, int num2) {
    // 递归终止条件：当num2为0时，num1即为GCD
    if (num2 == 0) {
        return num1;
    }
    // 递归调用：将num2作为新的num1，num1%num2作为新的num2
    return gcd(num2, num1 % num2);
}

int main() {
    int num1, num2;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    printf("GCD: %d", gcd(num1, num2));
    return 0;
}

内容的提问来源于stack exchange，提问作者heisenberg