[Python] 재귀 호출 깊이 제한 초과 에러 (RecursionError: maximum recursion depth exceeded)

 

RecursionError: maximum recursion depth exceeded는 파이썬에서 재귀 호출의 깊이 제한을 초과했을 때 발생하는 에러이다.

파이썬은 기본적으로 재귀 호출의 깊이에 제한을 두고 있으며, 이 한계를 초과하면 해당 에러가 발생한다.

일반적으로 파이썬은 재귀 호출의 최대 깊이를 1000으로 제한하고 있다.

이러한 제한은 스택의 한계를 넘어갔을 때, 스택 오버플로우를 방지하기 위한 것이다.

깊은 단계의 재귀 호출이 필요한 경우, 이 한계를 조절할 수 있다.

하지만 주의를 기울여야 하는데 이유는 크게 세 가지로 나눌 수 있다.

1. 스택 오버플로우
   재귀 호출은 호출 스택을 사용한다.
   스택은 제한된 메모리를 사용하며, 깊은 재귀 호출을 하면 스택이 넘치는 스택 오버플로우가 발생할 수 있다.
   스택 오버플로우는 프로그램을 비정상적으로 종료시키는 원인이 된다.
2. 메모리 사용
   깊은 재귀 호출을 허용하면 메모리 사용량이 급격히 증가할 수 있다.
   각 재귀 호출은 메모리를 차지하므로, 제한 없이 깊이를 늘리면 시스템의 메모리를 과도하게 소비할 수 있다.
3. 효율성
   재귀 호출이 깊어질수록 함수 호출 및 복귀에 따른 오버헤드가 증가한다.
   이는 성능 저하로 이어질 수 있다.
   (오버헤드: 오버헤드는 어떤 작업을 수행하는 과정에서 추가적으로 발생하는 비용이나 부가 작업을 의미. 재귀 호출에서의 오버헤드는 함수 호출 및 복귀 과정에서 필요한 작업으로, 각 재귀 호출이 호출 스택에 프레임을 추가하고 제거하는 과정에서 발생. 재귀 호출이 깊어질수록 이러한 오버헤드가 늘어나며, 이는 성능 저하로 이어질 수 있음.)

따라서 재귀 호출 깊이를 늘리는 것은 주의를 기울여야 한다.

깊이를 늘리는 대신 다른 방법을 고려하거나, 재귀를 반복문으로 변경하거나, 동적 계획법(Memoization) 등을 사용하는 것이 더 안전하며 효율적일 수 있다.

주의를 기울이지 않고 재귀 호출 깊이를 무작정 높이는 것은 예기치 못한 문제를 초래할 수 있다.

 

예시를 통해 RecursionError: maximum recursion depth exceeded가 발생하는 원인과 해결 방법 세 가지를 알아보자.

---

예시와 문제점

사용자로부터 \(n\), \(k\)값을 입력받아 이항계수를 구하는 코드를 통해 살펴보자.

먼저 코드는 아래와 같다.

코드는 재귀 함수와 동적 계획법을 다룬 저번 포스팅에서 가져와 일부를 수정한 코드이다.

class BinomialCoefficientCalculator:
    def __init__(self):
        self.memo = {}

    def calculate_recursive(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_recursive(n - 1, k - 1) + self.calculate_recursive(n - 1, k)

        return result

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # Recursive 방식의 계산
    calculator_recursive = BinomialCoefficientCalculator()
    result_recursive = calculator_recursive.calculate_recursive(n, k)

    # 결과 출력
    print(f"{n}C{k} (Recursive) = {result_recursive}")

이제 입력으로 \(n=1000\), \(k=500\)을 넣어보자.

에러가 발생하는 것을 확인할 수 있다.

RecursionError: maximum recursion depth exceeded in comparison

위의 입력으로 코드가 돌아갈 때, 재귀 호출의 깊이가 매우 깊어져서 RecursionError가 발생하고 있다.

 

그럼 이제 이 문제를 해결할 수 있는 방법 세 가지를 알아보자.

---

문제 해결 방법

RecursionError을 해결하는 방법 세 가지를 살펴보자.

각 예시 코드를 위의 이항계수 계산하는 코드에 넣고 

1. 재귀 호출 깊이 제한 변경

가장 쉬운 방법으로는 sys.setrecursionlimit을 사용하여 재귀 호출 깊이 제한을 늘리는 것이다.

그러나 이 방법은 스택 오버플로우의 가능성이 있으므로 사용에 주의하자.

import sys

sys.setrecursionlimit(3000)  # 예시: 재귀 깊이 제한을 높임

위 코드를 추가하면 재귀 깊이를 원하는 숫자(위의 코드는 3000)만큼 늘릴 수 있다.

 

아래 코드처럼 써서 사용할 수 있다.

import sys

class BinomialCoefficientCalculator:
    def __init__(self):
        self.memo = {}

    def calculate_recursive(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_recursive(n - 1, k - 1) + self.calculate_recursive(n - 1, k)

        return result

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 재귀 깊이 제한을 높임
    sys.setrecursionlimit(3000)

    # Recursive 방식의 계산 및 시간 측정
    calculator_recursive = BinomialCoefficientCalculator()
    result_recursive = calculator_recursive.calculate_recursive(n, k)

    # 결과 및 시간 출력
    print(f"{n}C{k} (Recursive) = {result_recursive}")

2. 반복문 사용

재귀 호출 대신 반복문을 사용하여 계산하는 방법으로 안전하고 효율적이다.

def calculate_iterative(self, n, k):
    result = 1
    for i in range(1, k+1):
        result *= (n - i + 1) / i
    return int(result)

위 코드처럼 재귀 함수를 사용하는 대신 반복문을 사용하여 계산을 할 수 있다.

 

아래 코드처럼 써서 해결 가능하다.

class BinomialCoefficientCalculator:
    def calculate_iterative(self, n, k):
        result = 1
        for i in range(1, k+1):
            result *= (n - i + 1) / i
        return int(result)

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 반복문 방식의 계산
    calculator_iterative = BinomialCoefficientCalculator()
    result_iterative = calculator_iterative.calculate_iterative(n, k)

    # 결과 출력
    print(f"{n}C{k} (Iterative) = {result_iterative}")

3. 동적 계획법 사용 (Memoization)

중복 계산을 피하기 위해 메모이제이션을 사용하여 동적 계획법을 적용할 수 있다.

Memoization은 이미 계산한 값을 저장하고 필요할 때마다 사용하여 중복 계산을 피한다.

def calculate_memoized(self, n, k):
    # 기저 조건: k가 0이거나 k가 n과 같을 때
    if k == 0 or k == n:
        return 1

    # 이미 계산된 값이 있다면 바로 반환
    if (n, k) in self.memo:
        return self.memo[(n, k)]

    # 이항 계수의 성질을 이용하여 재귀적으로 계산
    result = self.calculate_memoized(n - 1, k - 1) + self.calculate_memoized(n - 1, k)

    # 결과를 memo에 저장
    self.memo[(n, k)] = result

    return result

 

이 방법에 대한 전체 코드와 아이디어 및 자세한 설명은 재귀 함수를 사용하여 이항계수를 계산하는 이 포스팅을 참고하자.