The greatest common divisor (GCD), also called greatest common factor (GCF) or highest common factor (HCF), of two integers is the largest number that divides both of them without leaving a remainder. Euclidean algorithm is used to compute the GCD of two integers by making use of recursion.
The following shows the recursive way (Euclidean algorithm) to calculate GCD, however it is possible to use iterative way to do so, and it will be discussed later in the advanced topic.

Time Complexity
Given two integers x and y, the Euclidean algorithm recursively does division between two integers, and it is similar to some bit operations, so the time complexity depends on the numbers of bits of x and y, and actually it is O((log x)(log y))

Pseudo Code

gcd( x, y )
      if x < 0 then
          return gcd( -x, y )
      else if y < 0 then
          return gcd( x, -y )
      else if y == 0 then
          return x
      else
          report gcd( y, x%y )