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

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

---

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

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

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

최대 n = 997까지 작동 한 다음 "최대 재귀 깊이가 비교에서 초과했습니다" RuntimeError. 이것은 단지 스택 오버플로입니까? 주위를 돌아 다니는 방법이 있습니까?

---

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

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

---

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

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입니다.

또한보십시오:

• 파이썬 스크립트에서 스택 크기 설정
• Linux, Mac 및 Windows의 하드 재귀 제한은 무엇입니까?

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을 사용하십시오.)

---

물론 피보나치 수는 Binet 공식을 적용하여 O (n)으로 계산할 수 있습니다.

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

주석 작성자가 언급했듯이으로 인해 O (1)이 아니라 O (n)입니다 2**n. 또한 차이점은 하나의 값만 얻는 반면, 재귀를 사용하면 Fibonacci(n)해당 값까지의 모든 값을 얻는다는 것입니다.

---

"최대 재귀 깊이 초과"오류와 비슷한 문제가있었습니다. 내가 루핑하고있는 디렉토리의 손상된 파일로 인해 오류가 발생하고 있음을 발견했습니다 os.walk. 이 문제를 해결하는 데 문제가 있고 파일 경로로 작업중인 경우 파일이 손상되었을 수 있으므로 범위를 좁히십시오.

---

발전기를 사용 하시겠습니까?

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

위의 fib () 함수 : http://intermediatepythonista.com/python-generators

---

피보나치 수를 적게 얻으려면 행렬 방법을 사용할 수 있습니다.

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

numpy가 빠른 지수 알고리즘을 사용하기 때문에 빠릅니다. O (log n)로 답을 얻습니다. 그리고 정수만 사용하기 때문에 Binet의 공식보다 낫습니다. 그러나 모든 피보나치 수를 최대 n 개까지 원한다면 암기하여하는 것이 좋습니다.

---

많은 사람들이 재귀 제한을 늘리는 것이 좋은 해결책이지만 항상 제한이 있기 때문에 권장하지는 않습니다. 대신 반복 솔루션을 사용하십시오.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

---

@alex가 제안 했듯이 생성기 함수를 사용 하여이 작업을 수행 할 수 있습니다. 귀하의 질문에 해당하는 코드는 다음과 같습니다.

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0 """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error

---

피보나치 계산에 메모를 사용하여 재귀를 사용하여 훨씬 더 큰 숫자를 계산할 수있는 예제를 제공하고자합니다.

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

이것은 여전히 ​​재귀 적이지만 이전에 계산 한 피보나치 수를 다시 사용하는 대신 재사용 할 수있는 간단한 해시 테이블을 사용합니다.

---

import sys
sys.setrecursionlimit(1500)

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

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

참고 URL : https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it