O funcție care se apelează pe ea însăși folosește recursivitatea.
Ideea apare peste tot, atât în matematică, cât și în programare. Avantajul ei este că o funcție poate parcurge datele până când ajunge la un rezultat.
Ai grijă când scrii o astfel de funcție, pentru că ajungi ușor la una care nu se oprește niciodată sau care consumă prea multă memorie sau putere de procesare. Totuși, scrisă corect, recursivitatea este un mod eficient și elegant din punct de vedere matematic de a programa.
Exemplu
O numărătoare inversă recursivă care începe de la 5:
Ieșire: program Python complet
def countdown(n):
if n <= 0:
print("Gata!")
else:
print(n)
countdown(n - 1)
countdown(5)
Cazul de bază și cazul recursiv
Orice funcție recursivă are nevoie de două părți:
- Cazul de bază - Condiția care încheie recursivitatea
- Cazul recursiv - Punctul în care funcția se apelează pe ea însăși cu un argument modificat
Dacă elimini cazul de bază, funcția continuă să se apeleze pe ea însăși până când Python o oprește cu o eroare de recursivitate.
Aici nimic nu contează mai mult decât cazul de bază, așa că verifică întotdeauna că la condiția lui se va ajunge mai devreme sau mai târziu.
Exemplu
Identificarea cazului de bază și a cazului recursiv:
Ieșire: program Python complet
def factorial(n):
# Cazul de bază
if n == 0 or n == 1:
return 1
# Cazul recursiv
else:
return n * factorial(n - 1)
print(factorial(5))
Șirul lui Fibonacci
Un exemplu clasic de recursivitate este șirul lui Fibonacci. Începe cu 0 și 1, iar fiecare număr următor este ce obții adunând cele două numere dinaintea lui:
0, 1, 1, 2, 3, 5, 8, 13 și așa mai departe.
Șirul nu are sfârșit, iar aceeași regulă de adunare se aplică pe tot parcursul lui.
Cu recursivitatea, putem calcula orice număr ales din șir:
Exemplu
Găsește numărul de la poziția 7 din șirul lui Fibonacci, numărând de la 0:
Ieșire: program Python complet
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7))
Recursivitatea cu liste
O listă poate fi prelucrată recursiv, tratând un singur element la fiecare apel:
Exemplu
Adună toate elementele unei liste:
Ieșire: program Python complet
def sum_list(numbers):
if len(numbers) == 0:
return 0
else:
return numbers[0] + sum_list(numbers[1:])
my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))
Exemplu
Găsește cea mai mare valoare dintr-o listă:
Ieșire: program Python complet
def find_max(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))
Limita de adâncime a recursivității
În Python, recursivitatea poate merge doar până la o anumită adâncime. Implicit, limita este de obicei în jur de 1000 de apeluri recursive.
Poți mări această limită dacă ai nevoie de mai multă adâncime, dar astfel programul tău s-ar putea bloca.
Așadar, mărește-o cu grijă, iar pentru o recursivitate foarte adâncă ia în considerare folosirea iterației.
Exemplu
Afișează limita de recursivitate curentă:
Ieșire: program Python complet
import sys
print(sys.getrecursionlimit())
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())