...
Eroare Algoritmi și structuri de date · Căutare binară și sortări

RecursionError în merge sort: cazul de bază nu oprește lista cu un element

Pe scurt

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ă

Greșit
PYTHON
def merge_sort(v):
    if not v:
        return v
    m = len(v) // 2
    return interclaseaza(merge_sort(v[:m]), merge_sort(v[m:]))
Corect
PYTHON
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

Greșit
PYTHON
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])
Corect
PYTHON
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ă tu

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 [].

Codul care dă eroarea
PYTHON
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([]))
După reparație, programul afișează
[3, 8, 15, 21, 42]
[7]
[]
Indiciu

O listă cu un singur element este deja sortată și nu trebuie împărțită mai departe.

Alte forme ale mesajului

  • RecursionError: maximum recursion depth exceeded
  • RecursionError: 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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.