GESP 五级 · GESP 202503 C++ 五级 第 4 题

用以下辗转相除法（欧几里得算法）求 gcd(84, 60) 的步骤中，第二步计算的数是（ ）。

int gcd(int a, int b) {
    int big = a > b ? a : b;
    int small = a < b ? a : b;
    if (big % small == 0) {
        return small;
    }
    return gcd(small, big % small);
}

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

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

【考点】递归｜辗转相除法

1. 🎯 考纲定位

GESP 五级 C++ 算法模块第 3 单元「递归」，必考题型。命题人专盯递归调用链——考生要么只背"辗转相除求最大公约数"的结论，要么搞不清函数递归执行的顺序，导致把第三步甚至第四步的数当成第二步。