C Program to Find HCF or GCD of Two Numbers Using Recursion

HCF (Highest Common Factor) or GCD (Greatest Common Divisor) is the largest positive integer that divides two or more integers exactly without leaving a remainder. In C language, we can find the HCF or GCD of two numbers using recursion. This program uses the Euclidean Algorithm, in which a function repeatedly calls itself with the second number and the remainder of the division.

HCF (Highest Common Factor) या GCD (Greatest Common Divisor) वह सबसे बड़ी धनात्मक पूर्ण संख्या है, जो दो या दो से अधिक पूर्ण संख्याओं को बिना शेष छोड़े पूरी तरह विभाजित करती है। C लैंग्वेज में Recursion का उपयोग करके दो संख्याओं का HCF या GCD ज्ञात किया जा सकता है। इस प्रोग्राम में Euclidean Algorithm का उपयोग किया गया है, जिसमें फंक्शन दूसरी संख्या और भाग देने पर प्राप्त शेषफल के साथ स्वयं को बार-बार कॉल करता है।

Formula

The Euclidean Algorithm is based on the following mathematical rule:

Euclidean Algorithm निम्नलिखित गणितीय नियम पर आधारित है:

GCD(a,b)=GCD(b, a % b) 

The recursion stops when the second number becomes zero.

जब दूसरी संख्या शून्य हो जाती है, तब Recursive Calls रुक जाती हैं।

GCD(a,0)=|a| 

C Program Using Recursion

#include <stdio.h>
int hcf(int n1, int n2);
int main(void)
{
    int n1, n2;
    printf("Enter two integers: ");
    if (scanf("%d %d", &n1, &n2) != 2)
    {
        printf("Invalid input!\n");
        return 1;
    }
    if (n1 == 0 && n2 == 0)
    {
        printf("HCF of 0 and 0 is undefined.\n");
        return 1;
    }
    printf("HCF of %d and %d is %d.\n",
           n1, n2, hcf(n1, n2));
    return 0;
}
int hcf(int n1, int n2)
{
    if (n2 != 0)
        return hcf(n2, n1 % n2);
    else
        return (n1 < 0) ? -n1 : n1;
}

Output

Example 1:

Enter two integers: 12 18
HCF of 12 and 18 is 6.

Example 2:

Enter two integers: 24 36
HCF of 24 and 36 is 12.

Example 3:

Enter two integers: 15 25
HCF of 15 and 25 is 5.

Explanation of the Program

1. int hcf(int n1, int n2); is the function prototype that declares the recursive function.

   int hcf(int n1, int n2); फंक्शन प्रोटोटाइप है, जो Recursive Function को डिक्लेयर करता है।

2. The user enters two integers, which are stored in variables n1 and n2.

   यूजर दो पूर्णांक इनपुट करता है, जिन्हें n1 और n2 वेरिएबल में स्टोर किया जाता है।

3. The statement hcf(n1, n2) calls the recursive function to calculate the HCF.

   hcf(n1, n2) स्टेटमेंट HCF ज्ञात करने के लिए Recursive Function को कॉल करता है।

4. The condition if (n2 != 0) checks whether the second number is non-zero.

   if (n2 != 0) कंडीशन चेक करती है कि दूसरी संख्या शून्य नहीं है।

5. The statement return hcf(n2, n1 % n2); calls the same function again by passing the second number and the remainder.

   return hcf(n2, n1 % n2); स्टेटमेंट दूसरी संख्या और शेषफल को पास करके उसी फंक्शन को दोबारा कॉल करता है।

6. When n2 becomes zero, the recursive function returns the absolute value of n1. This is the HCF of the two numbers.

   जब n2 की वैल्यू शून्य हो जाती है, तब Recursive Function n1 का Absolute Value रिटर्न करता है। यही दोनों संख्याओं का HCF होता है।

Working of Recursive Function

Suppose the user enters 12 and 18. The recursive calls will work as follows:

मान लीजिए यूजर 12 और 18 इनपुट करता है। Recursive Calls निम्न प्रकार कार्य करेंगी:

hcf(12, 18)
= hcf(18, 12 % 18)
= hcf(18, 12)
= hcf(12, 18 % 12)
= hcf(12, 6)
= hcf(6, 12 % 6)
= hcf(6, 0)
= 6

Therefore, the HCF of 12 and 18 is 6.

इसलिए 12 और 18 का HCF 6 है।

Important Points

• HCF and GCD have the same meaning.

• This program uses the Euclidean Algorithm.

• The modulo operator % calculates the remainder.

• Recursion continues until the second number becomes zero.

• The time complexity of the Euclidean Algorithm is O(log(min(|a|, |b|))) for non-zero inputs.

• HCF और GCD का अर्थ एक ही होता है।

• इस प्रोग्राम में Euclidean Algorithm का उपयोग किया गया है।

• Modulo Operator % भाग देने पर प्राप्त शेषफल ज्ञात करता है।

• Recursive Calls तब तक चलती हैं, जब तक दूसरी संख्या शून्य नहीं हो जाती।

• Euclidean Algorithm की Time Complexity गैर-शून्य इनपुट के लिए O(log(min(|a|, |b|))) होती है।

HCF of 0 and 0 is undefined. This program handles that case separately. The absolute-value expression also handles negative inputs, except for the minimum representable int value, whose positive magnitude may not fit in int.

0 और 0 का HCF परिभाषित नहीं होता है। इस प्रोग्राम में इस स्थिति को अलग से हैंडल किया गया है। Absolute Value का उपयोग Negative Inputs को भी हैंडल करता है, लेकिन int की सबसे छोटी संभव वैल्यू के लिए उसका धनात्मक मान int में स्टोर नहीं हो सकता।