Back to For Beginners

Recursion in C Programming: Confusion Begins

For Beginners

Started by NUCLEAR RABBIT March 03, 2014 03:55 AM

5 comments, last by Burnt_Fyr 10 years, 1 month ago

NUCLEAR RABBIT

318

Author

March 03, 2014 03:55 AM

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

Aldacron

4,545

March 03, 2014 04:11 AM

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.

--- Official D Blog | Learning D | The One With D | D Bits

Pink Horror

2,459

March 03, 2014 04:56 AM

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.

frob

46,221

March 03, 2014 06:23 AM

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.