ce este recursivitate?

recursivitatea este procesul de definire a ceva în termeni de sine.

un exemplu de lume fizică ar fi plasarea a două oglinzi paralele una față de cealaltă. Orice obiect între ele ar fi reflectat 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ă. Aceste tipuri de construct sunt denumite funcții recursive.

următoarea imagine arată funcționarea unei funcții recursive numitărecurse.

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 lui 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 = 3print("The factorial of", num, "is", factorial(num))

ieșire

The factorial of 3 is 6

în exemplul de mai sus,factorial() este o funcție recursivă așa cum se numește.

când numim această funcție cu un număr întreg pozitiv, se va apela recursiv prin scăderea numărului.

fiecare funcție înmulțește numărul cu factorialul numărului de sub el până când este egal cu unul. Acest apel recursiv poate fi explicat în următorii pași.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

să ne uităm la o imagine care arată un proces pas cu pas a ceea ce se întâmplă:

recursivitatea noastră se termină 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 oprește recursivitatea sau altfel funcția se numește infinit.

interpretul Python limitează adâncimile recursivității pentru a ajuta la evitarea recursiunilor infinite, rezultând revărsări de stivă.

în mod implicit, adâncimea maximă de recursivitate este 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 (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

avantajele recursivității

1. funcțiile Recursive fac Codul să arate curat și elegant.
2. o sarcină complexă poate fi împărțită în sub-probleme mai simple folosind recursivitatea.
3. generarea secvenței este mai ușoară cu recursivitatea decât utilizarea unor iterații imbricate.

dezavantajele recursivității

1. uneori logica din spatele recursivității este greu de urmărit.
2. apelurile Recursive sunt scumpe (ineficiente), deoarece ocupă multă memorie și timp.
3. funcțiile Recursive sunt greu de depanat.