# Ruby Coding Interview Question: Find the Greatest Common Divisor (GCD) of Two Numbers

# Solution

`def gcd(a, b)`

b == 0 ? a : gcd(b, a % b)

end

puts gcd(24, 36) #=> 12

Let’s break down the code and understand how it works:

- The
`gcd`

method takes two parameters,`a`

and`b`

, representing the two numbers for which you want to find the GCD. - In this implementation, the code uses a ternary operator
`b == 0 ? a : gcd(b, a % b)`

to determine the base case for the recursion. If`b`

is equal to 0, it means we have found the GCD, so the method simply returns`a`

. Otherwise, it makes a recursive call to`gcd`

with the arguments`b`

and`a % b`

. This step is equivalent to swapping the values of`a`

and`b`

in the iterative implementation. - The expression
`a % b`

calculates the remainder when`a`

is divided by`b`

. By repeatedly dividing the larger number by the smaller number and taking the remainder, we ensure that in each iteration,`a`

becomes the smaller number and`b`

becomes the remainder. - The recursive calls continue until
`b`

becomes 0, at which point the base case is triggered, and the GCD, which is stored in`a`

, is returned as the final result.

To test the code, you provided an example usage:

`puts gcd(24, 36) #=> 12`

- In this case, the GCD of 24 and 36 is calculated by calling the
`gcd`

method with the arguments 24 and 36. The output will be`12`

, which represent the greatest common divisor of the two numbers. - The recursive implementation offers a more concise way to write the Euclidean algorithm. However, keep in mind that it may not be suitable for very large numbers or deep recursion due to potential stack overflow.
- When you execute
`puts gcd(24, 36)`

, the`gcd`

method is called with the arguments 24 and 36. The recursive calls are made as follows:

`gcd(24, 36)`

`gcd(36, 24 % 36)`

, which becomes`gcd(36, 24)`

`gcd(24, 36 % 24)`

, which becomes`gcd(24, 12)`

`gcd(12, 24 % 12)`

, which becomes`gcd(12, 0)`

At this point, the base case is triggered since `b`

is now 0, and the GCD, which is stored in `a`

, is returned. The output of the program is `12`

…