HR F#: Computing the GCD

The greatest common divisor (or GCD) of two integers is the largest positive integer that divides two of these integers. The first of the Recursion problems on the Functional track at Hackerrank is computing the GCD using the Euclidean Algorithm.

In this algorythm the largest from the pair is replaced with largest minus smallest until both in the pair become equal.

Just like:

12 9
(12-9=3) 9
3 (9-3=6)
3 (6-3=3)
3 3 => GCD(12,9)=3

It is very easy to do in the loop, but the task is to do it recursively.

let rec gcd (x, y) =
  if x = y then x
  else if x > y then gcd(x-y, y)
  else gcd(x, y-x)

The calls to the gcd are optimised as they are at the ends of the expression tree. For more details on that see How to check that tail recursion calls are optimised.

The complete solution:

open System

let rec gcd (x, y) =
  if x = y then x
  else if x > y then gcd(x-y, y)
  else gcd(x, y-x)

[<EntryPoint>]
let main argv =
  let pair = Console.ReadLine().Split(' ')
             |> Array.map int
  printfn "%d" (gcd (pair.[0], pair.[1]))
  0 // return an integer exit code