GCD function - please help explain
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);
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
https://msdn.microsoft.com/en-us/library/e4213hs1.aspx Here is the documentation for the operator.
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!
b==0 is the conditionala will be returned if b == 0
gcd(b, a % b) will be returned if b != 0This 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!
Last edited on
I not sure I really represented the recursion well/clearly in my last post:
Using the example of
We start by calling the function originally in our code:
Internally:
Since we know that
While the first call of the function is waiting for the value returned from its recursive call, the second function looks [abstractly] like this:
Inside the second call, we evaluate again
Since we know that
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:
Inside the third call, we evaluate again
Since we know that
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:
Note that this is a legal recursive process because it cannot be infinite.
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:5This 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 ) = 5Note that this is a legal recursive process because it cannot be infinite.
Topic archived. No new replies allowed.