⬅ Greatest Common Divisor | A Helpful Line-by-Line Code Tutorial | Euclidean Algorithm

'''
{
    This is the recursive function that you call to process
    the numbers continuously. For simplicity, the numbers in this case
    are called a and b. You can call them whatever you want, obviously.
}
'''
def EuclideanGCD(a, b):

    '''
    {
        We take the absolutes of a and b, and pop them back
        into a and b. We do this because we want to deal with
        non-negative numbers.
    }
    '''
    a = abs(a)
    b = abs(b)

    '''
    {
        The three conditions below are the recursive base conditions,
        which are put to end the recursive loop and return the correct
        answer. 

        When a and b are both 0, it basically means that the two numbers,
        don't really have a GCD, which might happen.
    }
    '''
    if a == 0 and b == 0:
        return None
        
    '''
    {
        When a is zero, it means that the GCD is stored in b,
        as we saw in the example.
    }
    '''
    if a == 0 and not b == 0:
        return b

    '''
    {
        Vice versa, when b is zero, the GCD is stored in a.
    }
    '''
    if not a == 0 and b == 0:
        return a

    '''
    {
        The algorithm is applied FROM the larger number 
        TO the smaller number. Always subtract the smaller
        from the larger number. So, to check which number
        is larger, we use this little condition.
    }
    '''
    if a > b:

        '''
        {
            So, I know we said subtraction, but repeated subtraction
            without extra conditions can cause computational issue.
            Using the modulus operator makes our life much simpler.
            The modulus operator gets us the remainder 
            of the first number divided with the second number, which 
            essentially means subtracting the second number from the 
            first number until you cannot subtract further. Hence, your
            remainder.

            Once you get the remainder, you just pass it into the function.
        }
        '''
        return EuclideanGCD(a % b, b)
    
    else:

        '''
        {
            If the second number is bigger or equal to the first, this is what gets called.
        }
        '''
        return EuclideanGCD(b % a, a)


# Example Function Call
print(EuclideanGCD(49, 21))


# 49 , 21 => GCD is 7
# 28 , 21 => GCD is 7
# 7 , 21 => GCD is 7
# 7 , 14 => GCD is 7
# 7 , 7 => GCD is 7