Python의 최대 재귀 깊이는 얼마이며, 어떻게 하면 재귀 깊이를 늘릴 수 있습니까?

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 것은은 ?? ?? ?? ?? ? ???걸걸피 ?법 ?? ????

스택 오버플로에 대한 보호 장치입니다.Python(또는 CPython 구현)은 테일 재귀를 최적화하지 않으며, 구속되지 않은 재귀는 스택 오버플로를 일으킵니다.재귀 제한은 다음과 같이 확인할 수 있습니다.

import sys
print(sys.getrecursionlimit())

를 사용하여 재귀 제한을 변경합니다.

sys.setrecursionlimit(1500)

하지만 그렇게 하는 것은 위험합니다. 표준 제한은 다소 보수적이지만 Python 스택 프레임은 상당히 클 수 있습니다.

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

재귀 깊이를 높게 설정하면 되는 것 같습니다.

import sys
sys.setrecursionlimit(1500)

이치노Python 인터프리터는 재귀 깊이를 제한하여 무한 재귀를 방지하여 스택 오버플로우를 발생시킵니다. 제한재귀 제한)( 제한)을 클릭합니다.sys.setrecursionlimit을 사용하다

Python 문서:

sys.getrecursionlimit()

Python 인터프리터 스택의 최대 깊이인 재귀 제한의 현재 값을 반환합니다.이 제한은 무한 재귀로 인해 C 스택의 오버플로가 발생하여 Python이 충돌하는 것을 방지합니다.에 의해 설정할 수 있습니다.

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

import sys

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

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

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

그런 다음 사용자 지정 제한이 있는 함수를 호출하려면 다음을 수행할 수 있습니다.

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

「 」의with재귀 제한이 기본값으로 복원됩니다.

추신: 재귀 제한의 큰 값에 대해 Python 프로세스의 스택 크기를 늘릴 수도 있습니다.은 ★★★★★★★★★ulimit 또는 " " " "limits.conf(5)예를 들어 파일입니다.

resource.setrlimit하려면 segfault를 .

Linux 커널은 프로세스 스택을 제한합니다.

Python은 로컬 변수를 인터프리터의 스택에 저장하기 때문에 재귀가 인터프리터의 스택 공간을 차지합니다.

Python 인터프리터가 스택 제한을 초과하려고 하면 Linux 커널에 의해 분할 오류가 발생합니다.

는, 「스택 제한」, 「스택 제한」으로됩니다.getrlimit ★★★★★★★★★★★★★★★★★」setrlimit시스템 콜

은 Python을 이러한 액세스를 합니다.resource★★★★★★ 。

sys.setrecursionlimit예를 들어 https://stackoverflow.com/a/3323013/895245에서 언급되는 것은 Python 인터프리터가 자체 스택크기에 부과하는 제한을 늘릴 뿐 Python 프로세스에서 Linux 커널에 의해 부과되는 제한에는 영향을 미치지 않습니다.

프로그램 예:

main.py

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)

계속 setrlimitRAM은 결국 고갈되고 스왑 광기로 인해 컴퓨터가 중지되거나 OOM Killer를 통해 Python을 죽일 수 있습니다.

bash에서 스택 제한(KB)을 표시 및 설정할 수 있습니다.

ulimit -s
ulimit -s 10000

기본값은 8Mb입니다.

다음 항목도 참조하십시오.

• python 스크립트에서 스택 크기 설정
• 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을 사용합니다).

"최대 재귀 깊이가 초과되었습니다."는, 「」로 하고 되고 있는 것을 했습니다.os.walk이 문제를 해결하는 데 문제가 있고 파일 경로를 사용하는 경우 파일이 손상되었을 수 있으므로 파일 경로를 좁혀야 합니다.

물론 피보나치 수치는 비넷 공식을 적용하여 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입니다. O(1)가 O(n)이기 입니다.2**n 다른 하나의 값만 수 , ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ㄴ, ᄃ의 모든 값을 수 Fibonacci(n)그 값까지.

소수의 피보나치 숫자만 가져오려면 행렬 방법을 사용할 수 있습니다.

from numpy import matrix

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

numpy는 빠른 지수화 알고리즘을 사용하기 때문에 빠르다.O(log n)에서 답을 얻을 수 있습니다.그리고 그것은 정수만을 사용하기 때문에 비넷의 공식보다 낫다.그러나 만약 당신이 모든 피보나치 숫자를 n까지 원한다면, 암기하는 것이 좋습니다.

, 하다, 하다, 하다, 하다, 할 수 있어요.@lru_cachesetrecursionlimit()★★★★

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

산출량

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

원천

functools lru_cache

@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

RecursionError: 최대 재귀 깊이가 비교에서 초과되었습니다.

해결책:

우선 Python에서 큰 입력(> 10^4)으로 재귀 함수를 실행하면 "최대 재귀 깊이 초과 오류"가 발생할 수 있습니다.

Python의 sys 모듈에는 python 버전의 재귀 제한을 표시할 수 있는 getrecursionlimit() 함수가 있습니다.

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

Python의 일부 버전에서는 기본값이 1000이고 다른 버전에서는 1500입니다.

이 제한을 변경할 수 있지만 너무 많이 늘리면 메모리 오버플로 오류가 발생한다는 것을 알아야 합니다.

그러니까 늘리기 전에 조심하세요.Python에서는 setrecursionlimit()를 사용하여 이 제한을 늘릴 수 있습니다.

import sys
sys.setrecursionlimit(3000)

이 문제의 원인에 대한 자세한 내용은 다음 링크를 참조하십시오.

https://elvand.com/quick-sort-binary-search/

편집: 6년 후 "Use generators"가 경솔하다는 것을 깨닫고 질문에 답하지 않았습니다.죄송합니다.

첫 번째 질문은 '재귀 제한을 정말 변경할 필요가 있는가?' 입니다.그렇지 않은 경우 재귀 제한 변경에 대해 다루지 않는 다른 답변이 적용될 수 있습니다. 않으면 앞서한 바와 을 덮어씁니다.재귀 제한은 재귀 제한으로 .sys.getrecursionlimit(n).

발전기 사용?

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()Python Generators 소개에서 수정된 함수입니다.

많은 사람들이 재귀 제한을 늘리는 것이 좋은 해결책이라고 권장하지만 항상 제한이 있기 때문에 좋은 해결책은 아닙니다.대신 반복적인 솔루션을 사용합니다.

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

메모화를 사용하여 Fibonacci를 계산하는 예를 들어보겠습니다.이 예에서는 재귀를 사용하여 훨씬 더 큰 숫자를 계산할 수 있습니다.

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))

이는 여전히 재귀적이지만, 는 이전에 계산된 Fibonacci 숫자를 다시 사용하는 대신 재사용할 수 있는 단순한 해시 테이블을 사용합니다.

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))

또한 동적 프로그래밍 보텀업 접근 방식을 사용할 수 있습니다.

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))

내가 누군가를 반복하고 있는지는 모르겠지만, 얼마 전 어떤 좋은 영혼은 반복적으로 호출되는 함수에 대해 Y 연산자를 썼다:

def tail_recursive(func):
  y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
  def wrap_func_tail(*args):
    out = y_operator(*args)
    while callable(out): out = out()
    return out
  return wrap_func_tail

재귀 함수에는 형식이 필요합니다.

def my_recursive_func(g):
  def wrapped(some_arg, acc):
    if <condition>: return acc
    return g(some_arg, acc)
  return wrapped

# and finally you call it in code

(tail_recursive(my_recursive_func))(some_arg, acc)

Fibonacci 숫자의 경우 함수는 다음과 같습니다.

def fib(g):
  def wrapped(n_1, n_2, n):
    if n == 0: return n_1
    return g(n_2, n_1 + n_2, n-1)
  return wrapped

print((tail_recursive(fib))(0, 1, 1000000))

출력:

..684684301719893411568996526838242546875

(실제로 디짓톤)

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