ตัวหารร่วมที่ยิ่งใหญ่ที่สุด (GCD) ของตัวเลขสองตัวคือจำนวนที่มากที่สุดที่หารทั้งสองตัว
ตัวอย่างเช่น สมมติว่าเรามีตัวเลขสองตัวต่อไปนี้:45 และ 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
โปรแกรมหา GCD ของตัวเลขสองตัวโดยใช้การเรียกซ้ำมีดังต่อไปนี้
ตัวอย่าง
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} ผลลัพธ์
GCD of 63 and 42 is 21
ในโปรแกรมข้างต้น gcd() เป็นฟังก์ชันแบบเรียกซ้ำ มันมีพารามิเตอร์สองตัวคือ a และ b ถ้า a หรือ b เป็น 0 ฟังก์ชันจะคืนค่า 0 ถ้า a หรือ b เท่ากัน ฟังก์ชันจะคืนค่า a ถ้า a มากกว่า b ฟังก์ชันจะเรียกตัวเองซ้ำด้วยค่า a-b และ b ถ้า b มากกว่า a ฟังก์ชันจะเรียกตัวเองซ้ำด้วยค่า a และ b-a
สิ่งนี้แสดงให้เห็นโดยข้อมูลโค้ดต่อไปนี้
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
} อีกวิธีในการค้นหา GCD ของตัวเลขสองตัวโดยใช้การเรียกซ้ำมีดังนี้
ตัวอย่าง
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} ผลลัพธ์
GCD of 63 and 42 is 21
ในโปรแกรมข้างต้น gcd() เป็นฟังก์ชันแบบเรียกซ้ำ มันมีพารามิเตอร์สองตัวคือ a และ b ถ้า b มากกว่า 0 แล้ว a จะถูกส่งกลับไปยังฟังก์ชัน main() มิฉะนั้น ฟังก์ชัน gcd() จะเรียกตัวเองซ้ำด้วยค่า b และ a%b
ซึ่งแสดงให้เห็นโดยใช้ข้อมูลโค้ดต่อไปนี้
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
} 