Introducere în recursivitate în Python

Cuprins

Vrei să aprofundezi subiectul recursivității în programare? Acest ghid despre recursivitate în Python îți va servi drept punct de plecare ideal.

Recursiunea este o tehnică extrem de utilă pentru soluționarea problemelor, pe care orice programator ar trebui să o aibă în repertoriul său. Deși poate părea intimidantă la început, recursiunea te poate ajuta să descoperi soluții elegante pentru probleme complexe.

În acest material, vom adopta o abordare practică, bazată pe cod, pentru a înțelege recursiunea prin intermediul Python. Mai exact, vom discuta despre:

Fundamentele recursiunii
Funcțiile recursive și mecanismul lor de funcționare
Implementarea funcțiilor recursive în Python
Distincția dintre abordările iterative și recursive în rezolvarea problemelor

Să începem explorarea!

Ce reprezintă recursiunea?

Recursiunea este o tehnică de programare în care o funcție se apelează pe sine în mod repetat, cu scopul de a rezolva o problemă.

În esență, recursiunea este o metodă de a aborda problemele care presupune divizarea unei probleme complexe în subprobleme mai mici, dar de natură similară. Practic, aceasta îți permite să rezolvi o problemă în funcție de versiuni mai simple ale aceleiași probleme.

Așadar, cum transpunem recursiunea în cod? Pentru a înțelege acest lucru, hai să analizăm funcționarea funcțiilor recursive.

Înțelegerea funcțiilor recursive

O funcție recursivă se definește prin auto-invocarea sa în cadrul propriei definiții. Fiecare apel recursiv reprezintă o versiune mai restrânsă sau mai simplă a problemei inițiale.

Pentru a preveni o recursiune infinită, funcțiile recursive trebuie să includă unul sau mai multe cazuri de bază – condiții care indică momentul în care funcția încetează să se mai apeleze și returnează un rezultat.

Să analizăm mai detaliat. O funcție recursivă este alcătuită din:

Cazul de bază: Cazul de bază este o condiție (sau un set de condiții) care specifică momentul în care recursiunea trebuie să se oprească. Când cazul de bază este îndeplinit, funcția returnează un rezultat fără a mai efectua apeluri recursive. Acesta este crucial pentru a preveni recursiunea infinită.
Cazul recursiv: Cazul recursiv stabilește modul în care problema este segmentată în subprobleme mai mici. În această secțiune a funcției, aceasta se autoapelează cu valori modificate. Astfel, fiecare apel recursiv reprezintă un pas către atingerea cazului de bază.

În continuare, să discutăm despre ce se întâmplă când apelezi o funcție recursivă.

Cum funcționează recursiunea în profunzime

Atunci când o funcție este invocată, un registru al contextului său de execuție este stocat în stiva de apeluri. Acest registru conține informații precum argumentele funcției, variabilele locale și adresa de returnare după finalizarea execuției funcției.

În cazul funcțiilor recursive, când o funcție se autoapelează, un nou registru este adăugat în stiva de apeluri, suspendând temporar execuția funcției curente. Stiva permite Python să monitorizeze toate apelurile de funcții în așteptare, inclusiv cele rezultate din apelurile recursive.

Recursiunea continuă până când se ajunge la cazul de bază. Când cazul de bază returnează un rezultat, apelurile de funcții sunt rezolvate unul câte unul – fiecare funcție returnând rezultatul către nivelul anterior din stiva de apeluri. Acest proces continuă până la finalizarea apelului inițial al funcției.

Implementarea recursiunii în Python

În această secțiune, vom analiza trei exemple practice de recursivitate:

Calcularea factorialului unui număr
Calcularea numerelor Fibonacci
Implementarea căutării binare prin recursiune

Pentru fiecare exemplu, vom descrie problema, vom prezenta implementarea recursivă în Python și vom explica modul de funcționare al acesteia.

#1. Calculul factorialului folosind recursiunea

Problemă: Calculează factorialul unui număr întreg nenegativ n, notat cu n!. Din punct de vedere matematic, factorialul unui număr n este rezultatul înmulțirii tuturor numerelor întregi pozitive de la 1 la n.

Calculul factorialului se pretează bine la recursivitate, așa cum se observă:

Iată funcția recursivă pentru a calcula factorialul unui număr dat n:

def factorial(n):
    # Cazul de bază
    if n == 0 or n == 1:
        return 1
    # Cazul recursiv: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Să calculăm 5! folosind funcția factorial():

factorial_5 = factorial(5)
print(factorial(5))
# Ieșire: 120

Să vedem cum funcționează funcția:

Avem un caz de bază care verifică dacă n este egal cu 0 sau 1. Dacă această condiție este îndeplinită, funcțiile returnează 1. Nu uita că 0! este 1, la fel și 1!.
Dacă n este mai mare decât 1, calculăm n! prin înmulțirea lui n cu factorialul lui n-1. Aceasta se exprimă ca n * factorial(n – 1).
Funcția continuă să efectueze apeluri recursive cu valori descrescătoare ale lui n până când se atinge cazul de bază.

#2. Numerele Fibonacci prin recursivitate

Problemă: Găsește termenul de la al n-lea indice din Secvența Fibonacci. Secvența Fibonacci este definită astfel: F(0) = 0, F(1) = 1 și F(n) = F(n-1) + F(n-2) pentru n >= 2.

def fibonacciSeq(n):
    # Cazurile de bază
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Recursiunea: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Să executăm funcția:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Ieșire: 5

Iată cum funcționează funcția:

Să începem prin a discuta cazurile de bază. Dacă n este 0, returnează 0. Iar dacă n este 1, returnează 1. Nu uita F(0) = 0 și F(1) = 1.
În cazul recursiv, dacă n este mai mare decât 1, funcția calculează F(n) adunând termenii F(n-1) și F(n-2). Aceasta se exprimă ca fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
Funcția continuă să facă apeluri recursive cu valori descrescătoare ale lui n până când ajunge la cazurile de bază.

#3. Implementarea recursivă a căutării binare

Problemă: Implementează un algoritm de căutare binară folosind recursiunea pentru a identifica poziția unui element țintă într-o listă sortată.

Iată implementarea recursivă a căutării binare:

def binarySearch(arr, target, low, high):
    # Cazul de bază: ținta nu a fost găsită
    if low > high:
        return -1

    mid = (low + high) // 2

    # Cazul de bază: ținta a fost găsită
    if arr[mid] == target:
        return mid
    # Cazul recursiv: caută în jumătatea stângă sau dreaptă a listei
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

Funcția binarySearch continuă să împartă intervalul de căutare la jumătate cu fiecare apel recursiv până când fie găsește ținta, fie constată că ținta nu se află în listă.

Iată un exemplu de rulare a funcției:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Ieșire: 4

Să detaliem ce face funcția:

În implementarea recursivă a căutării binare, avem două cazuri de bază. În primul rând, dacă low devine mai mare decât high, înseamnă că elementul țintă nu se află în listă. Prin urmare, returnăm -1 pentru a indica faptul că ținta nu a fost găsită.
Celălalt caz de bază verifică dacă elementul de la indexul mijlocului din intervalul curent de căutare este egal cu ținta. Dacă acestea se potrivesc, returnăm indexul mijlocului, indicând că am găsit ținta.
În cazul recursiv, dacă elementul din mijloc este mai mare decât ținta, căutăm recursiv în jumătatea stângă a listei apelând binarySearch(arr, target, low, mid – 1). Dacă elementul din mijloc este mai mic decât ținta, căutăm în jumătatea dreaptă apelând binarySearch(arr, target, mid + 1, high).

Abordarea recursivă vs. iterativă

Abordarea iterativă – prin folosirea buclelor – este o altă metodă comună pentru rezolvarea problemelor. Dar cum se diferențiază aceasta de recursivitate? Să aflăm.

Mai întâi, să comparăm soluțiile recursive și iterative aplicate unei probleme comune: calculul factorialului unui număr.

Iată implementarea recursivă a calculului factorial:

def factorialRec(n):
    # Cazul de bază
    if n == 0 or n == 1:
        return 1
    # Cazul recursiv: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Deoarece știm că factorialul unui număr nenegativ este produsul tuturor numerelor de la 1 până la n, putem scrie și o implementare iterativă folosind bucle.

def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Ambele implementări dau rezultate identice.

factorial_5 = factorialRec(5)
print(factorial_5)
# Ieșire: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Ieșire: 120

Dar este abordarea iterativă preferabilă recursivității? Când apare o recursivitate profundă – cu prea multe apeluri de funcții – te poți confrunta cu erori din cauza depășirii adâncimii recursiunii. O buclă este o opțiune mai bună pentru problemele a căror implementare recursivă necesită prea multe apeluri de funcții pentru a ajunge la cazul de bază.

Să rezumăm diferențele dintre implementările iterative și recursive:

Caracteristică	Abordare recursivă	Abordare iterativă
Structură	Utilizează apeluri de funcții recursive și se bazează pe stiva de apeluri.	Utilizează bucle pentru iterare fără apeluri suplimentare de funcții.
Cazuri de bază	Necesită cazuri de bază explicite pentru a opri recursiunea.	De obicei, folosește condiții de buclă pentru terminare.
Performanța	Poate fi mai puțin eficientă din cauza stivei de apeluri. Recursiunea profundă poate genera erori de depășire a stivei.	În general, mai eficientă din punct de vedere al memoriei și mai puțin predispusă la erori de depășire a stivei.
Depanarea	Poate fi dificil de depanat din cauza multiplelor apeluri de funcții și a contextelor de execuție imbricate.	Mai ușor de depanat, având în vedere că fluxul de execuție este mai liniar.

Concluzie

În acest articol, am început prin a defini ce este recursiunea și cum să creăm funcții recursive cu cazuri de bază și relații de recurență.

Apoi, am scris cod Python – implementări recursive ale unor probleme comune de programare. În final, am analizat diferențele dintre abordările iterative și recursive, precum și avantajele și dezavantajele fiecăreia dintre aceste metode.

Pentru aprofundare, consultă această listă de întrebări de interviu Python.