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.
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., pair.)) 0 // return an integer exit code
Subscribe to @NET
Get the latest posts delivered right to your inbox