În cuvinte simple, recursivitatea este o modalitate de a rezolva problema prin faptul că o funcție se numește în sine, cuvântul „ recursiv 'Provine din verbul latin' recidiva ”, Care înseamnă să reface ceva. Aceasta este funcția recursivă, reface același lucru din nou și din nou, adică își amintește de sine. În acest articol, vom afla despre recursivitatea în python. Următoarele sunt subiectele tratate în acest blog:
- Ce este recursiunea în Python?
- Condiția de reziliere
- Limita de recursiune a lui Python
- Aplatizarea listelor cu recursivitate
- Avantajele recursivității
- Dezavantaje ale recursiunii
Ce este recursiunea în Python?
Recursivitatea este procesul de determinare a ceva în termeni de sine. Știm că în Python, orice funcție poate apela orice altă funcție, o funcție se poate numi și ea însăși. Aceste tipuri de funcții care se numesc până când anumite condiții nu sunt îndeplinite sunt denumite funcții recursive.
să luăm câteva exemple pentru a vedea cum funcționează, dacă vi se dă un număr întreg pozitiv n, factorialul ar fi.
- n! = n * (n-1) * (n-2) și așa mai departe.
- 2! = 2 * (2-1)
- unu! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Înlocuirea valorilor de mai sus va avea ca rezultat următoarea expresie
- 4! = 4 * 3 * 2 * 1
Trebuie să definim o funcție care să spună fapt (n) care ia ca parametru întregul pozitiv sau 0 și returnează al n-lea factorial, cum putem face asta folosind recursivitatea?
Să vedem, pentru a face acest lucru folosind recursivitatea, trebuie să examinăm următoarea ecuație
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # putem rescrie declarația de mai sus ca pe această linie
Acum, dacă trecem 2 ca parametru, vom obține:
2! = 2,1! = 2
În mod similar, dacă trecem de 1 vom obține:
unu! = 1,0! = 1
Dar dacă trecem de 0, se sparge
0! = 0. (- 1)! și aici factorial pentru -1 nu este definit, deci funcționează numai pentru valori> 0
Deci, trebuie să scriem două cazuri
1. n! = n. (n-1)! dacă n> = 1
2. 1 dacă n = 0
Aceasta este o soluție completă pentru toate numerele întregi pozitive și 0.
eșuează rapid vs eșuează în siguranță
Condiția de reziliere
O funcție recursivă trebuie să îndeplinească o condiție importantă pentru a termina. Trecând la o condiție în care problema poate fi rezolvată fără recursivitate suplimentară, o funcție recursivă se va termina, minimizând problema în sub-pașii mai mici. O recursiune poate ajunge într-o buclă infinită dacă condiția de reziliere nu este îndeplinită în apeluri.
Condiții factoriale:
- factorial de n = n * (n-1) atâta timp cât n este mai mare de 1.
- 1 dacă n = 0
Vom converti condițiile factoriale de mai sus în codul python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Să luăm un exemplu, să presupunem că dorim să găsim factorialul 4:
fact (4) #this va returna 4 * fact (3) și așa mai departe până n == 1.
Ieșire: 24
Este folosit atât de des ca exemplu de recursivitate datorită simplității și clarității sale. Rezolvarea unor instanțe mai mici ale unei probleme la fiecare pas, numită recursivitate în informatică.
Limita de recursiune a lui Python
În unele limbi, puteți crea o buclă recursivă infinită, dar, în Python, există o limită de recursivitate. Pentru a verifica limita, executați următoarea funcție din modulul sys. care va da limita recursiunii setate pentru python.
import sys sys.getrecursionlimit ()
Ieșire: 1000
De asemenea, puteți modifica limita folosind funcțiile modulului sysetrecursionlimit () în funcție de cerința dvs., acum să creăm o funcție care se numește recursiv până când depășește limita și verifică ce se întâmplă:
def recursive (): recursive () if __name__ == '__main__': recursive ()
Dacă rulați codul de mai sus, veți obține o excepție de execuție: RuntimeError: adâncimea maximă de recursivitate depășită. Python vă împiedică să creați o funcție care se termină într-o buclă recursivă nesfârșită.
Aplatizarea listelor cu recursivitate
Alte lucruri pe care le puteți face folosind recursivitatea, cu excepția factorialelor, să presupunem că doriți să creați un singur dintr-o listă care este imbricată, se poate face folosind codul de mai jos:
def aplatizați (a_list, flat_list = none): dacă flat_list nu este none: flat_list = [] pentru elementul din a_list: dacă este instanță (item, list): aplatizați (item, flat_list) altfel: flat_list.append (item) returnează flat_list dacă __name__ == '__main__': imbricat = [1,2,3, [4,5], 6] x = aplatiza (imbricat) print (x)
Ieșire: [1,2,3,4,5,6]
Rularea codului de mai sus va avea ca rezultat o listă unică în loc de o listă de numere întregi care conține o listă de numere întregi pe care am folosit-o ca intrare. De asemenea, puteți face același lucru folosind și alte modalități, Python are ceva numit itertools.chain () puteți verifica codul utilizat pentru crearea unui lanț de funcții () este o abordare diferită să faceți același lucru ca și noi.
Avantajele recursivității
Codul este curat și elegant într-o funcție recursivă.
O sarcină compusă poate fi împărțită în sub-probleme mai simple folosind recursivitatea.
Generarea secvenței este mai ușoară cu recursivitatea decât utilizarea unor iterații imbricate.
Dezavantaje ale recursiunii
Urmarea logicii din spatele funcției recursive ar putea fi uneori dificilă.
Apelurile recursive sunt costisitoare (ineficiente), deoarece ocupă multă memorie și timp.
Funcțiile recursive sunt greu de depanat.
În acest articol am văzut ce este recursivitatea și cum putem dezvolta funcții recursive din enunțul problemei, modul în care matematic poate fi definită o afirmație problemă. Am rezolvat o problemă a factorialului și am aflat condițiile necesare pentru a găsi factoriale din care am putut converti acele condiții în cod python, oferindu-vă înțelegerea modului în care funcționează recursiunea. Cred că este îngrijit că Python are o limită încorporată pentru recursivitate pentru a împiedica dezvoltatorii să creeze funcții recursive slab construite. Un lucru important de observat este că recursivitatea este greu de depanat, deoarece funcția continuă să se apeleze.