Euclid is trying to find the largest common divisor of two numbers: a and b.
Example
Input:
let a = 3
let b = 9Expected value/output:
3
[collapse]
Hint
Recursively subtract the smaller number from the larger number until they become equal. Can you see why this works? Take a rectangle with lengths a and b. Whenever you do a subtraction from a and b, reduce the rectangle accordingly. Run this algorithm until you are left with a square (with length a = b).
[collapse]
Solution
let a = 3
let b = 9
func gcd(a:Int, b:Int) -> Int {
if a == b {
return a
}
else {
if a > b {
return gcd(a:a-b,b:b)
}
else {
return gcd(a:a,b:b-a)
}
}
}
print(gcd(a:a, b:b))[collapse]
