📌 재귀 함수(이것이 취업을 위한 코딩 테스트다 with python)

📖 01. 재귀 함수

-> 재귀함수는 스택과 같은 형태로 생각하면 된다.

G를 A와B의 최대공약수라고 가정하면 a, b는 서로소 일 수 밖에 없다.
A를 B로 나눈 몫을 q라고 한다면 A와 B의 관계를 나타 낼 수 있다.
r(나머지)로 식을 정리한다
이제 (a-qb)와 b가 서로소임을 증명하면 된다.
귀류법을 이용해서 (a-qb)와 b가 서로소가 아님을 가정하자.
그럼 공통의 최대 공약수가 존재할 것이고 p라고 하자.
이후 a와b로 식정리를 하면 p가 공통인수가 된다. 이는 처음에 a와b가 서로소라고 했기 때문에 가정에 적합하지 않다.
따라서 (a-qb)와 b는 서로소이다. 따라서 r과 B는 A와 B의 최대공약수(G)를 갖는다.

[출처] 이것이 취업을 위한 코딩테스트다 with python (나동빈 지음)