## Extended Euclid algorithm for GCD in Python

Euclid’s recursive program based algorithm to compute GCD (Greatest Common Divisor) is very straightforward. If we want to compute gcd(a,b) and b=0, then return a, otherwise, recursively call the function using a=b and b=a mod b.