Doriți să aflați totul despre recursivitate în programare? Acest tutorial despre recursivitate în Python vă va ajuta să începeți.
Recursiunea este o tehnică foarte utilă de rezolvare a problemelor pe care să o adăugați la setul de instrumente al programatorului. Deși inițial este adesea dificil de învățat, recursiunea vă poate ajuta să găsiți soluții mai elegante la probleme complexe.
În acest tutorial, vom adopta o abordare bazată pe cod pentru a învăța recursiunea folosind Python. În special, vom acoperi:
- Bazele recursiunii
- Funcțiile recursive și modul în care funcționează
- Implementarea Python a funcțiilor recursive
- Diferențele dintre abordările iterative și recursive ale rezolvării problemelor
Să începem!
Cuprins
Ce este recursiunea?
Recursiunea este o tehnică de programare în care o funcție se autoapelează în mod repetat pentru a rezolva o problemă.
În esență, recursiunea este o abordare de rezolvare a problemelor care implică descompunerea unei probleme complexe în subprobleme mai mici, identice. În esență, vă permite să rezolvați o problemă în termeni de versiuni mai simple ale acesteia.
Deci, cum implementăm recursiunea în cod? Pentru a face acest lucru, să înțelegem cum funcționează funcțiile recursive.
Înțelegerea funcțiilor recursive
Definim o funcție recursivă care se autoinvocă în definiția sa. Fiecare apel recursiv reprezintă o versiune mai mică sau mai simplă a problemei originale.
Pentru a se asigura că recursiunea se termină în cele din urmă, funcțiile recursive trebuie să includă unul sau mai multe cazuri de bază – condiții în care funcția încetează să se mai apeleze și returnează un rezultat.
Să dezvăluim asta în continuare. O funcție recursivă constă din:
- Cazul de bază: Cazul de bază este o condiție (sau condiții) care determină când recursiunea ar trebui să se oprească. Când este îndeplinit cazul de bază, funcția returnează un rezultat fără a mai efectua apeluri recursive. Un caz de bază este esențial pentru a preveni recursiunea infinită.
- Cazul recursiv: Cazul recursiv definește cum se descompune problema în subprobleme mai mici. În această parte a funcției, funcția se autoapelează cu intrări modificate. Fiecare apel recursiv este, prin urmare, un pas către atingerea cazului de bază.
În continuare, să discutăm ce se întâmplă atunci când apelați o funcție recursivă.
Cum funcționează recursiunea sub capotă
Când o funcție este apelată, o înregistrare a contextului său de execuție este plasată în stiva de apeluri. Această înregistrare include informații despre argumentele funcției, variabilele locale și locația de returnat odată ce funcția termină execuția.
În cazul funcțiilor recursive, atunci când o funcție se autoapelează, o nouă înregistrare este împinsă în stiva de apeluri, suspendând efectiv execuția funcției curente. Stiva îi permite lui Python să țină evidența tuturor apelurilor de funcții în așteptare, inclusiv a celor de la apelurile recursive.
Până când se ajunge la cazul de bază, recursiunea continuă. Când cazul de bază returnează un rezultat, apelurile de funcție sunt rezolvate unul câte unul – fiecare funcție returnând rezultatul la nivelul anterior al stivei de apeluri. Acest proces continuă până la finalizarea apelului inițial al funcției.
Implementarea recursiunii în Python
În această secțiune, vom explora trei exemple simple de recursivitate:
Pentru fiecare exemplu, vom prezenta problema, vom oferi implementarea recursivă Python și apoi vom explica cum funcționează implementarea recursivă.
#1. Calcul factorial folosind recursiunea
Problemă: Calculați factorialul unui număr întreg nenegativ n, notat cu n!. Din punct de vedere matematic, factorialul unui număr n este produsul tuturor numerelor întregi pozitive de la 1 la n.
Calculul factorial se pretează bine recursiunii, după cum se arată:
Iată funcția recursivă pentru a calcula factorialul unui număr dat n:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: 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)) # Output: 120
Acum să vedem cum funcționează funcția:
- Avem un caz de bază care verifică dacă n este egal cu 0 sau 1. Dacă condiția este îndeplinită, funcțiile returnează 1. Reamintim 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. Acesta este exprimat ca n * factorial(n – 1).
- Funcția continuă să facă apeluri recursive cu valori descrescătoare ale lui n până când ajunge la cazul de bază.
#2. Numere Fibonacci cu recursivitate
Problemă: Găsiți termenul la al n-lea indice din Secvența Fibonacci. Secvența Fibonacci este definită după cum urmează: F(0) = 0, F(1) = 1 și F(n) = F(n-1) + F(n-2) pentru n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Să rulăm funcția:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Iată cum funcționează funcția:
- Să începem prin a discuta cazurile de bază. Dacă n este 0, returnează 0. Și dacă n este 1, returnează 1. Reamintim F(0) = 0 și F(1) = 1.
- În cazul recursiv, dacă n este mai mare decât 1, funcția calculează F(n) prin adăugarea termenilor F(n-1) și F(n-2). Aceasta este exprimată 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 recursiva a căutării binare
Problemă: Implementați un algoritm de căutare binar folosind recursiunea pentru a găsi poziția unui element țintă într-o listă sortată.
Iată implementarea recursivă a căutării binare:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
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 determină că ținta nu este î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) # Output: 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 mare, înseamnă că elementul țintă nu este în listă. Deci, revenim -1 pentru a indica faptul că ținta nu a fost găsită.
- Celălalt caz de bază verifică dacă elementul de la mijlocul indexului din mijlocul intervalului curent de căutare este egal cu ținta. Dacă se potrivesc, returnăm indicele la mijloc, indicând că am găsit ținta.
- În cazul recursiv, dacă elementul din mijloc este mai mare decât ținta, căutăm recursiv jumătatea stângă a matricei apelând binarySearch(arr, target, low, mid – 1). Dacă elementul din mijloc este mai mic decât ținta, căutăm jumătatea dreaptă apelând binarySearch(arr, target, mid + 1, high).
Recursivă vs. Abordare iterativă
Abordarea iterativă – folosind bucle – este o altă abordare comună pentru rezolvarea problemelor. Deci, cu ce este diferit de recursivitate? Să aflăm.
În primul rând, comparăm soluțiile recursive și iterative cu o problemă comună: calculul factorialului unui număr.
Iată implementarea recursivă a calculului factorial:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: 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) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Dar este o abordare iterativă preferată față de recursivitate? Când există recursivitate profundă – cu prea multe apeluri de funcție – puteți întâlni erori din cauza depășirii adâncimii recursiunii. Buclă este o opțiune mai bună pentru problemele a căror implementare recursivă necesită prea multe apeluri de funcție pentru a ajunge la cazul de bază.
Să rezumam diferențele dintre implementările iterative și recursive:
Caracteristică Abordare recursivaAbordare iterativăStructurăFolosește apeluri de funcții recursive și se bazează pe stiva de apeluri.Folosește bucle pentru iterare fără apeluri de funcție suplimentare.Cazuri de bazăNecesită cazuri de bază explicite pentru a opri recursiunea.De obicei, utilizează condiții de buclă pentru terminare.PerformanțaPoate fi mai puțin eficientă din cauza stivei de apeluri. . Recursiunea profundă poate duce uneori la 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 apelurilor multiple de funcții și a contextelor de execuție imbricate. .Abordare iterativă vs recursivă
Concluzie
În acest articol, am început prin a afla ce este recursiunea și cum să definim funcții recursive cu cazuri de bază și relații de recurență.
Apoi am scris niște cod Python – implementări recursive ale problemelor comune de programare. În cele din urmă, am învățat diferențele dintre abordările iterative și recursive și avantajele și dezavantajele fiecăreia dintre aceste abordări.
Apoi, consultați această listă de întrebări de interviu Python.