• Create Account

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

6 replies to this topic

### #1NUCLEAR RABBIT  Members

318
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!

### #2Aldacron  GDNet+

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

### #3Pink Horror  Members

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

### #4frob  Moderators

41269
Like
12Likes
Like

Posted 03 March 2014 - 12:23 AM

POPULAR

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 occasionally write about assorted stuff.

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

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

### #6Aldacron  GDNet+

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

### #7Burnt_Fyr  Members

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