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

两块长方形土地的长宽分别为 $24$ 和 $36$ 米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长，则函数 gcd 调用顺序为（ ）。

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 五级「算法与数据结构」模块——五级明确要求掌握递归函数调用机制。命题人卡住的是「递归深度」与「返回值时机」的混淆点：很多考生以为递归一定会层层调用到底，却忽略了满足整除条件时函数会立即返回，因此误选多调用一层的选项。