โปรแกรมหาตัวหารร่วมมาก (GCD) แบบเรียกซ้ำใน Python

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

ตัวอย่างเช่น หาก 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