두 숫자의 최대공약수(GCD)는 두 숫자를 나누는 가장 큰 숫자입니다.
예:45와 27이라는 두 개의 숫자가 있다고 가정해 보겠습니다.
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
재귀를 이용하여 두 숫자의 GCD를 구하는 프로그램은 다음과 같다.
예시
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} 출력
GCD of 63 and 42 is 21
위의 프로그램에서 gcd()는 재귀 함수입니다. 두 개의 매개변수, 즉 및 b가 있습니다. a 또는 b가 0이면 함수는 0을 반환합니다. a 또는 b가 같으면 a를 반환합니다. 가 b보다 크면 함수는 a-b 및 b 값을 사용하여 자신을 재귀적으로 호출합니다. b가 a보다 크면 함수는 값과 b-a를 사용하여 자신을 재귀적으로 호출합니다.
다음 코드 스니펫에서 이를 확인할 수 있습니다.
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
} 재귀를 사용하여 두 숫자의 GCD를 찾는 또 다른 방법은 다음과 같습니다.
예시
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} 출력
GCD of 63 and 42 is 21
위의 프로그램에서 gcd()는 재귀 함수입니다. 두 개의 매개변수, 즉 및 b가 있습니다. b가 0보다 크면 a가 main() 함수로 반환됩니다. 그렇지 않으면 gcd() 함수는 b 및 a%b 값을 사용하여 자신을 재귀적으로 호출합니다.
이것은 다음 코드 스니펫을 사용하여 보여줍니다.
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}