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;
}

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.

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.

As this is homework, I strongly recommend asking your teacher about it.

1. Your teacher is being paid to help you understand it. If they don't know where you are struggling they won't be able to help you.

2. If you come to class without asking questions yet turning in functional programs, the teacher will assume the teaching methods are working when they are not.

3. Your teacher and your classmates might be watching as they search the web. Some schools have restrictive policies about asking for homework help on public forums.

4. When a student goes to the teacher for help, the teacher will know the student is working and wants to learn. This will have an impact on how the teacher works with you in the future; talking with your teachers means a better relationship (they can work with you better and will help you), a better educational experience (you learn more) and also usually a better grade (better prospects, more scholarship/grant/funding options) and otherwise makes your school life better.

Talk to the teacher, it just works out better for everyone.

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

I think you should take a look.

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

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.

+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.