재귀 함수를 활용해 C++에서 n개 정수의 GCD 공식 출력하기

정수 하나가 입력으로 주어졌을 때, 재귀(recursion)를 사용하여 n개 수의 GCD(최대공약수) 공식을 출력하는 것이 목표입니다.

세 수 a1, b1, c1의 최대공약수는 gcd(a1, gcd(b1, c1)) 형태로 표현할 수 있습니다. 마찬가지로 세 개보다 많은 수에 대해서도 gcd(a1, gcd(b1, gcd(c1, …, gcd(y1, z1))))와 같은 공식으로 최대공약수를 구할 수 있습니다.

예시

입력 − Num = 4;

출력 − 공식:

GCD(int a3, GCD(int a2, GCD(int a1, int b1)))

입력 − Num = 6;

출력 − 공식: GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))

프로그램에 적용된 접근 방식

이 접근 방식에서는 숫자의 개수를 입력받아 해당 개수에 대한 GCD 공식이 담긴 문자열을 반환하는 재귀 함수 gcdFormula(int num1)을 사용합니다.

기저 사례(base case): num1이 1이면 문자열 "int b"+to_string(num1)+""를 반환합니다.

그 외의 경우: gcdFormula(num1-1)을 다시 호출하며 이전 문자열에 결과를 덧붙여 나갑니다.

• 입력값 Num을 받습니다.

• 숫자의 개수를 입력받아 GCD 공식 문자열을 반환하는 함수 gcdFormula(int num1)을 정의합니다.

• num1이 1이면 "int b"+to_string(num1)+""를 반환합니다.

• 그렇지 않으면 "GCD(int a"<<num1-1<<", "; 를 출력합니다.

• 이어서 재귀 단계로 return (gcdFormula(num1 - 1)+")")를 수행합니다.

• 마지막에 전체 문자열이 완성되어 반환됩니다.

• main 함수 내부에서 얻은 결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
string gcdFormula(int num1){
    if (num1 == 1){
        return ("int b"+to_string(num1)+"");
    }
    else{
        cout<<"GCD(int a"<<num1-1<<", ";
        return (gcdFormula(num1 - 1)+")");
    }
}
int main(){
    int Num = 6;
    cout<<"Formula is :"<<endl;
    cout<<gcdFormula(Num);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Formula is :
GCD(int a6, GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1))))))