/ HackerRank Functional Challenges

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
Alex Netkachov

Alex Netkachov

Alex likes functional programming, algorithms and code reviews. Apart from programming, his favourites are walking with his family in the parks and national trails and reading books.

Read More

Why not to stay updated if the subject is interesting? Join Telegram channel Alex@Net or follow alex_at_net on Twitter. Or just, use the comments form below.