GESP 五级 · GESP 202606 C++ 五级 第 18 题

对任意正整数 a、b，以下两种写法的 gcd 函数返回值完全相同。

int gcd1(int a, int b) {
    return b ? gcd1(b, a % b) : a;
}
int gcd2(int a, int b) {
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

辗转相除法求最大公约数：gcd(a,b) = gcd(b, a%b)，当b=0时返回a。时间复杂度O(log min(a,b))。

辗转相除法中gcd(a,b)和gcd(b,a)结果相同。注意a和b的顺序不影响结果。

【考点】欧几里得算法｜递归与迭代等价性｜GESP五级算法模块

递归版 gcd1 直接照搬数学定义：当 b 非零时递归调用 gcd1(b, a % b)，否则返回 a。迭代版 gcd2 用循环模拟相同状态转移：t=b; b=a%b; a=t 每轮交换，直到 b=0 返回 a。两者本质都是欧几里得算法，数学上 gcd(a,b)=gcd(b,a%b)，终止条件相同，因此对任意正整数必然返回相同结果。

陷阱在于混淆实现方式与算法本质。gcd1 用递归、gcd2 用循环，但状态机完全一致；有人误以为递归版本栈溢出会出错，可题目明确"任意正整数"，且五级不考栈大小限制。若把 b? 改成 if(b) return gcd1(b,a%b); 或把 while(b) 改成 do-while(b=a%b,a=t);，逻辑仍等价，这正是命题人想检测的"是否理解算法而非死记代码"。

反命题视角：若把返回值改成 b? a : b 或加上 count++ 返回 (a,b,count)，答案会变为"不完全相同"；若把参数改成 int a,b; 且允许负数，则 a%b 在 C++ 中符号规则导致结果不同。刷到类似题先问：两种写法是否实现同一数学过程？是则选正确，否则找差异。