Question:
Write a function gcd that takes two natural numbers and calculates their gcd.
Example: gcd (6, 15) should return 3.
Answer:
function gcd (a,b) {
if (b == 0) {
return a;
} else {
let remainder = a % b;
return gcd (b, remainder);
}
}
--- we need to understand 'euclid's alogrithm for gcd'
--- if we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
--- now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.
--- If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop
--- If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
> we declare a function 'gcd'
> it has 2 parameters: 'a' and 'b'
> if b is equal to 0, then a shall be the gcd (if you understand euclids alogorithm)
> if b is not equal to 0, then we calculate the remainder
> we create a variable 'remainder'
> we initialize it with a value / remainder that we get by dividing a by b; using modulo operator
> like this a % b; we use the modulo / remainder operator
> we then return the same function gcd with two parameters (b, remainder)
> this will again call the function gcd (a,b) but this time it will have a value of (a = b, b = remainder)
>>> we should try and understand this with an example to get clarity
>>> let us assume that we call the function gcd with some numbers
>>> like this: gcd (45, 99) ====>>> gcd (a,b)
>>> first it will check if b = 0; but b = 99
>>> so it will execute the code in the else block
>>> it will divide 45 / 99 using the remainder operator and store the output in the remainder variable
>>> the output shall be 45 % 99 = 45; so remainder = 45
>>> now we return the gcd function again with new values
>>> gcd (99, 45) ====>>> gcd (b = 99, remainder as calculated = 45)
>>> so our original parameters shall now be gcd(99, 45) ====>>> gcd(a = 99, b = 45)
>>> first it will check if b = 0; but b = 45
>>> so it will execute the code in the else block
>>> it will divide 99 / 45 using the remainder operator and store the output in the remainder variable
>>> the output shall be 99 % 45 = 9; so new remainder = 9
>>> now we return the gcd function again with new values
>>> gcd (45, 9) ====>>> gcd (b = 45, remainder as calculated = 9)
>>> so our original parameters shall now be gcd(45, 9) ====>>> gcd(a = 45, b = 9)
>>> again it will check if b = 0; but b = 9 >>> so it will execute the code in the else block
>>> it will divide 45 / 9 using the remainder operator and store the output in the remainder variable
>>> the output shall be 45 % 9 = 0; so remainder = 0
>>> now we return the gcd function again with new values
>>> gcd (9, 0) ====>>> gcd (b = 9, remainder as calculated = 0)
>>> so our original parameters shall now be gcd(9, 0) ====>>> gcd(a = 9, b = 0)
>>> again it will check if b = 0; and this time b = 0
>>> so it will return a which is 9
>>> and this is our GCD value for 2 numbers
