최대공약수 python

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다.

- a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a % b)

- 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n

def gcd(a, b):
    if b == 0: # 종료 조건
        return a
    return gcd(b, a % b)

print(gcd(1, 5)) # 1    
print(gcd(3, 6)) # 3   
print(gcd(69, 24)) # 3
print(gcd(81, 27)) # 27