파이썬에서 트리 구조 데이터를 재귀 함수로 훑다가 RecursionError: maximum recursion depth exceeded를 만나면 보통 “재귀 한도가 1000이니까 1000단계를 넘었구나” 하고 sys.setrecursionlimit()부터 올립니다. 그런데 직접 돌려 보니 단순하지 않았습니다. 중첩 댓글 개수를 세는 함수가 한도 1000에서 깊이 499에 멈췄고, 한도를 100만으로 올려도 어떤 재귀는 약 1,500단계에서 그대로 같은 오류를 냈습니다. 이 글에서는 RecursionError가 나는 실제 경계, 한도를 올려서 되는 경우와 안 되는 경우, 그리고 재귀를 반복문(스택)으로 바꾸는 방법을 실측 결과와 함께 정리합니다. 환경은 윈도우 11, Python 3.12.10이고 표준 라이브러리만 썼습니다.
RecursionError는 언제 나나 — 한도 1000의 실제 의미
파이썬은 함수가 자기 자신을 부를 때마다 호출 기록(프레임)을 하나씩 쌓습니다. 이 프레임이 무한히 쌓여 프로그램이 죽는 걸 막으려고 상한을 두는데, 기본값은 sys.getrecursionlimit()로 확인할 수 있고 이 노트북에서는 1000이었습니다. 1부터 n까지 더하는 가장 단순한 재귀로 경계를 찾아봤습니다.
import sys
def total(n):
"""1부터 n까지 더하기 — 재귀 버전"""
if n == 0:
return 0
return n + total(n - 1)
print("기본 재귀 한도:", sys.getrecursionlimit())
total(5000)기본 재귀 한도: 1000
total(998) 성공, total(999)에서 RecursionError
traceback 줄 수: 14
...
File "...\limit.py", line 9, in total
return n + total(n - 1)
^^^^^^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded한도는 1000이지만 실제로 성공한 건 total(998)까지였습니다. 스크립트 본체(모듈)와 호출한 쪽 프레임이 이미 몇 칸을 차지하고 있기 때문입니다. 그래서 “999단계까지는 된다”고 계산해 두면 경계에서 틀립니다. 또 5000단계를 시도한 traceback은 1000줄이 아니라 14줄이었습니다. 같은 줄이 반복되면 [Previous line repeated 996 more times]로 접어서 보여주기 때문에, 이 문구가 보이면 무한 재귀나 지나치게 깊은 재귀를 의심하면 됩니다.
참고로 처음 실행했을 때는 오류보다 한글 출력이 전부 깨진 게 먼저 보였습니다. 윈도우 콘솔 인코딩이 cp949라서 생긴 일이었고, python -X utf8 limit.py처럼 UTF-8 모드로 실행해 해결했습니다. 재귀와는 상관없는 문제지만 윈도우에서 결과를 볼 때 자주 겪는 일이라 적어 둡니다.
한도 1000인데 깊이 499에서 멈춘 이유
실전에 가까운 예로, 댓글에 답글이 달리고 그 답글에 또 답글이 달린 중첩 데이터를 만들고 전체 개수를 세 봤습니다. 처음엔 짧게 쓰려고 sum()과 제너레이터 식으로 작성했는데, 깊이 300은 됐지만 깊이 500에서 RecursionError가 났습니다. 한도의 절반밖에 안 됩니다. 같은 일을 for문으로 쓴 버전과 경계를 비교했습니다.
# 제너레이터 식 안에서 재귀 — 한 단계에 프레임 2개
def count_recursive(node):
return 1 + sum(count_recursive(c) for c in node["replies"])
# 같은 일을 for문으로
def count_plain(node):
n = 1
for c in node["replies"]:
n += count_plain(c)
return n$ python -X utf8 boundary.py
sum(제너레이터) 재귀 최대 깊이: 499
for문 재귀 최대 깊이: 998
json.dumps 깊이 1,000: OK, 53,780자
json.dumps 깊이 5,000: RecursionError: maximum recursion depth exceeded while encoding a JSON object
json.loads 대괄호 1,000겹: OK
json.loads 대괄호 10,000겹: RecursionError: maximum recursion depth exceeded while decoding a JSON array from a unicode string제너레이터 식 버전은 499, for문 버전은 998이었습니다. 제너레이터 식도 내부적으로는 함수처럼 프레임을 하나 만들기 때문에, 재귀 한 단계마다 프레임이 2개씩 쌓여 한도가 절반으로 줄어든 셈입니다. 코드가 짧고 보기 좋다고 재귀 안에 제너레이터 식이나 컴프리헨션을 넣으면 그만큼 일찍 터집니다.
표준 라이브러리도 예외가 아니었습니다. json.dumps()는 댓글 1,000단계 데이터는 처리했지만 5,000단계에서 while encoding a JSON object가 붙은 RecursionError를 냈고, json.loads()는 대괄호 1만 겹 문자열에서 실패했습니다. 내 코드에 재귀가 없어도 깊게 중첩된 데이터를 json으로 저장·로드하는 순간 같은 오류를 만날 수 있다는 뜻입니다.
setrecursionlimit으로 한도를 올리면 해결될까
가장 흔한 처방인 sys.setrecursionlimit()을 시험했습니다. 혹시 프로세스가 죽을 수 있어서 자식 프로세스로 띄우고 종료 코드를 확인했습니다. 먼저 순수 파이썬 함수끼리만 부르는 단순 재귀입니다.
$ python -X utf8 raise_limit.py
한도 10,000, total(9,000): 종료코드 0 (0x0), 0.03초, 출력: 40504500
한도 100,000, total(90,000): 종료코드 0 (0x0), 0.04초, 출력: 4050045000
한도 1,000,000, total(900,000): 종료코드 0 (0x0), 0.19초, 출력: 405000450000
한도 10,000,000, total(9,000,000): 종료코드 0 (0x0), 1.50초, 출력: 40500004500000Python 3.12.10에서는 한도를 1,000만으로 올리고 900만 단계를 재귀해도 크래시 없이 정상 종료(종료 코드 0)했고 1.50초 걸렸습니다. 여기까지만 보면 “한도만 올리면 된다”는 결론이 나옵니다. 그런데 앞의 제너레이터 버전과 json으로 같은 시험을 하자 결과가 달랐습니다.
$ python -X utf8 c_limit.py # sys.setrecursionlimit(1_000_000) 상태
파이썬 버전: 3.12.10
sum+제너레이터 재귀: 1,499
for문 재귀: 200,000
json.dumps: 1,498한도를 100만으로 올려 둔 상태인데도 sum()+제너레이터 재귀는 1,499, json.dumps()는 1,498에서 멈췄습니다. for문 재귀는 탐색 상한인 20만까지 통과했습니다. 두 경우의 공통점은 재귀 중간에 C로 만든 함수(sum, json 인코더)가 끼어 있다는 것입니다. 이런 재귀는 setrecursionlimit으로 올린 한도와 별개의 상한에 걸리는 것으로 보이며, 이번 실측에서는 한도를 아무리 올려도 약 1,500단계를 넘지 못했습니다.
| 재귀 형태 | 기본 한도(1000) | 한도 1,000,000으로 올린 뒤 |
|---|---|---|
| for문으로 쓴 순수 파이썬 재귀 | 998 | 200,000 통과(탐색 상한) |
| sum() + 제너레이터 식 재귀 | 499 | 1,499 |
| json.dumps (중첩 dict/list) | 1,000단계 OK, 5,000단계 실패 | 1,498 |
정리하면 한도 올리기는 “내 코드가 순수 파이썬 재귀이고, 깊이의 상한을 알고 있을 때”만 쓸 만한 임시방편입니다. 데이터가 커지면 깊이도 같이 커지는 구조라면 근본적으로는 반복문으로 바꾸는 게 맞습니다.
재귀를 반복문으로 바꾸기 — 스택을 직접 쌓는 법
재귀 함수가 하는 일은 “처리할 일을 호출 스택에 쌓아 두고 하나씩 꺼내 처리”하는 것입니다. 그 스택을 파이썬 리스트로 직접 만들면 재귀 없이 같은 결과를 낼 수 있습니다. 중첩 댓글을 (깊이, 댓글 id) 목록으로 펼치는 함수를 두 방식으로 작성했습니다.
def flatten_rec(node, depth=0, out=None):
if out is None:
out = []
out.append((depth, node["id"]))
for c in node["replies"]:
flatten_rec(c, depth + 1, out)
return out
def flatten_loop(root):
out = []
stack = [(root, 0)] # 처리할 (노드, 깊이)를 직접 쌓는다
while stack:
node, depth = stack.pop()
out.append((depth, node["id"]))
# 뒤집어서 넣어야 첫 답글이 먼저 나온다
for c in reversed(node["replies"]):
stack.append((c, depth + 1))
return out여기서 처음에 실수하기 쉬운 부분이 있습니다. 리스트의 pop()은 마지막에 넣은 것부터 꺼내기 때문에, 답글을 순서대로 넣으면 순서가 거꾸로 나옵니다. 댓글 8개짜리 작은 트리로 확인한 결과입니다.
작은 트리 재귀: [(0, 0), (1, 1), (2, 3), (1, 2), (1, 4), (2, 6), (1, 5), (1, 7)]
스택(뒤집기 X): [(0, 0), (1, 7), (1, 5), (1, 4), (2, 6), (1, 2), (1, 1), (2, 3)]
스택(뒤집기 O): [(0, 0), (1, 1), (2, 3), (1, 2), (1, 4), (2, 6), (1, 5), (1, 7)]뒤집지 않은 버전은 1번 답글보다 7번 답글이 먼저 나왔습니다. 개수 세기처럼 순서가 상관없는 작업이면 괜찮지만, 화면에 들여쓰기로 보여주는 용도라면 reversed()로 넣어야 재귀 버전과 똑같은 순서가 됩니다.
이제 무작위로 답글을 붙인 트리를 크기별로 만들어 두 방식을 비교했습니다.
$ python -X utf8 flatten.py
댓글 1,000개(최대 깊이 45): 재귀 0.0002초, 순서 같음 True / 스택 0.0006초
댓글 20,000개(최대 깊이 785): 재귀 0.0079초, 순서 같음 True / 스택 0.0102초
댓글 50,000개(최대 깊이 1988): 재귀 RecursionError / 스택 0.0204초댓글 2만 개(최대 깊이 785)까지는 두 방식 결과가 완전히 같았고, 속도는 오히려 재귀가 약간 빨랐습니다(0.0079초 대 0.0102초). 스택 버전은 매번 튜플을 만들어 넣고 꺼내는 비용이 있기 때문입니다. 다만 이 차이는 실행할 때마다 수 ms씩 달라졌습니다. 중요한 건 5만 개였습니다. 최대 깊이가 1,988이 되자 재귀는 RecursionError로 실패했고, 스택 버전은 0.0204초에 끝냈습니다. 데이터가 늘면 언젠가 터지는 코드냐, 아니냐의 차이입니다.
lru_cache를 붙인 재귀도 터진다
피보나치처럼 같은 값을 반복 계산하는 재귀에는 functools.lru_cache를 붙이는 게 정석입니다. 계산은 빨라지지만 깊이 문제는 그대로였습니다.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(2000) # 빈 캐시 → RecursionError
fib.cache_clear()
for i in range(0, 2001, 200):
fib(i) # 아래부터 200씩 채우면
fib(2000) # 성공 (418자리)$ python -X utf8 speed.py
1~900 합계 2000회: 재귀 0.203초 / 반복문 0.054초 (3.8배)
lru_cache fib(400): OK, 84자리
lru_cache fib(600): OK, 126자리
lru_cache fib(2000): RecursionError: maximum recursion depth exceeded
200씩 미리 채운 뒤 fib(2000): 418자리, 반복문과 같음: True캐시가 빈 상태에서 fib(2000)을 부르면 결국 fib(1999), fib(1998)…로 바닥까지 내려가야 해서 RecursionError가 났습니다. 0, 200, 400… 순서로 캐시를 아래부터 채운 뒤 부르면 한 번에 200단계씩만 내려가면 되므로 성공했고, 반복문 버전과 결과가 일치했습니다. 같은 실행에서 1~900 합계를 2,000번 반복한 비교에서는 재귀가 0.203초, 반복문이 0.054초로 3.8배 차이가 났습니다. 단순 반복을 재귀로 쓸 이유는 없다는 뜻입니다.
주의할 점
- 한도 1000은 “1000단계까지 된다”가 아닙니다. 실측에서 단순 재귀는 998, 제너레이터 식 안의 재귀는 499에서 멈췄습니다.
- 재귀 안에 제너레이터 식·컴프리헨션을 넣으면 한도가 절반이 됩니다. 깊어질 수 있는 재귀라면 for문으로 풀어 쓰세요.
- setrecursionlimit은 C 함수를 거치는 재귀에 효과가 없었습니다. 한도 100만에서도 sum+제너레이터와 json.dumps는 약 1,500에서 멈췄습니다(Python 3.12.10 기준, 버전마다 다를 수 있음).
- 스택으로 바꿀 때는 순서를 확인하세요. pop()은 마지막 것부터 꺼내므로 원래 순서가 필요하면 reversed()로 넣습니다.
- 재귀 코드가 없어도 json에서 터질 수 있습니다. 외부에서 받은 깊게 중첩된 JSON은 json.loads 단계에서 RecursionError가 날 수 있으니 예외 처리를 해 두세요.
마무리
RecursionError가 나면 한도를 올리기 전에, 그 깊이가 데이터에 따라 계속 커지는 구조인지부터 보세요. 커진다면 스택으로 바꾸는 게 답입니다.
가장 작은 첫걸음은 이렇습니다.
- traceback에
[Previous line repeated ... more times]가 있는지 보고, 어느 함수가 반복되는지 확인합니다. - 그 함수 안에 제너레이터 식이나
sum(),map()같은 C 함수를 거치는 재귀가 있는지 봅니다. 있다면 for문으로 풀어 씁니다. - 데이터 크기에 따라 깊이가 늘어나는 구조라면 위의
flatten_loop처럼 리스트를 스택으로 써서 반복문으로 바꾸고, 작은 데이터로 재귀 버전과 결과가 같은지 비교합니다.
다음 글에서는 폴더 두 개를 비교해서 바뀐 파일만 골라 동기화하는 파이썬 스크립트를 직접 만들어 돌려 보겠습니다.