Write a recursive JS program to find the greatest common divisor of two numbers.
Do you have no idea what the greatest common divisor is? Khan Academy video
This problem is really easy, if you understand the Math part of the problem very well.
If the lower number of the two can evenly divide into the larger number, then that is the greatest common divisor. Just return that number.
Else, what's the remainder from dividing the larger number by the smaller number?
Will that number divide evenly into the smaller number?
No?
Well, then what's the remainder from dividing the smaller number by that number?
Will that remainder divide equally into the smaller number? If yes, you've found your answer.
For example,
36, 96 - What's the greatest common divisor?
Step 1 - will 36 go into 96 evenly? No. Remainder = 24.
Step 2 - will 24 go into 36 evenly? No. Remainder = 12.
Step 3 - will 12 go into 36 evenly. Yes. Answer = 12.
12 is the greatest common divisor of 36 and 96.
Answer is in the comments.
var gcd = function(a, b) {
ReplyDeleteif ( b === 0) {
return a;
}
return gcd(b, a % b);
};