/* Functional Programming Example -- Greatest Common Divisor
   H. Conrad Cunningham, Professor
   Computer and Information Science
   University of Mississippi

   Developed for CSci 555, Functional Programming, Spring 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2016-02-10: Developed from 2015 Elixir version

I adapted this greatest common divisor (gcd) module from an Elixir
version, which as, in turn, adapted from a Lua version, which was, in
turn, adapted from the Scheme code in section 1.2.1 of Abelson and
Sussman's Structure and Interpretation of Computer Programs (SICP).

I have only tested this minimally.

Scala and functional programming highlights:
- States complexity measures

*/

object GCD {

  /* Function "gcd" computes the greatest common divisor of its two
     nonegative number arguments using Euclid's algorithm.  It is
     based on property: If r is the remainder of a divided by b, then
     the common divisors of a and b are precisely the same as the
     common divisors of b and r.
  
     Time complexity:  O(log max(a,b))
     Space complexity: O(1) with tail call optimization
  */

  def gcd(a: Int, b: Int): Int = b match {
    case 0 => a
    case n => gcd(b, a % b)   // tail recursion
  }

  // Should implement extensive tesing externally
  def main(args: Array[String]) {
    println("gcd(20,15) is " + gcd(20,15))
    println("gcd(15,20) is " + gcd(15,20))
    println("gcd(39,42) is " + gcd(39,42))
    println("gcd(13,19) is " + gcd(13,19))
  }

}