Python 재귀함수의 최대깊이

programmers 에서 알고리즘 문제를 풀다가 runtime error를 마주했다.

 

 

재귀함수를 사용한 트리 탐색 문제였는데 딱히 무한루프가 걸릴 부분은 없는 것 같아서 이런저런 고민을 했다.

문제의 제한조건은 트리 노드 개수 2 이상 300,000 이하.

 

알고보니 Python에서는 Recursion 호출 개수에 제한이 걸려있다고 한다.

 

docs.python.org/2/library/sys.html?highlight=setrecursionlimit#sys.setrecursionlimit

28.1. sys — System-specific parameters and functions — Python 2.7.18 documentation

 

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

 

sys.setrecursionlimit(limit)

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

 

재귀함수의 무한 소출로 인한  stack over flow와 crash를 막기 위해서 recursion limit이 설정되어있다고 한다.

getrecursionlimit 함수를 통해 확인하고 setrecusrionlimit 을 통해 limit을 변경할 수 있다.

 

default recursion limit을 확인해보았다.

window에 설치한 python 3.9에서 기본 limit이 1000으로 설정되어 있는 것을 확인하였다.

 

recursion depth limit을 넘어서면 아래와 같은 error가 발생한다.

Error message : RecursionError : maximum recursion depth exceeded in comparision

 

 문제 체점과정에서도 기본 recursion limit이 1000으로 설정되어있었다면 트리 탐색과정에서 depth가 1000이 넘어갔을 때 위과 같은 error 가 발생했을 것이다.

문제 풀이 상단에 아래와 같이 입력해 주면, runtime error 가 발생했던 4개의 case를 통과할 수 있었다.

import sys
sys.setrecursionlimit(300000)