[TIL #15] 콜라츠 추측

콜라츠 추축은 모든 자연수 $n$에 대해 다음 과정을 거쳐 항상 1이 된다는 추측이다.

 

$$\begin{equation}
T(n) = 
\begin{cases} 
\frac{n}{2}, & \text{if } n \text{ is even} \\
3n + 1, & \text{if } n \text{ is odd}
\end{cases}
\end{equation}$$

 

 

난 다음과 같이 구현했다.

using namespace std;

long long collatz(long long n, int cnt)
{   
    if (cnt >= 500)
        return -1;
    
    if (n == 1)
        return cnt;    
    
    return n % 2 == 0 ? collatz(n / 2, ++cnt) : collatz(n * 3 + 1, ++cnt);
}

int solution(int num) {
    return (int)collatz(num, 0);
}

재귀를 통해 간결한 코드를 작성했다.

하지만 재귀엔 스택 오버플로우의 위험이 있고, 함수 호출 자체가 오버헤드기 때문에 성능면에서 손해를 본다.

 

반복문을 사용하면 오버플로우의 위험이 없고 추가적인 함수 호출 오버헤드가 없으므로 더 효율적이다.

int collatz(int num) {
    int cnt = 0;
    while (num != 1 && cnt < 500) {
        if (num % 2 == 0)
            num /= 2;
        else
            num = num * 3 + 1;
        cnt++;
    }
    return (num == 1) ? cnt : -1;
}

 

 

이번엔 흥미 본위로 재귀를 사용해 풀었지만,

DFS나 분할 정복 같은 재귀를 사용하는 것이 효과적인 것들에 있어서 재귀를 활용할 수 있도록 해야겠다.

무턱대고 사용한다면 성능 상 손해를 보게 될 것이 분명하기 때문.