C Recursive Function - GCD

Question

I've started learning C and programming in general relatively recently and we were told to make a program that finds the GCD and LCM of two numbers using recursion.

Now after some grinding I managed to get this together.

#include<stdio.h>

int gcd(int a,int b);

int main()
{
    int a,b,l,temp;
    printf("Enter two numbers :\n");
    scanf("%d%d",&a,&b);
    if(a<b)
    {
        temp=a;
        a=b;
        b=temp;
    }
    l=gcd(a,b);
    printf("GCD = %i\nLCM = %i",l,a*b/l);

    return 0;
}

int gcd(int a,int b)
{
    static int c;
    c=a%b;
    a=b;
    b=c;
    if(c!=0)
    {
        gcd(a,b);
    }
    else
        return a;
}

Now for some reason unknown to me, the function does not work without the "else". More specifically like this:

int gcd(int a,int b)
{
    static int c;
    c=a%b;
    a=b;
    b=c;
    if(c!=0)
    {
        gcd(a,b);
    }
        return a;
}

Although irrelevant to the assignment I feel like I should understand what the problem here is. As a novice I would appreciate any and all help.

I apologize in advance if the question is too stupid or the code too messy.

Why are the local variables in a recursive function `static`? They shouldn't be. — M Oehm, Dec 06 '16 at 11:07

score 0 · Answer 1 · answered Dec 06 '16 at 11:51

0

You asked about problems in your code. Here,

 static int c;

why is it static, Furthermore you don't need third variable to calculate gcd using recursion. And,

 gcd(a,b);

In what variable are you returning gcd. This doesn't make sense at all. It's not a void function, it's returning an int.

Now the correct method,

    if (b != 0)
     return gcd(b, a%b);
    else 
     return a;

That's it.

answered Dec 06 '16 at 11:51

Sanjay-sopho

429
3
15

That static is actually a leftover from something else I was trying previously. Didn't really think to remove it. Also, I was just using gcd(a,b) to go through the Euclidean algorithm. To just iterate through and assign the values and then stop the recursion when c (the remainder) became 0 and return a. Like I said, quite new to C and and that's even more so the case for recursion. – Punyesh Kumar Dec 06 '16 at 12:03

score 0 · Accepted Answer · edited May 23 '17 at 11:46

The problem is the recursive call:

int gcd(int a,int b)
{
    static int c;
    c=a%b;
    a=b;
    b=c;
    if(c!=0)
    {
        gcd(a,b); // The problem is here 
    }
    else
        return a;
}

You have done two different approaches:

In the case above you don't have a return statement if c!=0. Your function has to return int. Normally compilers give you a warning because you will return a kinda random number see here. So let's say it is luck that your function with else works.
Without the else statement you will always return a. You calculate gcd but you will never use the result so your result of the first call will always be the smaller number between the a and b of your main. You need to use the result of your recursive call to make the function working.

The right approach is to return your result of the recursive call like Sanjay-sopho already said:

return gcd(a,b);

Additionally it is bad coding style to use braces on the if and no braces on the else ;) Both cases are fine but keep it identical.

score 0 · Answer 3 · answered Dec 21 '22 at 08:47

0

in "C" make it like this, make a method to Take two number and find the gcd is name gcd

int gcd (int a,int b){ 
if (b==0)
return a;
else return gcd(b,a%b);

in the main i will colling by

printf("G.C.D OF %d AND %d is : %d ",a,b,gcd(a,b));

I use a recursiv functions

answered Dec 21 '22 at 08:47

Salha Yahya

1

1

Hi, thank you for contributing. Your code does not compile, a } is missing. Moreover, it would help to make correct indentiation and say a few words to the recursive approach. – maze Dec 22 '22 at 16:58

C Recursive Function - GCD

3 Answers3