gcd

object GCD extends App{

  println("GCD is: " + gcd(args(0).toInt, args(1).toInt))

  //a and b positive according to how the problem was stated.
  //the solution provided is a direct translation of the hint included in the problem description.
  //the funzion gcd is tail recursive, as such, if the compiler supports tail recursive //optimization,the time and space
  //overhead due to the allocation of a new stack frame for each function's call is reduced/eliminated.
//Since the new b' parameter for each function invocation has a maximum value of b'=b-1, O(b) is an //upper limit on the number of function calls. It is demonstrable that the complexity of this algorithm //is O(log(n)) where n= a + b
  def gcd(a: Int, b: Int): Int =
    if(b == 0)
      a
    else
      gcd(b, a % b)
}