[TIL] 10월 25일: 파이썬 기본 재귀함수 깊이

Jung·2021년 10월 25일

목록 보기

34/77

Python RecursionError

백준 11050번을 풀다가 RecursionError에 빠졌다. 이에 대해 알아보았는데 아래와 같다.
RecursionError는 재귀와 관련된 에러다. 이 에러는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊을 때 발생한다. Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있다.

BOJ(백준)의 채점 서버에서 이 값은 1,000으로 되어 있다.

재귀 깊이를 1,000보다 작게 테스트 케이스를 넣어 실행을 시키면 RecursionError가 뜨지 않고 잘 실행이 되었다. 하지만 아래 코드로 제출했을 때 에러가 떴다 🙀

n, k = map(int, input().split())


def factorial(a):
    if a == 1:
        return 1

    return a * factorial(a-1)


print(factorial(n) // (factorial(k) * factorial(n-k)))

그래서 python sys 모듈에 있는 setrecursionlimit 메소드를 사용해 해결하려고 했다. 아래와 같은 방식으로 최대 재귀함수의 깊이를 원하는 만큼 설정할 수 있다.

import sys
sys.setrecursionlimit(10**5)  # 100000

n, k = map(int, input().split())


def factorial(a):
    if a == 1:
        return 1

    return a * factorial(a-1)


print(factorial(n) // (factorial(k) * factorial(n-k)))

하지만 또 내게 다가온 시련

메모리 초과가 떠버렸다. 그래서 재귀를 포기하고 반복문을 사용한 코드로 변경했다.

n, k = map(int, input().split())


def factorial(a):
    result = 1
    for i in range(1, a + 1):
        result *= i
    return result


print(factorial(n) // (factorial(k) * factorial(n-k)))

결과는...!