• Advertisement
Sign in to follow this  

Recursion in C Programming: Confusion Begins

This topic is 1420 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, 

 

So I was working on a HW assignment in my C programming class, and we are learning about recursion. I guess the idea itself is pretty self explanatory, a function calling itself, but how it works is where I get lost! I got the assignment to work, but I'm not sure why what I coded worked. How does the function know what to return when there's 2 numbers inputted? It's just a function with 2 parameters and no variable changing so how does x and y get altered? I understood my previous assignment where we used recursion to return x to the nth power, but this one is a little less concrete with me.

 

Could anyone help me understand this a little more? Any help is greatly appreciated!

#include <stdio.h>

int gcd(int x, int y)
{
    // base case
    if(y == 0)
        return x;
    return gcd(y, x % y);
}

int main(int argc, const char * argv[])
{
    int x = 54;
    int y = 24;
    
    printf("GCD of %i and %i is %i\n", x, y, gcd(x,y));
    
    return 0;
}

Share this post


Link to post
Share on other sites
Advertisement

The first time you call gcd, x=54 and y=24. The y==0 test fails because y is 24, so gcd is called again with x=54 x=24 and y= (54%24) = 6. The second call to gcd knows nothing about the x and y in the first call, so all it sees are 54 24 and 6. Here, y still is not equal to 0, so gcd is called again with x=54 x=6 and y = 54 24%6 = 0. On the third call, y==0 is true, so the function returns 54 6. Control returns back to the second call, which directly returns the result of the third call (54). Control returns to the first call, which directly returns the result of the second call. Therefore, printf prints "The gcd of 54 and 24 is 54 6."

EDIT: To the OP: I hope I didn't add too much to your confusion! I saw the line gcd(y, x%y) as gcd(x, x%y). Had I considered the meaning of gcd, I might have caught the error. Though the numbers were wrong, the rest of the post holds true.

No matter how many function arguments you have, recursive calls continue until the base condition is met (i.e. when you tell it to). If you did not include the test for y==0 in the function, you would have a case of infinite recursion. Each call has its own copies of the parameters and cannot see the values in the previous calls. When the base condition is met, the function returns all the way back up the call stack. Mechanically, it's the same as a normal function call process. a() calls b() calls c() calls d(), and when d finishes, control returns back up the callstack to a(). The only difference with recursive functions is that it's one function calling itself.

Edited by Aldacron

Share this post


Link to post
Share on other sites

Therefore, printf prints "The gcd of 54 and 24 is 54."


If that's what it prints, I don't think that counts as working.

I see this chain of events:

gcd(54, 24)
gcd(24, 6)
gcd(6, 0)

It's just a function with 2 parameters and no variable changing so how does x and y get altered?


No variables changing, really?

(x, y) goes in the first time. (y, x%y) goes in the second time. Those are two variables that change right there.

Share this post


Link to post
Share on other sites

This video helped when I first started using recursion. Explains how recursion works really well.

I think you should take a look. 

   smile.png

 

 

(Don't worry cause its written in Java. It does not affect you from understanding.)

Edited by shadowstep00

Share this post


Link to post
Share on other sites


If that's what it prints, I don't think that counts as working.



Indeed. I didn't pay close enough attention. Sorry for the noise.

Share this post


Link to post
Share on other sites

+1 to what frob said, and as a side note, are you not looking for the Greatest Common Factor(or GCF rather than GCD)?

 

edit: I see that GCD and GCF as well as HCF are all used to describe what I've always known to be the greatest common factor of a set of numbers.

Edited by Burnt_Fyr

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement