在Python中递归计算两个数的最大公约数的程序

假设我们有两个数字a和b。我们要以递归的方式查找这两个数字的最大公约数。要获取最大公约数，我们将使用欧几里得算法。

所以，如果输入是a = 25，b = 45，那么输出将是5。

为了解决这个问题，我们将遵循以下步骤−

• 定义一个名为gcd()的函数。这将使用a、b
• 如果a与b相同，则
  • 返回a
• 否则，当a < b时，
  • 返回gcd(b, a)
• 否则，
  • 返回gcd(b, a-b)

示例

让我们看看以下实现，以更好地理解−

def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a-b)

a = 25
b = 45
print(gcd(a, b))

输入

25, 45

输出

5