- 채점
- 런타임 에러
- 런타임 에러 (RecursionError)
RecursionError
RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.
Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()
을 이용해 확인할 수 있습니다. BOJ의 채점 서버에서 이 값은 1,000으로 되어 있습니다.
소스 1. n을 입력받고, 1부터 n까지 합을 재귀 함수로 구하는 소스
calc(n)
을 호출하면 총 n+1번의 재귀 호출이 발생합니다. print(calc(n))
으로 함수를 호출하고 있기 때문에, print(calc(n))
의 재귀의 깊이는 n+2가 됩니다. 따라서, n < 998의 경우에는 RecursionError가 발생하지 않지만, n ≥ 998부터는 RecursionError가 발생하게 됩니다. 998 이상의 값을 넣었을 때 런타임 에러 메시지는 다음과 같습니다.
Traceback (most recent call last): File "Main.py", line 8, in <module> print(calc(n)) File "Main.py", line 5, in calc return n + calc(n-1) File "Main.py", line 5, in calc return n + calc(n-1) File "Main.py", line 5, in calc return n + calc(n-1) [Previous line repeated 995 more times] File "Main.py", line 2, in calc if n == 0: RecursionError: maximum recursion depth exceeded in comparison
이 에러를 해결하는 방법은 2가지가 있습니다.
첫 번째는 재귀 함수를 사용하지 않는 것입니다. 소스 1은 소스 2와 같이 재귀 함수를 사용하지 않는 방법으로도 구현할 수 있습니다.
소스 2. 소스 1을 반복문을 사용하게 변경한 소스
DFS를 이용했다면 BFS로, 다이나믹 프로그래밍을 재귀로 구현했다면 반복문으로 구현하는 것 처럼 재귀를 사용하지 않게 구현하는 방법으로 해결할 수 있습니다.
두 번째는 sys.setrecursionlimit()
을 사용하는 것입니다. 이 함수를 사용하면, Python이 정한 최대 재귀 갚이를 변경할 수 있습니다. 소스 1의 최대 재귀 깊이를 1,000,000 정도로 크게 설정하면 런타임 에러 없이 실행이 됩니다.
소스 3. 소스 1의 최대 재귀 깊이를 변경한 소스
sys.setrecursionlimit()
로 설정할 수 있는 최댓값을 크게 변경했다고 하더라도, 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어지면, Segmentation fault
가 발생해 런타임 에러 이유로 SegFault를 받게됩니다.
소스 4. 소스 1의 최대 재귀 깊이를 매우 크게 변경한 소스
재귀의 깊이 제한이 10억까지 늘어났으니 입력으로 1억을 넣어도 올바르게 값을 구해야 합니다. 하지만, 이 깊이 제한은 채점 서버가 감당할 수 없는 값으로 Segmentation fault가 발생합니다.
sys.setrecursionlimit()
으로 변경한 최대 깊이 제한이 너무 작을 때도 RecursionError가 발생합니다.
소스 5. 소스 1의 최대 재귀 깊이를 1로 변경한 소스
소스 5와 같이 10**6
을 1**6
으로 오타를 낸 경우라면, sys.setrecursionlimit(1)
이 실행됩니다. 이 경우에도 RecursionError가 발생하며, 런타임 에러 메시지는 다음과 같습니다.
Traceback (most recent call last): File "Main.py", line 2, in <module> sys.setrecursionlimit(1) RecursionError: cannot set the recursion limit to 1 at the recursion depth 1: the limit is too low