CODEWITHSUNDEEP
c
user2134555
user2134555

Reputation:

GCD of two numbers using Recursive function - What's Wrong?

I am new to Programming, just a student.

I have written a program to calculate the GCD of two numbers using recursive function, but it's giving the correct answer for some, while it gives wrong answer for a few others. Kindly help me in identifying the problem:

#include<stdio.h>
#include<conio.h>

int gcd(int,int,int)

int main(){
    int a,b,x,val;
    printf("Enter the first number: ");
    scanf("%d",&a);
    printf("Enter the second number: ");
    scanf("%d",&b);

    if(a>b)
        x=b;
    else
        x=a;

    val=gcd(a,b,x);
    printf("The GCD of the two numbers you entered is:%d",val);
    getch();
    return 0;
}

int gcd(int a,int b,int x){
    if(a%x==0){
        if (b%x==0)
            return x;
    }else
        return gcd(a,b,x-1);
}

For example, the program gives a wrong answer when first number = 69, second number = 65, whereas in some other cases it mysteriously gives the right answer.

Can someone help me out here?

Upvotes: 0

Views: 4745

Answers (4)

Musadul Islam
Musadul Islam

Reputation: 408

GCD of two numbers in C (the easiest way):

while(secNum != 0) {
    Temp = fNum % secNum;
    fNum = secNum;
    secNum = Temp;
}

printf("GCD of the given two numbers : %d",fNum);

Upvotes: 0

Dr. S
Dr. S

Reputation: 121

Example: consider the numbers a=100 and b=44. When it reaches x=25, which divides 100, but not 44, your code doesn't have a proper path to take.

You are not taking all the conditions (paths) into consideration.

int gcd(int a,int b,int x){
    if(a%x==0){
        if (b%x==0)
           return x;
        else
           // ERROR ERROR ERROR, 
           // if the code reaches here, then it neither calls gcd recursively, 
           // nor does it return anything valueable
    }else
        return gcd(a,b,x-1);
}

You should change the code as below.

int gcd(int a,int b,int x){        
    if(a%x==0)
        if (b%x==0)
        {
            return x;
        }
    return gcd(a,b,x-1);
}

OR 

int gcd(int a,int b,int x){
    if(a%x==0 && b%x==0) return x;        
    return gcd(a,b,x-1);
}

Upvotes: 0

trumpetlicks
trumpetlicks

Reputation: 7075

Try this:

int gcd(int a,int b,int x){
    if(a%x==0 && b%x==0) return x;        
    }else return gcd(a,b,x-1);
}

This catches both the modulus comparisons to 0 in one if statement, all conditions not falling within this get gcd calls.

Upvotes: 1

mathk
mathk

Reputation: 8143

Check your code path. Not all condition return an integer in the gcd function. Which compiler are you using? It should give you a warning or error.

Upvotes: 1

Related Questions