i don't understand why this works:

Code:
```int gcd(int a, int b)
{
if (b == 0)
return a;

return gcd(b, a % b);
}```
so if i have the fracking 10/4 and i call gcd(10,4) it would return 2? how the hell does it work? i really don't understand this....recursion-wah?

2. trace it out:
10 , 4 : 10 doesn't == 0 so we call again
4, 2 : 2 doesn't == 0 so we call again
2, 0 : 0 == 0 so we return 2

http://en.wikipedia.org/wiki/Euclidean_algorithm

3. yeah but i really don't understand HOW this works....i don't want to use this code if i don't understand it

4. would this bit of code work????
Code:
```int gcd (int numer, int denom)
{
if (denom == 0)
return numer;
return gcd(denom,numer % denom);
}

//
//
//
void reduceRational (int& numer, int& denom)
{
int factor = gcd (numer, denom);
numer /= factor;
denom /= factor;
}```
????

6. Originally Posted by Thantos

ya but it didn't make a whole lot of sense...what about my code?

7. Code:
```int gcd(int a, int b)
{```
Above is a function that takes two ints and gives them the name a and b

Code:
`    if (b == 0)`
This checks to see if b is equal to zero

Code:
`        return a;`
if b was equal to zero than return a
Code:
```    return gcd(b, a % b);
}```
if b does not equal zero then the function calls it self over and over again until b finally equals zero

so in the above is you called the function with the two ints 10 and 4 like so:
Code:
`gcd(10, 4);`
it will check to see if 4 is eqaul to zero and if it is not then it recalls the function using gcd(4, 10%4) which is really gcd(4, 2) (the % finds the remainder of the two numbers). So now we repeat the same proccess. 2 does not equal zero so we do gcd(2, 4%2) which is gcd(2,0). Now that b (0) is equal to zero we return a which is 2.

I am not sure how to explain it any easier.

8. the reduceRational function should work and the gcd should work. However the gcd parameter names are a little misleading since its only the numerator and the denomitor during the first call.

9. Originally Posted by Bitphire
Code:
```int gcd(int a, int b)
{```
Above is a function that takes two ints and gives them the name a and b

Code:
`    if (b == 0)`
This checks to see if b is equal to zero

Code:
`        return a;`
if b was equal to zero than return a
Code:
```    return gcd(b, a % b);
}```
if b does not equal zero then the function calls it self over and over again until b finally equals zero

so in the above is you called the function with the two ints 10 and 4 like so:
Code:
`gcd(10, 4);`
it will check to see if 4 is eqaul to zero and if it is not then it recalls the function using gcd(4, 10%4) which is really gcd(4, 2) (the % finds the remainder of the two numbers). So now we repeat the same proccess. 2 does not equal zero so we do gcd(2, 4%2) which is gcd(2,0). Now that b (0) is equal to zero we return a which is 2.

I am not sure how to explain it any easier.
i understand HOW the function actually goes about working

i don't understand WHY it works...WHY does calling itself over and over get you the gcd????????????\

what about my code? does that work?

10. Maybe think of it like this:
Code:
```int gcd1(int a, int b)
{
if (b == 0)
return a;
int x = gcd2(b, a % b);
return x;
}

int gcd2(int a, int b)
{
if (b == 0)
return a;
in y = gcd3(b, a % b);
return y;
}
int gcd3(int a, int b)
{
if (b == 0)
return a;

}```

11. try using the non recursive version and see if that helps you understand it better.

Note this is a very old algoirthm created by a freakin genius.
The proof for this may be outside of your comprehension.

12. Originally Posted by Thantos
try using the non recursive version and see if that helps you understand it better.

Note this is a very old algoirthm created by a freakin genius.
The proof for this may be outside of your comprehension.
ouch. try me.

13. i don't understand WHY it works...WHY does calling itself over and over get you the gcd
Then why did you post any code?

14. i dunno...i just wanna know how this works so when my teacher asks me im not all "well i got it off the internet"