RecursionError: maximum recursion depth exceeded
Funcția recursivă s-a apelat de prea multe ori fără să se oprească, iar Python a depășit limita de aproximativ 1000 de apeluri imbricate. Adaugă un caz de bază (de exemplu if n <= 1: return 1) și verifică dacă fiecare apel se apropie de el.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Fiecare apel de funcție ocupă un loc pe stiva de apeluri. Python limitează adâncimea acestei stive la aproximativ 1000 de niveluri (sys.getrecursionlimit()), ca să nu blocheze programul. Când o funcție recursivă continuă să se apeleze fără să se oprească, limita e atinsă și primești RecursionError: maximum recursion depth exceeded.
În 99% din cazuri problema e una din trei: lipsește cazul de bază (condiția care returnează fără să mai apeleze funcția), cazul de bază există, dar pasul recursiv sare peste el (de exemplu n - 2 pornind de la un număr impar, cu condiția n == 0), sau datele chiar sunt prea adânci (o listă de 5000 de elemente procesată element cu element).
În stiva de apeluri vei vedea aceeași linie repetată de sute de ori. Linia care contează e cea cu apelul recursiv: uită-te la argumentul trimis și întreabă-te dacă ajunge vreodată la cazul de bază.
De ce apare: cauzele frecvente
1Lipsește cazul de bază
def factorial(n):
return n * factorial(n - 1)
print(factorial(5))def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))Fără o condiție de oprire, factorial coboară la 0, -1, -2 și tot așa până la limita stivei. Cazul de bază n <= 1 oprește coborârea.
2Pasul sare peste cazul de bază
def pasi(n):
if n == 0:
return 0
return 1 + pasi(n - 2)
print(pasi(7))def pasi(n):
if n <= 0:
return 0
return 1 + pasi(n - 2)
print(pasi(7))Pornind de la 7, șirul e 7, 5, 3, 1, -1... și nu atinge niciodată exact 0. Cu n <= 0 condiția prinde și valorile negative.
3Argumentul nu se schimbă la apelul recursiv
def suma(lista):
if not lista:
return 0
return lista[0] + suma(lista)def suma(lista):
if not lista:
return 0
return lista[0] + suma(lista[1:])Funcția se reapelează cu aceeași listă, deci problema nu se micșorează niciodată. Fiecare apel trebuie să primească o problemă mai mică.
Repară eroarea, direct în pagină
Funcția factorial(n) de mai jos dă RecursionError: maximum recursion depth exceeded, pentru că nu are caz de bază. Repar-o ca să afișeze factorialele lui 5, 1 și 0: 120, 1 și 1.
def factorial(n):
return n * factorial(n - 1)
print(factorial(5))
print(factorial(1))
print(factorial(0))120 1 1
Indiciu
Adaugă la început o condiție care returnează 1 pentru n mai mic sau egal cu 1.
Reparația
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))
print(factorial(1))
print(factorial(0))De ce merge
O funcție recursivă are nevoie de două părți: cazul de bază, care răspunde direct, și pasul recursiv, care apropie problema de cazul de bază. Aici pasul exista (n - 1), dar nimic nu oprea coborârea, așa că apelurile continuau cu 0, -1, -2 până la limita stivei. Condiția n <= 1 oprește recursivitatea și acoperă și cazul factorial(0), care trebuie să fie 1. Cu n == 1 ai fi rezolvat 5 și 1, dar factorial(0) ar fi coborât din nou la infinit.
Alte forme ale mesajului
RecursionError: maximum recursion depth exceeded while calling a Python objectRecursionError: maximum recursion depth exceeded in comparison
Cum o eviți pe viitor
Înainte să scrii apelul recursiv, scrie cazul de bază și întreabă-te:
- ce intrare e atât de mică încât știu răspunsul direct?
- fiecare apel primește o intrare strict mai mică (n - 1, lista[1:], un subarbore)?
- condiția prinde și valorile pe care le pot sări (folosește
<=în loc de==când pasul e mai mare decât 1)?
Dacă datele pot fi foarte adânci (liste lungi, grafuri cu mii de noduri), scrie varianta iterativă cu o stivă sau o coadă explicită.
Întrebări frecvente
Pot rezolva eroarea cu sys.setrecursionlimit?
Doar dacă recursivitatea e corectă și datele sunt adânci. Dacă lipsește cazul de bază, o limită mai mare doar amână eroarea. În editorul din browser sys.setrecursionlimit nu e permis: stiva WebAssembly e mai mică și worker-ul s-ar putea opri. Varianta sigură e o buclă cu stivă explicită.
De ce limita e 1000 și nu mai mare?
E o valoare de siguranță aleasă de Python: fiecare nivel ocupă memorie, iar fără limită programul ar putea consuma toată stiva sistemului și s-ar opri brusc, fără niciun mesaj util.
Erori înrudite
RecursionError în merge sort: cazul de bază nu oprește lista cu un element Cazul de bază din merge sort verifică doar lista goală (if not lista), dar o listă cu un element se împarte în [] și [x], iar [x] se reîmparte la nesfârșit. Oprește recursivitatea la cel mult un element: if len(lista) <= 1: return lista. RecursionError la DFS: graful are un ciclu și lipsesc nodurile vizitate DFS-ul recursiv nu ține minte nodurile vizitate, iar graful are un ciclu (sau e neorientat: A-B înseamnă și B-A), deci se plimbă la nesfârșit până la RecursionError. Adaugă un set vazut și nu reintra în nodurile din el. TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' Ai adunat un număr cu rezultatul unei funcții care a returnat None: de obicei o funcție recursivă care, într-o ramură, face apelul recursiv fără return în fața lui. Pune return pe fiecare ramură a funcției. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
