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

Gokul
4 min readJun 8

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:
  1. gcd(24, 36)
  2. gcd(36, 24 % 36), which becomes gcd(36, 24)
  3. gcd(24, 36 % 24), which becomes gcd(24, 12)
  4. 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

Gokul

Consultant | Freelancer | Ruby on Rails | ReactJS

Recommended from Medium

Lists

See more recommendations