Chương trình tính toán gcd của hai số một cách đệ quy bằng Python

Giả sử chúng ta có hai số a và b. Chúng ta phải tìm GCD của hai số này theo cách đệ quy. Để có được GCD, chúng tôi sẽ sử dụng thuật toán Euclide.

Vì vậy, nếu đầu vào là a =25 b =45, thì đầu ra sẽ là 5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm gcd (). Điều này sẽ mất a, b
• nếu a giống với b, thì
  • trả về một
• ngược lại khi a
• trả về gcd (b, a)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

25, 45

Đầu ra

5