Was ist die maximale Rekursionstiefe und wie kann sie erhöht werden?

Question

Ich habe diese Endrekursive Funktion hier:

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

Es funktioniert bis n=997, dann bricht es einfach ab und gibt einen RecursionError: maximum recursion depth exceeded in comparison aus. Ist das einfach ein Stacküberlauf? Gibt es einen Weg, das zu umgehen?

Answer 1

RecursionError: maximale Rekursionstiefe bei Vergleich überschritten

Lösung :

Zunächst ist es besser zu wissen, dass Sie beim Ausführen einer rekursiven Funktion in Python mit einer großen Eingabe ( > 10^4) möglicherweise einen "maximale Rekursionstiefe überschritten Fehler" erhalten können.

Das sys-Modul in Python hat eine Funktion getrecursionlimit(), die die Rekursionstiefe in Ihrer Python-Version anzeigen kann.

import sys
print("Python Rekursionsbegrenzung = ", sys.getrecursionlimit())

Der Standardwert in einigen Versionen von Python liegt bei 1000 und in anderen bei 1500

Sie können diese Begrenzung ändern, aber es ist sehr wichtig zu wissen, dass bei zu großer Erhöhung ein Speicherüberlauffehler auftritt.

Seien Sie also vorsichtig, bevor Sie sie erhöhen. Sie können setrecursionlimit() verwenden, um diese Begrenzung in Python zu erhöhen.

import sys
sys.setrecursionlimit(3000)

Bitte folgen Sie diesem Link für weitere Informationen zu einigen Ursachen dieses Problems :

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

Answer 2

Wir können das mit dem @lru_cache Decorator und der setrecursionlimit() Methode tun:

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

Ausgabe

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151701125

Quelle

functools lru_cache

Answer 3

Wie @alex vorgeschlagen hat, könnten Sie eine Generator-Funktion verwenden, um dies sequentiell anstelle von rekursiv zu tun.

Hier ist der Äquivalent des Codes in Ihrer Frage:

def fib(n):
    def fibseq(n):
        """ Geben Sie iterativ die ersten n Fibonacci-Zahlen zurück, angefangen bei 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')  # -> keine Rekursionstiefe Fehler

Answer 4

Bearbeitung: 6 Jahre später habe ich realisiert, dass meine Aussage "Verwenden von Generatoren" leichtfertig war und die Frage nicht beantwortet hat. Entschuldigung dafür.

Ich vermute, meine erste Frage wäre: Brauchst du wirklich eine Änderung des Rekursionslimits? Wenn nicht, dann könnten meine Antwort oder eine der anderen Antworten, die sich nicht mit der Änderung des Rekursionslimits befassen, zutreffen. Andernfalls, wie bereits erwähnt, das Rekursionslimit mit sys.getrecursionlimit(n) überschreiben.

Generatoren verwenden?

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

fibs = fib() #scheint die einzige Möglichkeit zu sein, dass die folgende Zeile funktioniert, ist den unendlichen Generator einer Variablen zuzuweisen

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

for num in f:
        print num

Obige fib() Funktion angepasst von Einführung in Python-Generatoren.

Answer 5

Ich wollte Ihnen ein Beispiel für die Verwendung von Memoisierung geben, um Fibonacci zu berechnen, da dies Ihnen ermöglichen wird, signifikant größere Zahlen unter Verwendung von Rekursion zu berechnen:

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

Dies ist immer noch rekursiv, verwendet jedoch eine einfache Hashtabelle, die es ermöglicht, zuvor berechnete Fibonacci-Zahlen wiederzuverwenden, anstatt sie erneut zu berechnen.