문제 15 - 콜라츠 추측 (Python)

프로그래머스

 

주어진 수가 1이 될 때까지 특정 연산을 반복하며 그 횟수를 구하는 문제입니다. 이 과정에서 재귀 함수(Recursion)의 기초 설계 방법인 상태 정의, 종료 조건 설정, 그리고 점화식 수립의 원리를 학습할 수 있습니다.

---

1.  나의 풀이

def collatz(n, cnt):
    # [종료 조건 1] 작업을 500번 반복할 때까지 1이 되지 않는다면 -1을 반환
    if cnt == 500:
        return -1
    
    # [종료 조건 2] 주어진 수가 1인 경우 현재까지의 반복 횟수를 반환
    if n == 1:
        return cnt
    
    # 상태 변화: 반복 횟수 1 증가
    cnt += 1

    # [점화식] 짝수라면 2로 나누고, 홀수라면 3을 곱하고 1을 더함
    if n % 2 == 0:
        return collatz(n // 2, cnt)
    else:
        return collatz(n * 3 + 1, cnt)


def solution(num):
    # 숫자 num과 초기 카운트 0을 인자로 전달하여 재귀 시작
    return collatz(num, 0)

---

2.  오늘 배운 점 및 복기 노트

재귀 함수의 정의와 필요성

재귀 함수는 함수 내부에서 자기 자신을 다시 호출하는 구조를 말합니다. 많은 알고리즘 문제가 반복문으로 해결 가능함에도 재귀를 사용하는 이유는 크게 세 가지가 있습니다. 첫째, 구현해야 할 알고리즘이 반복문보다 점화식의 형태로 표현될 때 훨씬 자연스럽습니다. 둘째, 현재 상태를 함수의 인자로 관리하므로 상태 변화를 위한 변수 사용을 줄여 사이드 이펙트를 방지할 수 있습니다. 셋째, 코드의 길이가 짧아져 전반적인 가독성이 높아집니다.

 

재귀 설계의 3단계 프로세스

재귀를 올바르게 구현하기 위해서는 세 가지 요소가 반드시 포함되어야 합니다.

1. 상태 정의: 문제를 풀기 위한 최소한의 데이터가 무엇인지 정의합니다. 이번 문제에서는 '현재의 숫자'와 '진행된 횟수'가 상태가 됩니다.
2. 종료 조건: 함수가 더 이상 자신을 호출하지 않고 값을 반환하는 지점을 명시합니다. 종료 조건이 없거나 부실하면 무한 호출에 빠지게 됩니다.
3. 점화식: 현재 상태에서 다음 상태로 넘어가는 논리적인 규칙을 세웁니다.

재귀적 사고와 가설 검증

재귀 함수가 실제로 메모리 스택에 쌓이고 빠지는 과정을 일일이 추적하는 것은 불가능에 가깝습니다. 따라서 재귀 문제를 풀 때는 "이 함수가 다음 단계의 답을 올바르게 가져올 것이다"라는 믿음을 바탕으로 논리적인 점화식을 설계하는 데 집중해야 합니다. 복잡한 증명 대신 대입법을 통해 요구되는 범위 내에서 가설이 맞는지 확인하는 방식이 코딩 테스트에서는 효율적입니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

스택 오버플로와 파이썬의 한계점

재귀 함수는 호출될 때마다 실행이 완료된 후 돌아갈 주소를 메모리의 스택 영역에 누적합니다. 이 스택은 무한하지 않으므로 일정 개수를 넘어가면 스택 오버플로(Stack Overflow)가 발생하며 프로그램이 강제 종료됩니다. 파이썬의 경우 기본 재귀 깊이 제한이 1,000개로 설정되어 있습니다. 만약 더 깊은 재귀가 필요하다면 sys.setrecursionlimit()을 사용하여 제한을 늘려야 합니다.

import sys
sys.setrecursionlimit(10 ** 6)

 

꼬리 재귀(Tail Recursion)의 개념과 장점

기존 재귀 방식은 함수 종료 후 돌아와서 추가 연산(예: \( f(n-1) + f(n-2) \))을 수행해야 하므로 스택을 계속 점유합니다. 반면 꼬리 재귀는 return 문에서 함수 호출 외에 아무런 연산도 하지 않도록 설계하여, 함수 종료 후 즉시 결과만 반환하게 만듭니다. 컴파일러가 이를 지원할 경우 반복문으로 자동 변환되어 성능이 극대화되지만, 파이썬 인터프리터는 현재 이 최적화를 지원하지 않으므로 여전히 재귀 횟수 제한에 유의해야 합니다.

 

상태를 인자로 관리하는 습관

피보나치 수열을 예로 들 때, 단순 재귀는 중복 계산이 많아 속도가 느리지만 꼬리 재귀 방식인 \( fib\_tail(n, second, first + second) \)와 같이 상태를 인자로 넘기면 연산 횟수를 획기적으로 줄일 수 있습니다. 이번 콜라츠 추측 풀이에서도 cnt를 인자로 넘기는 방식을 채택하여 상태 관리의 효율성을 높였습니다.