Ați fost vreodată prins într-un ciclu aparent nesfârșit în care o problemă continuă să se ramifică în fragmente mai mici?
Dacă da, este posibil să fi ajuns în lumea captivantă a recursiunii. Deși poate părea dificil de înțeles, nu vă faceți griji! În această postare, vom merge într-o călătorie interesantă pentru a afla despre tipurile de recursiuni.
Prin urmare, puneți-vă centura în timp ce explorăm numeroase abordări recursive. Pregătiți-vă să intrați în tărâmul fascinant al recursiunii și observați-i capacitatea remarcabilă de a rezolva probleme complicate.
Ce sunt mai exact recursiunile?
În cuvinte de bază, recursiunea este o tehnică de programare puternică care include o funcție care se autoapelează în timpul execuției. Este ca și cum ai privi într-o oglindă și ai vedea o imagine în interiorul unei imagini, rezultând un ciclu autoreferențial.
Putem aborda probleme mari folosind recursiunea împărțindu-le în subprobleme mai mici și mai ușor de gestionat.
Este similar cu asamblarea unui puzzle, în care o piesă se leagă de alte părți pentru a produce o imagine completă. Recursiunea ne permite să rezolvăm problemele într-o manieră elegantă și eficientă prin repetarea aceluiași set de instrucțiuni cu diverse intrări.
1-Recursie directă
Recursiunea directă este cel mai elementar tip de recursivitate, în care o funcție se autoinvocă direct. Aceasta presupune împărțirea unei probleme problematice în subprobleme mai mici până când se realizează un caz de bază, ceea ce duce la terminare.
Funcția recursivă se autoapelează cu diverse intrări, permițând repetarea execuției aceluiași set de instrucțiuni. Fiecare invocare se bazează pe cea anterioară, apropiindu-se progresiv de cazul de bază care determină terminarea recursiunii.
Să verificăm acest exemplu.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
ieșire:
5
4
3
2
1
2-Recursiune indirectă
Recursiunea indirectă adaugă o răsucire intrigantă căii recursive. Spre deosebire de recursiunea directă, care implică o funcție care se autoapelează în mod explicit, recursiunea indirectă include un lanț de apeluri de funcție.
O funcție o apelează pe alta, care poate apela apoi funcția inițială sau orice altă funcție care revine în cele din urmă la cea originală. Această rețea interconectată de apeluri de funcții produce un dans captivant în care mai multe funcții colaborează pentru a rezolva o problemă.
Exemplu:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
ieșire:
A: 3
B: 2
A: 1
3-Recursie liniară
Luați în considerare o călătorie pe un traseu drept, câte un pas, până când ajungeți la obiectivul dvs. Această tehnică secvenţială este întruchipată de recursiunea liniară, în care o funcţie efectuează un singur apel recursiv în fiecare iteraţie a funcţiei.
Cu fiecare apel recursiv, procesul recursiv se mută mai aproape de un caz de bază prin scăderea dimensiunii problemei. Se procedează într-o manieră clară și liniară, rezolvând subproblemele pe rând până când se ajunge la răspunsul final.
Exemplu:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
ieșire:
120
4-Tree Recursive
Când o funcție se ramifică în mai multe apeluri recursive, intrăm în lumea recursiunii arborescente. O funcție din recursiunea arborelui generează multe apeluri recursive, fiecare dintre ele rezolvă o subproblemă separată, așa cum fac ramurile unui arbore.
Această structură de ramificare permite investigarea simultană a mai multor rute, defalcând efectiv problemele complicate în componente mai mici, interdependente.
Exemplu:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
ieșire:
8
5-Recursiune imbricată
Recursiunea imbricată adaugă un grad interesant de complexitate universului recursiv. În această formă de recursivitate, o funcție încorporează un apel recursiv ca argument în cadrul unui alt apel recursiv.
Apelul recursiv interior acționează asupra unei valori care este dependentă de apelul recursiv exterior. Complexitatea crește cu fiecare invocare imbricată, culminând cu un model intrigant de apeluri recursive imbricate.
Exemplu:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Rezultat:
91
6-Recursie de coadă
Recursiunea cozii este o tehnică de optimizare a algoritmilor recursivi care le pot îmbunătăți performanța. Apelul recursiv apare ca acțiunea finală a unei funcții cu recursiunea coadă, realizarea.
Deoarece nu există operații restante în urma apelului recursiv, compilatorul sau interpretul poate simplifica recursiunea prin înlocuirea acesteia cu un simplu salt.
Această abordare de optimizare, cunoscută sub numele de optimizare a apelului final, reduce cerința pentru fiecare apel recursiv de a păstra un cadru de stivă, rezultând o viteză sporită și o utilizare mai redusă a memoriei.
Exemplu:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Ieșire:
120
7-Recursiune non-coadă
Spre deosebire de recursiunea coadă, recursiunea non-coadă implică activități suplimentare efectuate după apelul recursiv în cadrul unei funcții. Înainte de a putea fi efectuate alte acțiuni, fiecare apel recursiv trebuie să se finalizeze și să revină.
În consecință, până când se ajunge la cazul de bază și se încheie recursiunea, se menține un teanc de operațiuni restante. Recursiunea non-coadă utilizează frecvent mai multă memorie și este mai puțin eficientă decât recursiunea coadă, dar este totuși un instrument util pentru abordarea unei varietăți de probleme.
Exemplu:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
ieșire:
15
Învelire
Recursiunea este un concept intrigant în programare. Ne permite să abordăm problemele complicate într-o manieră recursivă, autoreferențială.
Oferă o metodă distinctă de a gândi și de a rezolva problemele, împărțindu-le în bucăți mai mici și mai ușor de gestionat. Când lucrați cu recursivitate, totuși, este esențial să folosiți atenție la anumite puncte.
Ar trebui să identificați cazuri de bază adecvate care permit terminarea recursiunii. Dacă nu sunt prezente, funcția poate continua să se numească pentru totdeauna.
În al doilea rând, pe baza scenariului în cauză, selectarea tipului adecvat de recursivitate poate duce la soluții mai eficiente și mai elegante. Încercați să găsiți ce funcționează cel mai bine pentru problema din mână. Când lucrați cu adâncimi mari de recursivitate, fiți conștienți de pericolele potențiale, cum ar fi depășirea stivei.
Lasă un comentariu