GESP 五级 · GESP 五级样题（C++ 组） 第 11 题

下列代码中，函数 f 的作用是（ ）。

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

这题一眼就是欧几里得算法，核心就是看递归里参数怎么变：从(a,b)变成(b,a%b)，直到b为0返回a，这就是辗转相除求最大公约数的标准写法，直接选C。

很多学生一看到递归就慌，要么把a%b当成求最小公约数，要么被选项里的“质因子”“最小公倍数”带偏。其实辗转相除每一步都在缩小余数，最后剩下的那个非零数就是最大的公约数，跟质数没关系，跟最小公倍数更是两码事（最小公倍数要用a*b除以最大公约数，代码里完全没有乘积运算）。

【考点】递归｜欧几里得算法｜辗转相除法

1. 题目在考什么

这道题出自GESP五级《算法基础》模块，命题人想检验的是：考生能否透过递归的“外壳”看到内在的数学本质。代码里只有两行，但每一行都藏着经典算法的骨架。如果只背过“最大公约数用辗转相除”这个结论，却说不清为什么这段递归就是辗转相除，那遇到变式题（比如终止条件改成b==1）就会栽跟头。所以，解题的关键不是跑代码，而是把递归步骤和欧几里得算法的迭代步骤一一对应起来。