2024年5月2日发(作者：)

利用递归求两个数的最大公约数(利用辗转相

除法)

递归是一种在计算机编程中常用的技术，它允许一个函数在其自

身内部调用。递归求最大公约数也是一种常见的应用，特别是在利用

辗转相除法求解最大公约数时。

那么，什么是最大公约数呢？最大公约数是指两个或多个整数共

有的约数中最大的一个。而辗转相除法，即欧几里得算法，是求最大

公约数最常用的方法之一。

我们来看一个具体的例子，假设我们要求解两个数26和38的最

大公约数。首先，使用辗转相除法，我们将26除以38，得到余数12。

然后，我们将38除以12，得到余数2。再次，我们将12除以2，得到

余数0。当余数为零时，我们可以得出结论：最大公约数为2。

现在，我们将这个算法转化为递归函数的形式。我们定义一个函

数GCD(a,b)，其中a和b是待求解的两个数。如果b等于0，那么

GCD(a,b)等于a。否则，我们可以使用辗转相除法，将b作为新的a，

将a除以b的余数作为新的b，然后再次调用GCD函数。

这样，我们就可以写出求解最大公约数的递归函数：

```python

def GCD(a, b):

if b == 0:

return a

else:

return GCD(b, a % b)

```

接下来，我们可以通过调用这个函数来求解两个数的最大公约数。

例如，我们可以使用以下代码来求解26和38的最大公约数：

```python

result = GCD(26, 38)

print("26和38的最大公约数是：" + str(result))

```

输出结果为：26和38的最大公约数是：2

通过使用递归函数求解最大公约数，我们可以简洁地实现这个功

能，并且递归的思想也能够帮助我们更好地理解问题的解决过程。

在实际应用中，递归求解最大公约数不仅可以用于两个数的求解，

还可以扩展到多个数的求解。只需要将前两个数的最大公约数与第三

个数继续使用该递归函数求解，依次类推，直到计算到最后一个数。

总结起来，递归求解最大公约数的辗转相除法是一种高效且常用

的方法。通过了解这个算法和实现递归函数，我们不仅可以应对问题

的求解，还能够更好地理解递归思想在计算机编程中的应用。无论是

对于初学者还是专业人士来说，掌握递归求解最大公约数都是有指导

意义的。希望这篇文章能够帮助您更好地理解和应用递归求解最大公

约数的方法。