दो संख्याओं का महत्तम समापवर्तक (GCD) वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है।
उदाहरण के लिए: मान लें हमारे पास निम्नलिखित दो संख्याएँ हैं: 45 और 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 तो, 63 और 42 का GCD 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); } 
