[파이썬 문법] 나는 재귀를 안 썼는데 왜 recursionError가?

최근 백준 문제를 풀다가 좀 편하게 짜려고 이상한 코드를 하나 짰었다.

백준 게시판에 질문도 했었는데 아무도 답이 없었고, 이상한 짓이 굉장히 하고싶어지는 시험기간의 영향으로 해결하게 된 문제이다.

 

문제는 요약하면 문자열 여러개가 주어지고 배치되는 순서가 주어지면 그거에 맞춰서 문자열을 배치하면 되는 문제이다.

 

n이 50만이나 되고, 문자열 길이의 총합도 50만까지 가능하다. 따라서 일반적으로 문자열을 합치는 방식으로 풀게된다면 시간 초과가 나게 된다.

 

그 이유는 파이썬 문자열 연산은 최종적으로 완성되는 문자의 길이만큼의 시간이 소요된다. 조금 깊게 가보면 파이썬 문자열은 "불변성"을 갖고, 뒤에 추가되는 것이 아닌 불변하는 여러개의 문자열에서 문자를 긁어와 새로운 문자열을 만드는 것이기 때문이다.

a라는 문자열이 있고, b라는 문자열이 있을 때 a+=b를 하게 되면 a에 뒤에 b가 추가되는 것이 아닌 a의 메모리 주소에 a+b의 값을 재할당 하는 것이다.

 

50만개의 개별 문자가 존재하고 매번 더해준다면 문자열의 크기만큼, 따라서 2+3+4....+500000 으로 시간 초과를 받을 것이다.

 

해당 문제를 해결하기 위해 사실 맨 처음에 append와 같은 방법을 떠올렸다. append는 O(1)에 추가된다. 길이가 N인 문자열을 append 하는 것도 O(1)이 걸린다. 왜냐하면 append는 실제로 값을 추가하는 것이 아닌 "참조"를 추가하는 것이기 때문이다.

 

그렇게 순서에 맞게 append를 해줬다. dict를 같이 사용해서 최종 dict에는 [1,[2,[3,[4,[5,...]]]]] 이런 식으로 중첩되어있는 형태를 가진 한 개의 값만 남아있게 될 것이고, 해당 값을 이제 적절히 꺼내기만 하면 될 것이라 생각했다.

 

그 방법으로 살짝 좋은 방법은 아니지만 시도했던 방법이 통으로 문자열로 변환한 뒤 [ , ] 이 3가지만 다 빼버리면 되는거 아닌가? 라는 생각으로 코드를 짜 보았었다.

 

그렇게 나온 코드가 아래와 같은데

from sys import stdin
input=stdin.readline
n=int(input())
dd=dict()
s=[0]
for i in range(1,n+1):
    dd[i]=[i]
    s.append(input().rstrip())
for i in range(n-1):
    a,b=map(int,input().split())
    dd[a].append(dd[b])
    del dd[b]
for i in dd:
    ans=''.join(''.join(str(dd[i]).split("[")).split(']')).split(',')
    for j in ans:
        print(s[int(j)],end='')

재미로 짠 코드라 틀릴거 같다는 생각은 했었지만 생각지도 못한 에러를 마주치게 되었었다.

??

 

틀릴거 같다는 생각은 했었지만 RecursionError라니, 분명 나는 재귀를 쓴 적이 없을텐데 왜 이런 에러가 발생했는지 궁금했다.

 

구글링을 해봐도, gpt를 이용해봐도 만족스러운 답을 얻을 수는 없었다.

 

이것저것 테스트 해보다 재미있는 코드 하나를 짜게 되었는데,

arr=[0]
for i in range(1,3000):
    arr.append([arr[-1],i])

아까처럼 중첩된 배열을 생성하는 코드이다.

코드를 실행하면 아래와 같이 생성된 배열을 얻을 수 있다.

arr[0] = 0
arr[1] = [0, 1]
arr[2] = [[0, 1], 2]
arr[3] = [[[0, 1], 2], 3]
...

실행 자체는 문제 없이 잘 실행된다. 그렇지만 arr을 출력하려고 하거나 문자열로 바꾸려 하는 등의 연산을 하게 된다면 다음과 같은 에러 메시지를 받을 수 있다.

RecursionError: maximum recursion depth exceeded while getting the repr of an object

이런 에러가 발생하는 이유에는 파이썬에서 데이터를 처리하는 내부 로직 때문이다.

 

print(arr)을 한다고 가정을 해보면 파이썬 내부에서는 다음과 같이 작동한다.

__repr__ 또는 __str__ 메소드를 호출한다.

공식 문서에서의 설명은 위와 같다. 호출 되었을 때 반환하는 문자열인데, 지금과 같은 배열 상태에서는 다음과 같이 작동한다.

print(arr) 
  → str(arr) 
    → arr.__str__() 
      → arr[0].__repr__() (여기서는 단순히 '0')
      → arr[1].__repr__() 
        → arr[1][0].__repr__() (이것은 arr[0])
        → arr[1][1].__repr__() (이것은 단순히 '1')
      → arr[2].__repr__() 
        → arr[2][0].__repr__() (이것은 arr[1])
          → arr[1][0].__repr__() (계속 더 깊이 들어감)
          → ...

이렇게 작동하게 되고, 따라서 저 깊이가 계속 늘어나면서 RecursionError가 발생하는 것이었다.

감히 파이썬으로 50만회의 재귀를 하려고 했으니 재귀 제한을 늘려도 TLE, MLE 2연타를 맞는 것은 당연한 수순이었다.

파이썬 재귀가 느린 이유는 이런 이유들이 있다.

 

24년 KAUPC 출제 때도 문제 제작 중에 50만번 재귀하는 DFS를 돌리면 재귀 제한 상관 없이 코드가 안돌아가는 일이 발생하기도 했었다. 역시나 이 문제도 마찬가지로 재귀 제한을 20만으로 잡고 제출한 코드가 통과되었기 때문에 50만개가 중첩되는 배열은 존재하지 않았던 것 같다.