互质整数判断递归函数的实现正确性校验与优化咨询

从数论的严格定义出发，最大公约数（gcd）是两个整数公共正约数中的最大值，因此gcd的取值永远为正整数，不存在gcd=-1的合法定义。
你在递归计算过程中遇到的带负号的结果，本质是辗转相除时保留了原数的符号，并非真正的gcd值。我们判断互质的核心依据是“两数的最大正公约数是否为1”，因此只要计算过程中得到的公共约数绝对值为1，无论带不带负号，都与gcd=1的数学意义完全等价，即属于互质场景。

这段递归代码存在一个核心逻辑漏洞，会导致多数边界测试用例返回错误结果：

• 逻辑运算符误用导致条件永真：你编写的(b != 1 || b != -1)恒为真。因为一个整数不可能同时等于1和-1，无论b取何值，“b不等于1 或者 b不等于-1”的判断永远成立。
  这个问题直接导致：只要满足a%b ==0，不管b是1、-1还是其他整数，都会触发第一个分支返回0，后续判断“b为±1则返回1”的分支永远无法执行。
  典型错误场景举例：
• 传入a=5、b=1：按规则应返回1（两数互质），但代码会因a%b==0触发永真条件，错误返回0
• 传入a=-3、b=-1：按规则应返回1（两数互质），代码同样会错误返回0
• 传入a=6、b=-2：按规则应返回0（两数不互质），这个场景下结果正确，但属于巧合，并非逻辑正确。
  除此之外，代码的分支冗余度较高，两个判断a%b==0的分支可以完全合并，不需要分开编写返回逻辑。

基于gcd的数学性质（gcd(a,b) = gcd(|a|, |b|)，辗转相除的递归定义为gcd(a,0)=a、gcd(a,b)=gcd(b, a mod b)），可以编写逻辑无漏洞、可读性更强的实现：

// 需引入<stdlib.h>头文件以调用abs取绝对值函数
int relatively_prime(int a, int b){
    // 统一将输入转为绝对值，消除符号带来的判断复杂度
    a = abs(a);
    b = abs(b);
    
    // 递归终止：当b为0时，当前层级的a就是最终gcd值
    if (b == 0) {
        // 互质判定标准为最终gcd等于1，C语言中布尔判断直接返回1/0，完全符合需求
        return a == 1;
    }
    // 套用标准辗转相除逻辑递归
    return relatively_prime(b, a % b);
}

该优化版本的优势：

• 完全遵循gcd的数学定义，从根源上避免逻辑判断错误
• 提前统一数值符号后，后续不需要反复判断正负，代码结构简洁
• 覆盖全边界场景：支持任意顺序传入的正负整数、输入为0的特殊情况（例如a=0、b=1时返回1，a=0、b=2时返回0），完全满足需求。

针对执行效率做进一步调整时，可以参考这些思路：

• 移除冗余的abs调用：辗转相除的递归过程中，余数的符号不会影响最终gcd的绝对值判定，哪怕保留负号，递归也会正常终止，只需在最后判断gcd的绝对值是否为1即可
• 将递归实现替换为迭代实现，避免递归调用的栈开销，对大整数输入场景更友好
• 引入奇偶优化：对偶数的除以2取余逻辑单独处理，减少辗转相除的迭代次数

内容的提问来源于stack exchange，提问作者Kyle Angelo Gonzales