Can anyone explain how this code works? GCD, Recursive, Euclidian algorithm

Question

Can anyone help explain to me how this code works? I am trying to understand how recursion works and how to write it.

def gcdRecur(a, b):
'''
a, b: positive integers

returns: a positive integer, the greatest common divisor of a & b.
'''

if b == 0:
    return a
else:
    return gcdRecur(b,a % b)

obj = gcdRecur(9,12)
print (obj)

Answer 1

This is an implementation of the Euclidean algorithm.

The basic principle is that the greatest common factor of a and b (where b < a, which it will be after a step at most) is also the greatest common factor of b and the remainder when you divide a by b.

By repeatedly applying this step, you get down to a case where eventually the remainder is 0 (because it can be shown the remainder keeps getting smaller) and then the gcf is the other number. So in your example of 9 and 12 it goes to 12 and 9, then 9 and 3, then 3 and 0 and returns 3 which is right.

The way the function works is through recursion, which means it calls itself.

Answer 2

This is an implementation of Euclid's algorithm.

Briefly, % is the modulus operator, which returns the remainder of dividing the first operand by the second, so a % b divides 9 by 12, which is 0 with a remainder of 9. The recursion alternates the arguments, so the next operation will be 12 % 9 == 3, followed by 9 % 3 == 0, because 3 divides 9 with no remainder. 3 is divides 12 too, because it is the sum of itself and 9, a number it divides with no remainder.