Python에서 두 숫자의 gcd를 재귀적으로 계산하는 프로그램

두 개의 숫자와 b가 있다고 가정합니다. 이 두 숫자의 GCD를 재귀적으로 찾아야 합니다. GCD를 얻기 위해 우리는 유클리드 알고리즘을 사용할 것입니다.

따라서 입력이 a =25 b =45와 같으면 출력은 5

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• gcd() 함수를 정의합니다. , b
• b와 같으면
  • 반환
• 그렇지 않으면
• gcd(b, a) 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a - b)

a = 25
b = 45
print(gcd(a, b))

입력

25, 45

출력

5