GESP 五级 · GESP 202406 C++ 五级 第 6 题

欧几里得算法还可以写成如下形式：

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

下面有关说法，错误的是（ ）。

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

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

【考点】递归｜栈空间｜算法效率

🎯 考纲定位

GESP 五级 C++ 模块，考查递归实现与迭代实现的对比。命题人专挑"递归更优雅"的直觉——考生看到简洁的递归代码就默认效率高，忽略了函数调用开销。