两种递归求解两数GCD算法的时间复杂度差异及优化问题

两种实现代码展示 #

减法递归初版 #

你最初写出的实现（补全语法缺失的右括号后可运行）：

long long gcd(long long a, long long  b){
   if(!(a - b)) return a;
   return gcd(max(a, b) - min(a, b), min(a, b));
}

取模递归通用版 #

广泛使用的实现：

long long gcd(long long a, long long b){ 
  if(!b) return a;
  return gcd(b, a % b);
}

问题1：两段程序的时间复杂度差异 #

• 减法递归版的最坏时间复杂度为O(max(a,b))：当两个数差距极大时会出现线性退化，比如计算gcd(1, 1000000000)时，需要做近10亿次递归调用，不仅耗时极长，还很容易触发栈溢出。
• 取模递归版的最坏时间复杂度为O(log(min(a,b)))：也就是经典欧几里得算法的复杂度，每次取模操作会直接把大数折减到小于小数的量级，哪怕是斐波那契数对这种公认的最坏输入，递归层数也仅和输入数值的十进制位数正相关，不会出现线性增长的情况，刚才提到的gcd(1, 1e9)场景，取模版仅需2次递归就能返回结果。

问题2：减法递归版GCD的优化方向 #

这个减法实现的本质是古法更相减损术，原生版本效率低，可以从几个方向优化：

• 加入奇偶性剪枝：利用2的公因子性质，两数均为偶数时直接提出公因子2计数，一奇一偶时把偶数除以2（偶数不可能和奇数有公因子2），两奇相减得到偶数后也立刻做除2操作，大幅减少减法次数。
• 提前对齐大小关系：每次递归前先保证a >= b，省掉每次调用都执行max、min的额外计算开销。
• 合并连续减法操作：当a远大于b时，不用反复递归做a-b，直接计算a = a % b，一步跳到多次减法后的结果，这步优化完成后逻辑就和取模版欧几里得算法一致。
• 尾递归转迭代：把递归逻辑改成循环实现，彻底避免大输入下的栈溢出问题。

优化后的更相减损术参考代码：

long long gcd(long long a, long long b) {
    int cnt2 = 0;
    // 先把所有公因子2提出来
    while ((a & 1) == 0 && (b & 1) == 0) {
        a >>= 1;
        b >>= 1;
        cnt2++;
    }
    while (a != b) {
        if (a < b) swap(a, b);
        a -= b;
        // 差是偶数就一直除2
        while ((a & 1) == 0) a >>= 1;
    }
    return a << cnt2;
}

问题3：取模版GCD的效率优势论证 #

可以从三个实际维度验证：

• 操作步数压缩：取模a % b本质等价于连续做k次a = a - b直到a < b，一次取模操作直接替代了k次减法递归，当a是b的上万、上亿倍时，一步就能完成减法版需要成千上万次的操作。
• 无最坏退化场景：取模版的最坏输入是连续斐波那契数对，比如gcd(F(n), F(n-1))，此时递归层数为n，而斐波那契数是指数增长的，n和输入值的对数成正比，永远不会出现减法版那种线性复杂度的退化情况。
• 硬件适配优势：现代CPU对整数取模有专用硬件指令支持，哪怕单次取模的时钟周期比减法长，但是因为总递归/循环次数比减法版低几个数量级，实际运行速度有量级优势。

补充注意：取模版如果要兼容负数输入，需要先对两个入参取绝对值，否则会因为负数取模的规则问题返回错误结果。

内容的提问来源于stack exchange，提问作者Pranshu