유클리드 호제법(최대공약수 재귀로 구하기)

두 자연수의 최대공약수를 구하는 대표적 알고리즘.

 

특징: 자연수 A,B에서 A%B=R일 때

A,B의 최대공약수 == B,R의 최대공약수

 

예를 들어 A: 192와 B: 162의 최대공약수를 구할 때(GCD(192,162))

Level	A	B
1	192	162
2	162	30
3	30	12
4	12	6

즉, 192와162의 최대공약수는 12와 6의 최대공약수(즉, 6)과 동일하다. 

따라서 재귀함수를 통해 R이 0이 아닌 동안 두 수를 나누도록 구현할 수 있다.

def gcd(a, b):
  if a%b==0:
    return b
  return gcd(b, a%b)

print(gcd(192,162))