Python 循环与递归求最大公约数 (GCD) 详解

最大公约数 (GCD) 是指两个或多个整数中最大的公因数。本文将介绍使用 Python 语言计算两个数的 GCD 的两种方法：循环法和递归法。

循环法

以下是使用欧几里得算法（辗转相除法）计算两个数的最大公约数的 Python 代码：

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

在这个函数中，我们使用 while 循环，每次将 b 设为 a 除以 b 的余数，同时将 a 设为原来的 b，直到 b 为 0 为止。最后返回 a，即为两个数的最大公约数。

递归法

我们还可以使用递归来实现求最大公约数的功能，代码如下：

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

在这个函数中，我们首先判断 b 是否为 0，如果是，直接返回 a。否则，我们将 a 设为 b，将 b 设为 a 除以 b 的余数，然后递归调用 gcd 函数，直到 b 为 0 为止。最后返回 a，即为两个数的最大公约数。这种递归实现方式更加简洁，代码量也更少。

总结

本文介绍了使用 Python 语言计算两个数的最大公约数 (GCD) 的两种方法：循环法和递归法。两种方法都基于欧几里得算法，但实现方式有所不同。循环法更易于理解，而递归法则更加简洁。选择哪种方法取决于你的个人偏好和需求。