Ik heb deze staart recursieve functie 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))
Het werkt tot n=997, dan breekt het en spuugt het gewoon een RecursionError: maximum recursion depth exceeded in comparison. Is dit gewoon een stack overflow? Is er een manier om er omheen te komen?
Antwoord 1, autoriteit 100%
Het is een bescherming tegen een stack-overflow, ja. Python (of liever, de CPython-implementatie) optimaliseert staartrecursie niet, en ongebreidelde recursie veroorzaakt stackoverflows. U kunt de recursielimiet controleren met sys.getrecursionlimit:
import sys
print(sys.getrecursionlimit())
en wijzig de recursielimiet met sys.setrecursionlimit :
sys.setrecursionlimit(1500)
maar dit is gevaarlijk — de standaardlimiet is een beetje conservatief, maar Python-stackframes kunnen behoorlijk groot zijn.
Python is geen functionele taal en staartrecursie is geen bijzonder efficiënte techniek. Het algoritme iteratief herschrijven, indien mogelijk, is over het algemeen een beter idee.
Antwoord 2, autoriteit 24%
Het lijkt erop dat je gewoon een hogere recursiediepte moet instellen:
import sys
sys.setrecursionlimit(1500)
Antwoord 3, autoriteit 10%
Het is om een stack overflow te voorkomen. De Python-interpreter beperkt de diepten van recursie om u te helpen oneindige recursie te voorkomen, wat resulteert in stack-overflows.
Probeer de recursielimiet te verhogen (sys.setrecursionlimit) of herschrijf uw code zonder recursie.
Van de Python-documentatie:
sys.getrecursionlimit()Retourneer de huidige waarde van de recursielimiet, de maximale diepte van de Python-interpreterstack. Deze limiet voorkomt dat oneindige recursie een overloop van de C-stack veroorzaakt en Python laat crashen. Het kan worden ingesteld door
setrecursionlimit().
Antwoord 4, autoriteit 7%
Als u vaak de recursielimiet moet wijzigen (bijvoorbeeld bij het oplossen van programmeerpuzzels), kunt u een eenvoudige contextmanager als volgt:
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)
Om vervolgens een functie met een aangepaste limiet aan te roepen, kunt u het volgende doen:
with recursionlimit(1500):
print(fib(1000, 0))
Bij het verlaten van de hoofdtekst van het with-statement wordt de recursielimiet hersteld naar de standaardwaarde.
Antwoord 5, autoriteit 3%
resource.setrlimit moet ook worden gebruikt om de stapelgrootte te vergroten en segfault te voorkomen
De Linux-kernel beperkt de stapel processen.
Python slaat lokale variabelen op de stapel van de interpreter op, en dus neemt recursie stapelruimte van de interpreter in beslag.
Als de Python-interpreter de stacklimiet probeert te overschrijden, maakt de Linux-kernel het segmentatiefout.
De grootte van de stapellimiet wordt bepaald met de systeemaanroepen getrlimit en setrlimit.
Python biedt toegang tot die systeemaanroepen via de module resource.
sys.setrecursionlimit vermeld b.v. op https://stackoverflow.com/a/3323013/895245 verhoogt alleen de limiet die de Python-interpreter zelf aan zijn eigen stackgrootte, maar het overschrijdt niet de limiet die door de Linux-kernel aan het Python-proces wordt opgelegd.
Voorbeeldprogramma:
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)
Natuurlijk, als je de setrlimit blijft verhogen, zal je RAM uiteindelijk opraken, waardoor je computer langzamer tot stilstand komt vanwege swapgekte, of Python doodt via de OOM Killer.
Vanuit bash kun je de stapellimiet (in kb) zien en instellen met:
ulimit -s
ulimit -s 10000
De standaardwaarde voor mij is 8 MB.
Zie ook:
- Stackgrootte instellen in een python-script
- Wat is de harde recursie limiet voor Linux, Mac en Windows?
Getest op Ubuntu 16.10, Python 2.7.12.
Antwoord 6, autoriteit 2%
Gebruik een taal die tail-call-optimalisatie garandeert. Of gebruik iteratie. Je kunt ook schattig worden met decorateurs.
Antwoord 7, autoriteit 2%
Ik had een soortgelijk probleem met de fout “Maximale recursiediepte overschreden”. Ik ontdekte dat de fout werd veroorzaakt door een beschadigd bestand in de map die ik doorliep met os.walk. Als u problemen ondervindt bij het oplossen van dit probleem en u werkt met bestandspaden, moet u het beperken, aangezien het een beschadigd bestand kan zijn.
Antwoord 8
Ik realiseer me dat dit een oude vraag is, maar voor degenen die dit lezen, raad ik af om recursie te gebruiken voor dit soort problemen – lijsten zijn veel sneller en voorkomen recursie volledig. Ik zou dit implementeren als:
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])
(Gebruik n+1 in xrange als je je fibonacci-reeks begint te tellen vanaf 0 in plaats van 1.)
Antwoord 9
Natuurlijk kunnen Fibonacci-getallen worden berekend in O(n) door de Binet-formule:
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))
Zoals de commentatoren opmerken, is het niet O(1) maar O(n) vanwege 2**n. Een verschil is ook dat je maar één waarde krijgt, terwijl je met recursie alle waarden van Fibonacci(n) tot aan die waarde krijgt.
Antwoord 10
Als je maar een paar Fibonacci-getallen wilt krijgen, kun je de matrixmethode gebruiken.
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
Het is snel omdat numpy het snelle exponentiatie-algoritme gebruikt. Je krijgt antwoord in O(log n). En het is beter dan de formule van Binet omdat het alleen gehele getallen gebruikt. Maar als je alle Fibonacci-getallen tot n wilt, dan kun je dit beter uit het hoofd leren.
Antwoord 11
Zoals @alex suggereerde, zou je een generatorfunctie om dit sequentieel te doen in plaats van recursief.
Dit is het equivalent van de code in uw vraag:
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
Antwoord 12
We kunnen dat doen met behulp van @lru_cache decorator en setrecursionlimit() methode:
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))
Uitvoer
3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125
Bron
Antwoord 13
Bewerken: 6 jaar later realiseerde ik me dat mijn "Gebruik generatoren" was spottend en gaf geen antwoord op de vraag. Mijn excuses.
Ik denk dat mijn eerste vraag zou zijn: is het echt nodig om de recursielimiet te wijzigen? Zo niet, dan zijn misschien mijn of een van de andere antwoorden die niet gaan over het wijzigen van de recursielimiet van toepassing. Anders, zoals aangegeven, overschrijft u de recursielimiet met sys.getrecursionlimit(n).
Generatoren gebruiken?
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
Boven fib() functie aangepast van Inleiding tot Python-generatoren.
Antwoord 14
Velen bevelen aan dat het verhogen van de recursielimiet een goede oplossing is, maar dat is niet zo omdat er altijd een limiet zal zijn. Gebruik in plaats daarvan een iteratieve oplossing.
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
Antwoord 15
Ik wilde je een voorbeeld geven van het gebruik van memoisatie om Fibonacci te berekenen, omdat je hiermee aanzienlijk grotere getallen kunt berekenen met recursie:
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))
Dit is nog steeds recursief, maar gebruikt een eenvoudige hashtabel die het hergebruik van eerder berekende Fibonacci-nummers mogelijk maakt in plaats van ze opnieuw te doen.
Antwoord 16
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))
Antwoord 17
We zouden ook een variant van dynamisch programmeren van onderop kunnen gebruiken
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))
Antwoord 18
Ik weet niet zeker of ik iemand herhaal, maar enige tijd geleden schreef een goede ziel Y-operator voor recursief genaamde functie zoals:
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
en dan moet de recursieve functie de vorm hebben:
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)
voor Fibonacci-getallen ziet uw functie er als volgt uit:
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))
uitvoer:
..684684301719893411568996526838242546875
(eigenlijk tonen van cijfers)
Antwoord 19
RecursionError: maximale recursiediepte overschreden in vergelijking
Oplossing:
Eerst is het beter om te weten dat wanneer u een recursieve functie in Python uitvoert op een grote invoer ( > 10^4), u een maximale recursiediepte overschreden fout kunt tegenkomen.
De sys-module in Python heeft een functie getrecursionlimit() die de recursielimiet in uw Python-versie kan weergeven.
import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())
De standaard in sommige versies van Python is 1000 en in andere was dit 1500
U kunt deze beperking wijzigen, maar het is erg belangrijk om te weten dat als u deze erg verhoogt, u een geheugenoverloopfout krijgt.
Wees dus voorzichtig voordat u het verhoogt. Je kunt setrecursionlimit() gebruiken om deze beperking in Python te verhogen.
import sys
sys.setrecursionlimit(3000)
Volg deze link voor meer informatie over iets dat dit probleem veroorzaakt: