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

使用如下欧几里得算法求 $\gcd(105,45)$ 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）。

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))。

注意递归深度过大会导致栈溢出。递归必须包含终止条件，否则造成无限递归。

1. 🎯 考纲定位（考点定位）

【考点】递归｜欧几里得算法｜取模运算 GESP 五级（C++）递归模块核心题。命题人想卡住"不会写递归、只会背公式"的考生——GESP 五级明确把递归列为必会考点。

2. 🧠 解题思维（拆解与通法）

看到题先抓函数签名：gcd(a, b) 里 b != 0 时递归调用 gcd(b, a % b)。代入初始值：105÷45 余 15，所以第一层必跳成 gcd(45,15)；再看 45÷15 余 0，第二层跳成 gcd(15,0) 立刻返回 15。通法：递归题第一步永远是"看终止条件"，第二步"算一次参数变化"，切忌想一步跳到最终答案。