How does this method determine the greatest common divisor?

Question

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. Wikipedia

The following method is able to determine the GCD:

def gcd(a, b)
  if a % b == 0
    b
  else
    gcd(b, a % b)
  end
end
p gcd(4, 12)
#=> 4

How does this method work?

It makes sense if a % b == 0 then b is the biggest number that can go into both a and b.

But why call the same method again but switch around the args and take the modulus again?

I'm not grokking the reasoning behind the else part.

Edit:

Adding some puts statements to make it clearer:

def gcd(a, b)
  puts "Inside gcd, a: #{a}, b: #{b}, a \% b: #{a % b}"

  if a % b == 0
    puts "Inside if, a: #{a}, b: #{b}, a \% b: #{a % b}"
    b
  else
    puts "Inside else, a: #{a}, b: #{b}, a \% b: #{a % b}"
    gcd(b, a % b)
  end
end

p gcd(55, 105)

stdout:

Inside gcd, a: 55, b: 105, a % b: 55
Inside else, a: 55, b: 105, a % b: 55
Inside gcd, a: 105, b: 55, a % b: 50
Inside else, a: 105, b: 55, a % b: 50
Inside gcd, a: 55, b: 50, a % b: 5
Inside else, a: 55, b: 50, a % b: 5
Inside gcd, a: 50, b: 5, a % b: 0
Inside if, a: 50, b: 5, a % b: 0
5

Answer 1

This is what is called an Euclidean Algorithm.

In order to understand why you need to swap the numbers and make another recursion call you need to understand what is the actual maths behind it. Check this YouTube video out to see how Euclidean algorithm works. Otherwise, I wrote my explanation of the algorithm below.

---

Formal explanation of the Euclidean algorithm:

Input

• Two positive integers, a and b.

Output

• The greatest common divisor, gcd, of a and b.

Internal computation

• If a < b, exchange a and b.
• Divide a by b and get the remainder, r. If r = 0, report b as the GCD of a and b.
• Replace a by b and replace b by r. Return to the previous step.

---

For example:

gcd(40,7)

40 = 7(5) + 5 
 7 = 5(1) + 2
 5 = 2(2) + 1 <-- your gcd
 2 = 1(2) + 0

but, this implies that...

gcd(40,7) = gcd(7, gcd(40,7)) =
gcd(7, 5) = gcd(5, gcd(7, 5)) =
gcd(5, 2) = gcd(2, gcd(5, 2)) = 
gcd(2, 1) = 0

when gcd(a,b) = 0, b is equal to 1, so we return b

Now here is the important part! If we didn't swap numbers around we wouldn't be able to perform the necessary maths and, ultimately, track the location of b, which is our gcd.

---

So, the swap is essentially needed to keep the factors on the right. Try doing the maths without the swaps and you'll quickly see why it is important ;)

Hope this helps!