GESP 五级 · GESP 202512 C++ 五级 第 5 题

下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

int gcd1(int a, int b) {
    return b == 0 ? a : gcd1(b, a % b);
}

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

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

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递归与迭代｜欧几里得算法｜栈空间消耗

🎯 考纲定位（考点定位）

GESP五级《算法基础》模块，递归与迭代的对比是核心考点。命题人专门设计这道题，就是要卡住那些只背"递归更优雅"却不懂"函数调用栈开销"的考生。大多数学生能判断A、B、C，唯独容易被D迷惑。