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**61**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