백준에서 어떤 문제를 재귀를 통해 풀어보려 했다.
그리고 풀던 도중 확인한 것은 파이썬의 최대 재귀 깊이(maximum recursion depth)가 매우 작다는 것이다. 기본 값은 10^3로 확인했다.
이 문제를 어떻게 해결하는지 검색해보니 보통 최대한도 깊이를 변경해버리더라.
import sys
sys.setrecursionlimit(10**6)문제를 푸는데에 지장은 없겠지만 기본값을 바꿔가며 문제를 풀어야한다니 마음 한구석이 불편했다. 파이썬에서 기본 깊이를 이렇게 작게 설정한 이유가 있지 않을까.
재귀 깊이가 작은 이유
https://www.geeksforgeeks.org/python-handling-recursion-limit/
뭔가 검색할 때마다 검색결과에 자주 뜨는 사이트에서 답을 찾았다. 파이썬에서는 tail recursion optimization을 지원하지 않아서 재귀함수가 호출 될 때마다 stack frame이 쌓여 쉽게 stack overflow가 발생한다고 한다. 그래서 이를 방지하기 위해 재귀한도 깊이를 작게 설정했다고 한다.
Languages such as lisp and c/c++ have this sort of optimization. But, the Python interpreter doesn’t perform tail recursion optimization. Due to this, the recursion limit of python is usually set to a small value (approx, 10^4).
그런데 한가지 드는 의문이 있다. 내가 이해한 바로는 우선 일반적인 재귀와 tail recursion은 다르다.(여러 다른 블로그 참고 1 2 3)
tail recursion optimization은 tail recursion 형태가 아닌 다른 재귀의 형태에 대해선 적용될 수가 없다. 즉 tail recursion이 아닌 다른 재귀 형태에 대해선 파이썬이나 다른 언어들이나 똑같을 텐데 왜 하필 파이썬만 재귀한도 깊이가 작을까...
예를 들어
def fact(n):
if(n == 0):
return 1
return n * fact(n - 1)위와 같은 함수는 tail recursion이 아니니 optimization이 안되니까 파이썬이나 c/c++나 똑같이 재귀함수가 호출 될 때마다 stack frame이 쌓이는거 아닌가...? 똑같이 쌓이는데 왜 파이썬만 재귀한도가 작을까...
파이썬은 왜 tail recursion optimization을 지원 안하는가
그렇담 왜 파이썬은 저 기능을 지원하지 않는지 궁금했다.
https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion
첫번째 답변자 분이 친절하게도 귀도반로썸이 작성한 옛날 블로그글 링크까지 남겨주셨다. 한줄 요약은 파이썬스럽지 않고 디버깅도 어렵기 때문이라고 한다.
파이썬에서 재귀 쓰지 않고 풀기
크게 두가지 방법이 있는 것 같다.
tail recursion인 경우 셀프로 반복문(for, while)을 사용해서 tail recursion optimization을 하거나
여러개의 작은 문제로 나눠푸는 개념이 같은 동적프로그래밍 방식으로 바꿔 푸는 것이다.
이 부분에 대해선 조금 더 공부해봐야 할 것 같다.
