[python] 파이썬에서 최대 재귀 깊이는 얼마이며 어떻게 증가합니까?

이 꼬리 재귀 기능이 있습니다.

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

그것은 작동합니다 n=997, 그리고 그것은 그냥 깨고 밖으로 뱉어 RecursionError: maximum recursion depth exceeded in comparison. 이것이 스택 오버플로입니까? 그것을 해결할 방법이 있습니까?

답변

스택 오버플로에 대한 보호입니다. 파이썬 (또는 CPython 구현)은 테일 재귀를 최적화하지 않으며 브 래딩되지 않은 재귀로 인해 스택 오버플로가 발생합니다. 으로 재귀 한계를 확인하고으로 재귀 한계를 sys.getrecursionlimit변경할 수 sys.setrecursionlimit있지만 그렇게하는 것은 위험합니다. 표준 한계는 약간 보수적이지만 파이썬 스택 프레임은 상당히 클 수 있습니다.

파이썬은 기능적 언어가 아니며 꼬리 재귀는 특히 효율적인 기술이 아닙니다. 가능한 경우 알고리즘을 반복적으로 다시 작성하는 것이 일반적으로 더 좋습니다.

답변

더 높은 재귀 깊이 를 설정 해야하는 것처럼 보입니다 .

import sys
sys.setrecursionlimit(1500)

답변

스택 오버플로를 피해야합니다. Python 인터프리터는 재귀 깊이를 제한하여 무한 재귀를 피하여 스택 오버플로를 발생시킵니다. 재귀 제한을 늘리 sys.setrecursionlimit거나 ( ) 재귀없이 코드를 다시 작성하십시오.

로부터 파이썬 문서 :

sys.getrecursionlimit()

파이썬 인터프리터 스택의 최대 깊이 인 재귀 한계의 현재 값을 반환합니다. 이 제한은 무한 재귀가 C 스택의 오버플로를 유발하고 Python을 충돌시키는 것을 방지합니다. 로 설정할 수 있습니다 setrecursionlimit().

답변

재귀 제한을 자주 변경해야하는 경우 (예 : 프로그래밍 퍼즐을 풀 때) 다음 과 같이 간단한 컨텍스트 관리자를 정의 할 수 있습니다 .

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit
        self.old_limit = sys.getrecursionlimit()

    def __enter__(self):
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

그런 다음 사용자 정의 한계를 가진 함수를 호출하려면 다음을 수행하십시오.

with recursionlimit(1500):
    print(fib(1000, 0))

with명령문 본문에서 나갈 때 재귀 한계가 기본값으로 복원됩니다.

답변

테일 콜 최적화를 보장하는 언어를 사용하십시오. 또는 반복을 사용하십시오. 또는 데코레이터로 귀여워하십시오 .

답변

resource.setrlimit 또한 스택 크기를 늘리고 segfault를 방지하는 데 사용해야합니다.

리눅스 커널 은 프로세스 스택을 제한한다 .

파이썬은 지역 변수를 인터프리터의 스택에 저장하므로 재귀는 인터프리터의 스택 공간을 차지합니다.

파이썬 인터프리터가 스택 제한을 초과하려고 시도하면 Linux 커널은이를 분할 오류로 만듭니다.

스택 제한 크기는 getrlimit및 setrlimit시스템 호출로 제어됩니다 .

파이썬은 resource모듈을 통해 이러한 시스템 호출에 대한 액세스를 제공 합니다.

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

물론 ulimit를 계속 늘리면 RAM이 부족하여 스왑 광기로 인해 컴퓨터가 정지되거나 OOM Killer를 통해 Python을 종료합니다.

bash에서 다음을 사용하여 스택 제한 (KB)을보고 설정할 수 있습니다.

ulimit -s
ulimit -s 10000

저의 기본값은 8Mb입니다.

또한보십시오:

Ubuntu 16.10, Python 2.7.12에서 테스트되었습니다.

답변

나는 이것이 오래된 질문이라는 것을 알고 있지만 읽는 사람들에게는 이것과 같은 문제에 대해 재귀를 사용하지 않는 것이 좋습니다. 목록이 훨씬 빠르며 재귀를 완전히 피하십시오. 나는 이것을 다음과 같이 구현할 것이다 :

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(피보나치 수열을 1이 아닌 0부터 시작하면 xrange에서 n + 1을 사용하십시오.)