# How to find GCD of two numbers ?

[Question]: There is two number find the Greatest common divisor example 3,6 – GCD is 3
Better Approach using Euclidean algorithm Here we used recursion which swap the params with second argument as modulo divisor.
The space complexity is O(log(min(a,b))) as well, due to the recursive calls being placed on the call stack. Each recursive call consumes memory space on the stack, but since the depth of recursion is at most O(log(min(a,b))), the space complexity is also O(log(min(a,b))).

``````Method #1 Using Recursion
// TC: O(log(min(a,b)))
// SC: O(log(min(a,b)))

func gcd(_ a: Int, _ b: Int) -> Int {
if (b == 0) { return a }
return gcd(b, a % b)
}
print("GCD is-->", gcd(3, 6))//prints 3``````
``````Method #2 Using Loop
// TC: O(log(min(a,b)))
// SC: O(1)
func gcd(_ a: Int, _ b: Int) -> Int {
var a = a
var b = b
while b != 0 {
let temp = a
a = b
b = temp % b
}
return a
}``````

If we do dry run for above code snippet
Case 1: For 3,11 a & b values in loop will be —
3 ,11
11, 3
3, 2
2, 1
1, 0 Here “b” is zero Hence returns 1 which is “a”
————————————————————————————————————————————————————————
Case 2: For 3,6 a & b values in loop will be —
3,6
6,3
3,0 Here “b” is zero Hence returns 3 which is “a”