Python实现欧几里得算法求GCD时函数返回None问题咨询

• 核心原因是递归调用未显式返回结果：Python中所有函数如果没有执行到显式的return语句，默认返回值为None。
• gcd函数逻辑漏洞：当参数a != 0时，仅执行了gcd(rem(b, a), a)递归调用，未将递归的返回值作为当前函数的返回值返回。a != 0分支执行完递归后无任何return操作，因此函数默认返回None，这是最终返回结果为None的直接原因。
• 自定义rem函数也存在相同的递归返回缺失问题：if(a - b > b)分支中仅调用了rem(a-b, b)，未返回递归结果，最终返回的a-b并非预期的递归计算后余数。

# 修正余数计算函数
def rem(a, b):
    if(a - b > b):
        # 新增return返回递归结果
        return rem(a-b, b)
    return a-b

# 修正GCD计算函数
def gcd(a, b):
    if(a != 0):
        # 新增return返回递归调用结果
        return gcd(rem(b, a), a)
    else:
        return b

print(gcd(84, 126))
# 输出：42

Python原生支持取余运算符%，可以直接替代自定义rem函数简化实现：

def gcd(a, b):
    return gcd(b % a, a) if a != 0 else b

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