Ruby Program to Find GCD Using Recursion

You can find the GCD of two numbers in Ruby using recursion with def gcd(a, b); b == 0 ? a : gcd(b, a % b); end which calls itself until the remainder is zero.

Examples

Inputgcd(48, 18)

Output6

Inputgcd(7, 5)

Output1

Inputgcd(0, 10)

Output10

How to Think About It

To find the GCD using recursion, check if the second number is zero. If yes, return the first number as the GCD. Otherwise, call the function again with the second number and the remainder of the first number divided by the second number. This repeats until the remainder is zero.

Algorithm

1

Take two numbers as input.

2

Check if the second number is zero.

3

If yes, return the first number as the GCD.

4

If no, call the function again with the second number and the remainder of the first number divided by the second number.

5

Repeat until the second number becomes zero.

Code

ruby

def gcd(a, b)
  return a if b == 0
  gcd(b, a % b)
end

puts gcd(48, 18)

Output

6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial call

gcd(48, 18) checks if 18 == 0 (false), so calls gcd(18, 48 % 18) which is gcd(18, 12)

2

Second call

gcd(18, 12) checks if 12 == 0 (false), so calls gcd(12, 18 % 12) which is gcd(12, 6)

3

Third call

gcd(12, 6) checks if 6 == 0 (false), so calls gcd(6, 12 % 6) which is gcd(6, 0)

4

Base case

gcd(6, 0) returns 6 because second number is zero

Call	a	b	a % b
1	48	18	12
2	18	12	6
3	12	6	0
4	6	0	-

Why This Works

Step 1: Check if second number is zero

The function stops when the second number is zero because the first number at that point is the GCD.

Step 2: Recursive call with remainder

Each recursive call reduces the problem by replacing the first number with the second, and the second with the remainder of the first divided by the second.

Step 3: Eventually reach base case

This process repeats until the remainder is zero, ensuring the GCD is found.

Alternative Approaches

Iterative approach

ruby

def gcd_iterative(a, b)
  while b != 0
    a, b = b, a % b
  end
  a
end

puts gcd_iterative(48, 18)

Uses a loop instead of recursion; easier to understand for some but less elegant.

Using Ruby's built-in method

ruby

puts 48.gcd(18)

Ruby has a built-in gcd method for integers, which is the simplest and most efficient.

Complexity: O(log(min(a, b))) time, O(log(min(a, b))) space

Time Complexity

Each recursive call reduces the problem size roughly by the remainder, which decreases quickly, leading to logarithmic time complexity.

Space Complexity

Recursive calls add to the call stack, so space complexity is proportional to the number of calls, which is logarithmic.

Which Approach is Fastest?

The built-in Ruby method is fastest and most optimized, followed by the iterative approach, then recursion due to call stack overhead.

Approach	Time	Space	Best For
Recursive	O(log(min(a,b)))	O(log(min(a,b)))	Learning recursion and elegant code
Iterative	O(log(min(a,b)))	O(1)	Performance and avoiding stack overflow
Built-in method	O(log(min(a,b)))	O(1)	Fastest and simplest for production