GCD function - please help explain

[ssoffel]

Greatest common denominator function - can somebody please walk me through how this function works.



int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

[PrivateRyan]

https://msdn.microsoft.com/en-us/library/e4213hs1.aspx Here is the documentation for the operator.

b==0 is the conditional
a will be returned if b == 0 gcd(b, a % b) will be returned if b != 0

This recursive solution will return the greatest common divisor of the two original numbers by continually looking until the GCD is found.

Consider two numbers 50, 45
when you originally call the function:

answer = gcd(50, 45)
the function will show that b != 0, therefore instead of return the value of A, will return a recursive call to itself with the parameters gcd(45, 50%45)

50%45==5 so B will now equal 5 in this recursive call:
now when B != 0, the call will happen again for a third time, this time with gcd(5, 45%5)

45%5==0 so B will now equal 0

since this third call to the function will have B==0, the current value of A (which is 5), will be returned, rather than another recursive call. This value will be returned all the way back up to the first call, which will return it to whatever called it originally.

Some numbers have no common divisors greater than 1. Try something like 50,47 and see how it will return the value of 1!

[PrivateRyan]

I not sure I really represented the recursion well/clearly in my last post:

Using the example of A = 50, B = 45:

We start by calling the function originally in our code:

int gcdAnswer = gcd( 50, 45 )

Internally:

return 45 == 0 ? 50: gcd( 45 , 50%45 );

Since we know that 45 == 0 is false, the second expression will be returned from the function:gcd( 45 , 50%45 );

While the first call of the function is waiting for the value returned from its recursive call, the second function looks [abstractly] like this:

return /*(of 1st function call)*/ = gcd( 45 , 5 )

Inside the second call, we evaluate again
return 5 == 0 ? 45: gcd( 5, 45%5);

Since we know that 45 == 0 is false, the second expression will be returned from the function:gcd( 5, 45%5 );

While the first call of the function is waiting for the value returned from its recursive call, and the second function is waiting for the value returned from its function call, the third function looks [abstractly] something like this:

return /*(of 1st function call)*/ = return /*(of 2nd function call)*/ = gcd( 5, 0 )

Inside the third call, we evaluate again
return 0 == 0 ? 5: gcd( 0, 5%0);

Since we know that 0 == 0 is true, the firstexpression will be returned from the function:5

This is returned from the third recursive call to the second, which will then return it to the original function call. It looks [abstractly] like this:

return /*(of 1st function call)*/ = return /*(of 2nd function call)*/ = gcd( 5, 0 ) = 5

Note that this is a legal recursive process because it cannot be infinite.

[ssoffel]

Thanks a ton PrivateRyan, that was a great explanation! I understand it now