정수 하나가 입력으로 주어졌을 때, 재귀(recursion)를 이용해 이 숫자 Num이 회문(palindrome)인지 아닌지 판별하는 것이 목표입니다.
회문 여부를 확인하는 방법은 간단합니다. 숫자를 뒤집은 값과 원래 값을 비교하면 됩니다. 뒤집힌 숫자가 원래 숫자와 완전히 같다면 그 수는 회문입니다.
예시
입력 − Num = 34212
출력 − 34212는 회문이 아닙니다!
설명 − 34212를 뒤집으면 21243이 됩니다. 34212 ≠ 21243이므로 입력된 숫자는 회문이 아닙니다.
입력 − Num = 32123
출력 − 32123은 회문입니다!
설명 − 32123을 뒤집어도 32123 그대로입니다. 뒤집은 값과 원래 값이 같으므로 이 숫자는 회문입니다.
프로그램에 사용된 접근 방식
이 접근 방식에서는 입력 숫자 num1과 임시 누적값 num2를 매개변수로 받는 재귀 함수 revrsNum(int num1, int num2)를 사용합니다.
기저 사례(Base case): num1이 0이면 지금까지 누적된 num2를 반환합니다.
그 외의 경우: 재귀 호출을 통해 num1의 뒤집힌 값을 계산하고, 최종적으로 계산된 역순 값을 반환합니다.
함수가 반환한 뒤집힌 값과 원래 입력값이 같다면, 입력 숫자는 회문입니다.
알고리즘 단계
- 입력 숫자 Num을 받습니다.
- Num2 = revrsNum(Num, 0) 형태로 함수를 호출하여 뒤집힌 값을 구합니다.
- 함수 revrsNum(int num1, int num2)는 재귀적으로 num1의 뒤집힌 값을 생성하여 반환합니다.
- num1이 0이면 지금까지 계산된 num2를 그대로 반환합니다.
- 그렇지 않으면 num2에 10을 곱한 후 num1 % 10(현재 일의 자리 숫자)을 더합니다.
- num1 = num1 / 10 연산으로 num1의 자릿수를 한 칸 줄입니다.
- revrsNum(num1, num2)를 호출하며 재귀를 반복합니다.
- 모든 자릿수 처리가 끝나면 최종 결과를 반환합니다.
- main 함수 안에서 얻어진 결과를 출력합니다.
예를 들어 1345431의 경우, 재귀 호출마다 일의 자리 숫자(1, 3, 4, 5, 4, 3, 1)를 차례로 꺼내어 누적값에 10을 곱하고 더하는 방식으로 1345431이 다시 만들어집니다. 원래 값과 동일하므로 회문임을 알 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int revrsNum(int num1, int num2){
if (num1 == 0){
return num2;
}
num2 *= 10;
num2 += (num1 % 10);
num1 = num1/10;
return revrsNum(num1, num2);
}
int main(){
int Num = 1345431;
int Num2 = revrsNum(Num,0);
if (Num == Num2){
cout <<Num<<" is Palindrome!";
}
else{
cout <<Num<<" is not a Palindrome!";
}
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1345431 is Palindrome!