문제

프로그래머스: 콜라 문제
https://school.programmers.co.kr/learn/courses/30/lessons/132267

해당 문제를 해결하기 위해 재귀 함수를 사용했다.

def bottle(a, b, n, result):
    if n < a:
        return result
    
    give = n // a * a
    receive = n // a * b
    return bottle(a, b, n - give + receive, result + receive)

에러

그런데 특정 테스트 케이스에서만 런타임 에러가 발생했다. 재귀 함수를 사용하고 있으므로 이와 관련된 것일 거라 생각했다. 찾아본 결과, 파이썬에서는 기본적으로 재귀 깊이 제한 (sys.getrecursionlimit())이 약 1000으로 설정되어 있기 때문에 재귀 호출이 1000번 이상 반복되어 RecursionError (maximum recursion depth exceeded)가 발생했을 가능성이 높은 것으로 보인다.

해결

이를 해결하기 위한 방법으로는 반복문으로 변경하거나 재귀의 깊이를 늘리는 방법이 있다. 하지만 재귀의 깊이를 늘리게 되면 메모리 소비가 커지고 무한 루프에 빠질 수 있어서 메모리를 절약할 수 있도록 반복문으로 변경하였다.

while n >= a:
   give = n // a * a
   receive = n // a * b
   n -= give - receive
   result += receive
return result

반복문으로 변경하니 런타임 예외가 발생하지 않고 통과되었다.