[Python] RecursionError

RecursionError란?

• Recursion(재귀) + Error(오류)
• 보통 Python이 정한 최대 재귀 깊이를 초과할 때 발생함.
• 최대 재귀 깊이는 sys.getrecursionlimit()로 확인 가능
• BOJ 채점 서버의 최대 재귀 깊이는 1000임.

힝 입니다

해결 방법

1. 재귀 함수 사용하지 않기

• DFS를 이용했다면 BFS를 이용하자.
• 다이나믹 프로그래밍을 재귀로 구현했다면 반복문으로 구현하자.

예시) Factorial 함수 구현

# 코드 1: 재귀 함수 사용
def Factorial(n):
    if n == 1:
        return 1
    else:
        return n * Factorial(n-1)


# 코드 2: for문 사용
def Factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

• 코드 1: RecursionError 발생 가능
• 코드 2: 잘 돌아감~~^_^
  (+ 참고로 Factorial 함수는 math.factorial() > for문 > 재귀함수 순으로 빠르다.)

2. 최대 재귀 깊이 변경

• sys.setrecursionlimit() 함수로 변경이 가능하다.

예시) 최대 재귀 깊이를 10^6으로 변경

import sys
sys.setrecursionlimit(10**6) # 최대 재귀 깊이를 1,000,000으로 설정
def calc(n):
    if n == 0:
        return 0
    else:
        return n + calc(n-1)

n = int(input())
print(calc(n))

• 단, 너무 깊으면 Segmentation fault가 발생할 수 있다.
• 또한 너무 얕아도 RecursionError가 발생할 수 있다.

---

참고 자료

• BOJ 도움말 > 런타임 에러 (RecursionError)
• Python 팩토리얼 속도 비교

관련 문제

• https://www.acmicpc.net/problem/1676