În acest tutorial, veți învăța să creați o funcție recursivă (o funcție care se numește singură).
Ce este recursivitatea?
Recursivitatea este procesul de definire a ceva în termeni de sine.
Un exemplu fizic al lumii ar fi plasarea a două oglinzi paralele una față de cealaltă. Orice obiect între ele s-ar reflecta recursiv.
Funcția recursivă Python
În Python, știm că o funcție poate apela alte funcții. Este chiar posibil ca funcția să se numească singură. Aceste tipuri de construct sunt denumite funcții recursive.
Următoarea imagine arată funcționarea unei funcții recursive numită recurse.
Funcție recursivă în Python
Următorul este un exemplu de funcție recursivă pentru a găsi factorialul unui număr întreg.
Factorialul unui număr este produsul tuturor numerelor întregi de la 1 la acel număr. De exemplu, factorialul 6 (notat ca 6!) Este 1 * 2 * 3 * 4 * 5 * 6 = 720.
Exemplu de funcție recursivă
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Ieșire
Factorialul de 3 este 6
În exemplul de mai sus, factorial()este o funcție recursivă așa cum se numește ea însăși.
Când numim această funcție cu un număr întreg pozitiv, aceasta se va numi recursiv prin scăderea numărului.
Fiecare funcție înmulțește numărul cu factorialul numărului de sub ea până când este egal cu unul. Acest apel recursiv poate fi explicat în pașii următori.
factorial (3) # primul apel cu 3 3 * factorial (2) # al doilea apel cu 2 3 * 2 * factorial (1) # al treilea apel cu 1 3 * 2 * 1 # revine de la al treilea apel ca număr = 1 3 * 2 # întoarcere din al doilea apel 6 # întoarcere din primul apel
Să vedem o imagine care arată un proces pas cu pas al ceea ce se întâmplă:
Funcționarea unei funcții factoriale recursive
Recursiunea noastră se termină atunci când numărul se reduce la 1. Aceasta se numește condiția de bază.
Fiecare funcție recursivă trebuie să aibă o condiție de bază care să oprească recursiunea sau altfel funcția se numește la infinit.
Interpretul Python limitează adâncimile recursivității pentru a ajuta la evitarea recursiunilor infinite, rezultând în revărsări ale stivei.
În mod implicit, adâncimea maximă a recursiunii este de 1000. Dacă limita este depășită, rezultă RecursionError. Să ne uităm la o astfel de condiție.
def recursor(): recursor() recursor()
Ieșire
Traceback (ultimul apel cel mai recent): Fișierul "", linia 3, în Fișierul "", linia 2, într-un Fișier "", linia 2, într-un Fișier "", linia 2, într-o (Linia anterioară repetată de încă 996 de ori ) RecursionError: adâncimea maximă de recursivitate depășită
Avantajele recursivității
- Funcțiile recursive fac ca codul să arate curat și elegant.
- O sarcină complexă poate fi împărțită în sub-probleme mai simple folosind recursivitatea.
- Generarea secvenței este mai ușoară cu recursivitatea decât utilizarea unei iterații imbricate.
Dezavantaje ale recursiunii
- Uneori, logica din spatele recursivității este greu de urmat.
- Apelurile recursive sunt costisitoare (ineficiente), deoarece ocupă multă memorie și timp.
- Funcțiile recursive sunt greu de depanat.
