행복한 수(Happy Number)란?
행복한 수는 각 자릿수의 제곱을 더한 값으로 숫자를 반복적으로 교체했을 때, 최종적으로 1에 도달하는 수를 말합니다. 반면 이 과정에서 같은 숫자가 다시 나타나면 무한히 사이클이 돌게 되는데, 이러한 수는 '불행한 수(Unhappy Number)'라고 부릅니다.
예를 들어, 13은 행복한 수입니다.
1² + 3² = 10
1² + 0² = 1
각 자릿수의 제곱을 계속 더하다 보면 결국 1에 도달하기 때문입니다. 반면 36은 불행한 수입니다. 36 → 45 → 41 → 17 → 50 → 25 → 29 → 85 → 89 ... 로 진행되며 4 → 16 → 37 → 58 → 89로 이어지는 무한 사이클에 빠져 1에 도달하지 못합니다.
재귀로 해결하는 접근 방식
이번 글에서는 재귀(recursion)를 활용해 어떤 숫자가 행복한 수인지 판별하는 함수를 작성해 보겠습니다.
이 문제의 핵심은 이미 등장했던 숫자들을 기록하는 것입니다. 동일한 숫자가 다시 나타난다면 무한 루프에 빠진 것이므로 false를 반환하고, 자릿수의 제곱합이 1이 되면 true를 반환하면 됩니다.
등장 여부를 추적하기 위해 객체(object)를 사용할 것입니다. Set이나 Map을 사용해도 되지만, 간단한 객체만으로도 충분히 구현할 수 있습니다.
구현 코드
먼저 각 자릿수의 제곱합을 재귀적으로 계산하는 헬퍼 함수와, 이를 활용해 행복한 수를 판별하는 메인 함수를 작성합니다.
const squareSumRecursively = (n, res = 0) => {
if(n){
return squareSumRecursively(Math.floor(n/10), res+Math.pow((n%10),2));
};
return res;
};
const isHappy = (num, map = {}) => {
if(num !== 1){
if(map[num]){
return false;
}
map[num] = 1;
return isHappy(squareSumRecursively(num), map);
};
return true;
}
console.log(isHappy(36));
console.log(isHappy(13));
console.log(isHappy(36));
console.log(isHappy(23));코드 설명
squareSumRecursively 함수: 숫자 n을 받아 마지막 자릿수(n % 10)의 제곱을 결과값에 누적하고, 나머지 부분(Math.floor(n / 10))을 대상으로 자기 자신을 다시 호출합니다. n이 0이 되면 누적된 제곱합을 반환합니다.
isHappy 함수: 숫자가 1이 아니라면, 해당 숫자가 이미 map 객체에 기록되어 있는지 확인합니다. 기록되어 있다면 사이클에 빠진 것이므로 false를 반환하고, 그렇지 않다면 현재 숫자를 기록한 뒤 자릿수 제곱합으로 재귀 호출을 이어갑니다. 최종적으로 1에 도달하면 true를 반환합니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
false true false true
36은 불행한 수이므로 false, 13은 행복한 수이므로 true가 출력됩니다. 같은 값을 두 번 호출해도 매번 새로운 빈 객체가 기본값으로 사용되므로 항상 일관된 결과를 얻을 수 있습니다. 23 역시 2² + 3² = 13 → 1² + 3² = 10 → 1로 도달하므로 true가 출력됩니다.