Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Recursion in C Programming: Confusion Begins


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 NUCLEAR RABBIT   Members   -  Reputation: 275

Like
0Likes
Like

Posted 02 March 2014 - 09:55 PM

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

------------------------My band: RISE OVER ME!

Sponsor:

#2 Aldacron   GDNet+   -  Reputation: 3396

Like
-1Likes
Like

Posted 02 March 2014 - 10:11 PM

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, 03 March 2014 - 08:45 AM.


#3 Pink Horror   Members   -  Reputation: 1540

Like
1Likes
Like

Posted 02 March 2014 - 10:56 PM

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.

#4 frob   Moderators   -  Reputation: 26739

Like
12Likes
Like

Posted 03 March 2014 - 12: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.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#5 shadowstep00   Members   -  Reputation: 615

Like
1Likes
Like

Posted 03 March 2014 - 04:28 AM

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

I think you should take a look. 

http://www.youtube.com/watch?v=ozmE8G6YKww   smile.png

 

 

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


Edited by shadowstep00, 03 March 2014 - 04:30 AM.

Failure is not an option...


#6 Aldacron   GDNet+   -  Reputation: 3396

Like
0Likes
Like

Posted 03 March 2014 - 08:33 AM


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.

#7 Burnt_Fyr   Members   -  Reputation: 1331

Like
0Likes
Like

Posted 03 March 2014 - 01:44 PM

+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, 03 March 2014 - 01:52 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS