用 Python 在递归中计算两个数的 GCD 的程序

假设我们有两个数字 a 和 b。我们必须以递归的方式找到这两个数的 GCD。为了得到 GCD，我们将使用欧几里得算法。

因此，如果输入是 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

更新于： 2021 年 10 月 12 日

7K+ 浏览量

开始您的职业生涯

完成课程获取认证

开始学习
广告