[에러 해결] Python 재귀 함수 수동 캐싱 오류: 잘못된 메모이제이션 원인과 올바른 구현 방법

안녕하세요, 개발자 여러분! 오늘은 파이썬(Python)에서 재귀 함수를 수동으로 캐싱(메모이제이션)할 때 자주 발생하는 오류와 그 해결 방법에 대해 깊이 있게 다뤄보겠습니다. 특히 스택오버플로우(Stack Overflow)에서 흔히 볼 수 있는 ‘잘못된 수동 캐싱’ 문제 사례를 통해, 올바른 메모이제이션의 본질과 구글 검색 상위 노출에 최적화된 고품질 기술 문서로 풀어내겠습니다.

재귀 함수는 복잡한 문제를 간결하게 해결할 수 있는 강력한 도구이지만, 동일한 하위 문제를 반복적으로 계산하여 비효율적일 수 있습니다. 이를 해결하기 위해 캐싱(메모이제이션) 기법이 사용되는데, 파이썬에서는 @lru_cache 데코레이터를 통해 쉽게 구현할 수 있습니다. 하지만 이 기능을 수동으로 구현하려 할 때 종종 예상치 못한 오류에 직면하게 됩니다.

1. 에러 발생 상황

문제 상황은 다음과 같습니다. 로봇이 숫자 1에서 시작하여 두 가지 명령(ADD 3, SUB 2) 중 하나를 정확히 68번 실행합니다. 이 시나리오에서 로봇이 도달할 수 있는 서로 다른 숫자의 총 개수는 몇 개일까요?

이 문제는 많은 중간 숫자가 중복 계산될 수 있는 깊은 재귀를 포함하므로, 반복적인 호출을 피하기 위한 캐싱이 필수적입니다.

Solution 1: @lru_cache 사용

파이썬의 내장 캐싱 데코레이터인 @lru_cache를 사용하면 이 문제를 정확하게 해결할 수 있습니다. 이 코드는 정답인 69를 반환합니다.

from functools import lru_cache

numbers = set()

@lru_cache(None)
def f(begin, depth):
    if depth == 68:
        numbers.add(begin)
    else:
        f(begin + 3, depth + 1)
        f(begin - 2, depth + 1)

f(1, 0)
print(len(numbers)) # 결과: 69

Solution 2: 수동 캐싱 시도 (잘못된 구현)

재귀의 이해를 돕기 위해 @lru_cache 없이 수동으로 캐싱을 구현하려는 시도입니다. 아이디어는 중간 숫자를 셋(processed)에 저장하고, 이미 처리된 숫자라면 재귀 호출을 피하는 것입니다.

processed = set()
numbers = set()

def f(begin, depth):
    if depth == 68:
        numbers.add(begin)
    else:
        # 이 부분이 문제입니다!
        if (begin + 3) not in processed:
            f(begin + 3, depth + 1)
            processed.add(begin + 3) # 호출 후에 추가
        
        if (begin - 2) not in processed:
            f(begin - 2, depth + 1)
            processed.add(begin - 2) # 호출 후에 추가

f(1, 0)
print(len(numbers)) # 결과: 45

위 코드는 45라는 잘못된 결과를 반환합니다. @lru_cache 버전과 비교했을 때 현저히 낮은 숫자입니다. 스택오버플로우 커뮤니티에서는 이 수동 캐싱 방식에 무엇이 문제인지, 어떻게 수정해야 올바른 답(69)을 얻을 수 있는지 질문했습니다.

2. 명확한 발생 원인

수동 캐싱(Solution 2)이 잘못된 결과를 내는 이유는 메모이제이션의 핵심 원리인 ‘상태(State) 식별’과 ‘캐싱 대상 및 시점’을 오해했기 때문입니다.

잘못된 상태 식별: begin 값만 캐싱

@lru_cache는 함수에 전달되는 모든 인자, 즉 (begin, depth) 튜플 전체를 하나의 ‘상태’로 간주하고 그 상태에 대한 결과를 캐싱합니다. 즉, f(5, 10)과 f(5, 20)은 begin 값은 같지만 depth가 다르므로 @lru_cache는 이를 별개의 호출로 보고 각각의 결과를 캐싱합니다.

하지만 Solution 2의 processed 셋은 오직 begin 값만 저장합니다. 예를 들어, begin 값이 5인 상태가 depth=10에서 한 번 처리되었다면, processed 셋에는 5가 추가됩니다. 이후 depth=20에서 다시 begin 값이 5에 도달하려 할 때, 5 in processed는 참이 되어 해당 경로를 차단해버립니다.

문제는 begin 값이 같더라도 depth가 다르면 앞으로의 계산 경로와 도달할 수 있는 최종 숫자가 완전히 달라질 수 있다는 것입니다. depth는 남은 명령 횟수를 나타내므로, 이는 매우 중요한 정보입니다. begin 값만으로 캐싱하는 것은 유효한 탐색 경로를 조기에 차단하여 최종적으로 도달 가능한 숫자들의 수를 과소평가하게 만듭니다.

잘못된 캐싱 시점 및 대상

Solution 2의 코드를 다시 보면:

if (begin + 3) not in processed:
    f(begin + 3, depth + 1)
    processed.add(begin + 3) # <--- 여기에 문제가 있습니다.

processed.add(begin + 3)이 재귀 호출 f(begin + 3, depth + 1) 이후에 실행됩니다. 이는 해당 (begin + 3) 값이 현재 호출의 모든 하위 재귀가 끝난 후에야 '처리되었다'고 표시하는 방식입니다. 일반적인 메모이제이션은 어떤 상태 (begin, depth)에 대한 계산을 시작하기 전에 해당 상태가 이미 처리 중이거나 처리 완료되었는지 확인하고, 처리할 예정이라면 바로 캐시(또는 processed 셋)에 추가합니다. 이로써 동일한 상태에 대한 중복 계산을 효과적으로 방지할 수 있습니다.

결론적으로, Solution 2는 재귀 함수의 '상태'를 불완전하게 정의하고, 캐싱의 시점 또한 적절하지 않아 올바른 결과를 얻지 못했습니다.

3. 해결 방법 및 코드 예시

올바른 수동 캐싱을 위해서는 다음 두 가지를 준수해야 합니다.

1. 캐싱 키(Key)로 함수의 모든 '상태'를 나타내는 인자(여기서는 (begin, depth) 튜플)를 사용해야 합니다.
2. 어떤 상태를 탐색하려 할 때, 탐색 시작 직전에 해당 상태를 '처리 중' 또는 '처리 완료'로 표시해야 합니다.

이를 반영하여 Solution 2를 수정하면 다음과 같습니다.

Solution 3: 올바른 수동 캐싱

processed_states = set() # (begin, depth) 튜플을 저장
numbers = set()

def f(begin, depth):
    # 현재 상태 (begin, depth)가 이미 처리되었는지 확인
    if (begin, depth) in processed_states:
        return
    
    # 현재 상태를 처리 중/완료 상태로 추가
    processed_states.add((begin, depth))

    if depth == 68:
        numbers.add(begin)
    else:
        f(begin + 3, depth + 1)
        f(begin - 2, depth + 1)

f(1, 0)
print(len(numbers)) # 결과: 69

위 코드는 processed_states 셋에 (begin, depth) 튜플을 저장하고, 재귀 호출 직전(함수 시작 부분)에 현재 상태가 이미 처리되었는지 확인합니다. 만약 처리되었다면 즉시 return하여 중복 계산을 피합니다. 이 방식은 @lru_cache와 동일하게 동작하며, 올바른 결과인 69를 반환합니다.

이 문제에서는 단순히 "도달 가능한 숫자의 개수"만 찾으면 되므로, processed_states 셋에 (begin, depth) 튜플의 존재 여부만 확인해도 충분합니다. 만약 특정 상태 (begin, depth)에 대한 "반환 값"이 중요한 문제였다면, memo = {}와 같이 딕셔너리를 사용하여 memo[(begin, depth)] = result 형태로 캐싱했을 것입니다.

4. 향후 예방을 위한 팁

재귀 함수와 동적 계획법(Dynamic Programming) 문제를 다룰 때 이러한 오류를 예방하기 위한 몇 가지 팁을 드립니다.

1. '상태(State)'의 정확한 정의

   재귀 함수의 캐싱에서 가장 중요한 것은 '상태'를 정확히 정의하는 것입니다. 상태는 함수의 결과를 결정하는 모든 입력 인자를 포함해야 합니다. 이 문제에서는 begin과 depth 모두가 상태를 구성하는 필수 요소였습니다. 단순히 특정 변수 하나만으로 상태를 정의하지 않도록 주의하세요.

2. @lru_cache의 활용 극대화

   대부분의 파이썬 재귀 문제에서는 functools.lru_cache 데코레이터가 가장 빠르고 간편한 해결책입니다. 수동으로 캐싱을 구현하는 것보다 버그 발생 위험이 적고, 코드 가독성도 높습니다. 특별한 이유(예: lru_cache의 한계를 넘어서는 커스텀 캐싱 로직, 또는 학습 목적)가 아니라면 @lru_cache를 먼저 고려하세요.

3. 캐싱 시점의 이해

   메모이제이션은 함수가 어떤 상태에 대한 계산을 시작하기 직전에 해당 상태를 캐시에 추가하거나, 이미 캐시에 있는지 확인하여 중복 계산을 방지합니다. 이 '시점'을 정확히 이해하고 코드에 반영해야 합니다.

4. 작은 입력으로 디버깅

   복잡한 재귀 문제는 작은 depth 값 (예: 2, 3)으로 시작하여 print() 문을 이용해 processed 셋이나 lru_cache의 내부 동작(어떤 인자가 몇 번 호출되는지)을 추적해보는 것이 매우 효과적입니다. 이를 통해 잘못된 캐싱 로직을 쉽게 발견할 수 있습니다.

이 문서를 통해 파이썬 재귀 함수의 수동 캐싱 오류 원인을 명확히 이해하고, 향후 개발 과정에서 유사한 실수를 피하는 데 도움이 되기를 바랍니다. 올바른 메모이제이션 기법은 코드의 성능을 향상시키고 복잡한 알고리즘 문제를 효율적으로 해결하는 데 필수적인 지식입니다.