โปรแกรมคำนวณ gcd ของตัวเลขสองตัวแบบเรียกซ้ำใน Python

สมมติว่าเรามีตัวเลขสองตัว a และ b เราต้องหา GCD ของตัวเลขสองตัวนี้แบบเรียกซ้ำ ในการรับ GCD เราจะใช้อัลกอริทึมแบบยุคลิด

ดังนั้น หากอินพุตเป็น a =25 b =45 ผลลัพธ์จะเป็น 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน gcd() นี่จะใช้เวลา a, b
• ถ้า a เหมือนกับ b แล้ว
  • คืนสินค้า
• มิฉะนั้น เมื่อ
• ส่งคืน gcd(b, a)

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