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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Merge sort împarte lista în două jumătăți, le sortează recursiv și le interclasează. Recursivitatea se oprește când lista e atât de mică încât e deja sortată: cel mult un element.
Dacă scrii if len(lista) == 0 (sau if not lista), o listă cu un element trece de cazul de bază. Mijlocul este 1 // 2 = 0, deci jumătățile sunt [] și [x]. Jumătatea din dreapta e aceeași listă cu un element, care se împarte din nou la fel, la nesfârșit, până la RecursionError: maximum recursion depth exceeded.
Aceeași problemă apare la quicksort când pivotul rămâne într-una din părți ([x for x in v if x <= pivot] include pivotul): dacă toate elementele sunt egale, partea nu se micșorează niciodată. În stiva de apeluri vei vedea linia cu apelul recursiv repetată de sute de ori.
De ce apare: cauzele frecvente
1Cazul de bază prinde doar lista goală
def merge_sort(v):
if not v:
return v
m = len(v) // 2
return interclaseaza(merge_sort(v[:m]), merge_sort(v[m:]))def merge_sort(v):
if len(v) <= 1:
return v
m = len(v) // 2
return interclaseaza(merge_sort(v[:m]), merge_sort(v[m:]))Pentru len(v) == 1, v[m:] este tot v, deci problema nu scade. Cu <= 1 lista de un element e returnată direct.
2Quicksort cu pivotul inclus într-o parte
def quick(v):
if len(v) <= 1:
return v
p = v[0]
return quick([x for x in v if x <= p]) + quick([x for x in v if x > p])def quick(v):
if len(v) <= 1:
return v
p = v[0]
mici = [x for x in v[1:] if x < p]
egale = [x for x in v if x == p]
mari = [x for x in v[1:] if x > p]
return quick(mici) + egale + quick(mari)În varianta greșită, [x for x in v if x <= p] conține mereu pivotul; dacă toate elementele sunt ≤ pivot, lista nu se micșorează. Separând elementele egale, ambele apeluri primesc liste strict mai mici.
Repară eroarea, direct în pagină
Funcția merge_sort(v) sortează prețurile prin interclasare, dar dă RecursionError: maximum recursion depth exceeded. Funcția interclaseaza e corectă. Repară cazul de bază ca programul să afișeze [3, 8, 15, 21, 42], [7] și [].
def interclaseaza(a, b):
rez, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
rez.append(a[i])
i += 1
else:
rez.append(b[j])
j += 1
return rez + a[i:] + b[j:]
def merge_sort(v):
if not v:
return v
m = len(v) // 2
return interclaseaza(merge_sort(v[:m]), merge_sort(v[m:]))
print(merge_sort([21, 3, 42, 8, 15]))
print(merge_sort([7]))
print(merge_sort([]))[3, 8, 15, 21, 42] [7] []
Indiciu
O listă cu un singur element este deja sortată și nu trebuie împărțită mai departe.
Reparația
def interclaseaza(a, b):
rez, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
rez.append(a[i])
i += 1
else:
rez.append(b[j])
j += 1
return rez + a[i:] + b[j:]
def merge_sort(v):
if len(v) <= 1:
return v
m = len(v) // 2
return interclaseaza(merge_sort(v[:m]), merge_sort(v[m:]))
print(merge_sort([21, 3, 42, 8, 15]))
print(merge_sort([7]))
print(merge_sort([]))De ce merge
Orice listă ajunge prin împărțiri la bucăți de un element. Cu if not v, o listă [x] nu era oprită: mijlocul era 0, iar v[0:] era aceeași listă [x], care se reîmpărțea la nesfârșit. Cu len(v) <= 1, listele cu zero sau un element sunt returnate direct, iar fiecare apel recursiv primește o listă strict mai mică. Adâncimea recursivității devine log2(n).
Alte forme ale mesajului
RecursionError: maximum recursion depth exceededRecursionError: maximum recursion depth exceeded while calling a Python object
Cum o eviți pe viitor
La orice algoritm „împarte și stăpânește”, verifică două lucruri: cazul de bază acoperă cea mai mică problemă care nu se mai poate împărți (aici 0 și 1 element) și fiecare apel recursiv primește o listă strict mai mică. Testează pe [], [7], [7, 7, 7] și pe o listă deja sortată: acolo apar aproape toate erorile de recursivitate la sortări.
Întrebări frecvente
De ce merge sort pe [3, 1, 2] merge, dar pe [5] nu?
Pe orice listă se ajunge, prin împărțiri, la liste cu un element. Așa că eroarea apare de fapt pe orice listă nevidă, inclusiv [3, 1, 2]. Doar lista goală trece.
Merge sort poate depăși limita de recursivitate pe liste mari?
Nu în practică: adâncimea lui merge sort este log2(n), deci în jur de 20 de niveluri pentru un milion de elemente. Dacă primești RecursionError, cazul de bază e greșit.
Erori înrudite
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. TypeError: list indices must be integers or slices, not float Ai calculat poziția cu împărțirea obișnuită /, care dă mereu un număr zecimal (2.0, 2.5), iar indicii de listă trebuie să fie întregi. Folosește împărțirea întreagă: mijloc = (stanga + dreapta) // 2. Î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.
