Ce este funcția recursivă?

Funcția se numește din nou și din nou, până când satisface o condiție recursivă. O funcție de recursie descompune problema în probleme mai mici și apelează propria logică pentru a rezolva problema mai mică. Această tehnică este cunoscută sub numele de divizare și cucerire. Este folosit în matematică și domeniul informatică.

Funcția recursivă include un caz de bază (sau un caz terminal) și un caz recursiv. În cazul de bază, puteți lua în considerare problema principală de rezolvat, iar cazul recursiv împarte problema în părți mai mici până când atinge un nivel în care poate fi rezolvat ușor. Un caz recursiv poate întoarce un rezultat sau poate apela din nou pentru a diviza în continuare problema. De fiecare dată când problema se descompune în o problemă mai mică, funcția care se numește recursiv salvează starea apelului și se așteaptă rezultatul de la sine după ce a descompus problema.

Funcția recurentă în Python

Conceptul de recursiune rămâne același în Python. Funcția se numește pentru a descompune problema în probleme mai mici. Cel mai simplu exemplu la care ne-am putea gândi la o recursiune ar fi găsirea factorialului unui număr.

Să zicem că trebuie să găsim factorialul numărului 5 => 5! (Problema noastră)

Pentru a găsi 5! problema poate fi împărțită în altele mai mici 5! => 5 x 4!

Deci, pentru a primi 5! Trebuie să găsim 4! și înmulțiți-l cu 5.

Să continuăm să împărțim problema

5! = 4! x 5

4! = 3! x 4

3! = 3 x 2!

2! = 2 x 1!

1! = 1

Când ajunge la cea mai mică bucată, adică, obținând factorialul de 1, putem returna rezultatul ca

Să luăm un exemplu de pseudo-cod: -

Algoritm pentru factorial

Să vedem algoritmul factorial:

function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)

Funcționează apelurile

Să presupunem că găsim un factorial de 5.

get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call

Rezultatul final va fi 120 unde am început executarea funcției. Funcția noastră de recursură se va opri atunci când numărul va fi atât de redus încât rezultatul poate fi obținut.

  • Primul apel care primește factorialul de 5 va avea ca rezultat o condiție recursivă în care va fi adăugat la stivă și se va face un alt apel după reducerea numărului la 4.
  • Această recursiune va continua să apelezi și să rupi problema în bucăți mai mici până când ajunge la condiția de bază.
  • Starea de bază aici este când numărul este 1.
  • Fiecare funcție recursivă are propria sa condiție recursivă și o condiție de bază.

Pro și contra funcției recursive Python

  • Execuția recursului este astfel încât nu va face niciun fel de calcul până când ajunge la condiția de bază.
  • Pentru a ajunge la condiții de bază, puteți rămâne fără memorie.
  • Într-o problemă mare, unde pot exista un milion de pași sau putem spune că un milion de recursuri pentru a face programul s-ar putea ajunge să dea o eroare de memorie sau o eroare de segmentare.
  • 1000000! = 1000000 * 999999! =?
  • Recursiunea este diferită de iterație, nu se mărește ca o metodă iterativă.
  • Diferite limbi au diferite optimizări pentru recurs.
  • În multe limbi, metoda iterativă ar fi mai performantă decât recursivitatea.
  • Fiecare limbă are unele restricții în ceea ce privește profunzimea recursului cu care te-ai putea confrunta atunci când rezolvi probleme mari.
  • Uneori este dificil să înțelegem problemele complexe cu recurs, în timp ce este destul de simplu cu iterația.

Unii pro

  • În unele cazuri, recursivitatea este un mod convenabil și mai rapid de utilizat.
  • Foarte util în traversarea arborelui și în căutarea binară.

Codul Python - Recursiune și iterație

Am înțeles ce este recursiv și cum funcționează în Python, așa cum știm că toate limbile au o implementare diferită a recursivității pentru optimizare a memoriei și calculului. Există un caz în care iterația ar fi mai rapidă decât recursul.

Aici am compara ambele metode de recurs și de iterație pentru a vedea cum funcționează Python în ambele cazuri.

1. Cod de recursiune pentru factori

def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition

2. Problemă factorială folosind iterație (buclă)

def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact

3. Tipărirea rezultatelor

print(get_recursive_factorial(6))
print(get_iterative_factorial(6))

ieşire:

După cum putem vedea ambele dau aceeași ieșire, întrucât am scris aceeași logică. Aici nu putem vedea nicio diferență în execuție.

Să adăugăm ceva cod de timp pentru a obține mai multe informații despre executarea recursurilor și a iterației în Python.

Vom importa biblioteca „timp” și vom verifica ce oră durează recursiunea și iterația pentru a returna rezultatul.

4. Cod cu calculul timpului

import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))

Vom face executări repetate cu o valoare diferită pentru factori și vom vedea rezultatele. Rezultatele de mai jos pot varia în funcție de la mașină la mașină. Am folosit MacBook Pro 16 GB RAM i7.

Utilizăm Python 3.7 pentru execuție

Cazul 1: - Factorial din 6:

Cazul 2: Factorial de 50:

Cazul 3: Factorial de 100:

Cazul 4: Factorial de 500:

Cazul 5: Factorial de 1000:

Am analizat ambele metode într-o problemă diferită. Mai mult, ambele au fost similare cu excepția cazului 4.

În cazul 5 am primit o eroare în timp ce o făceam cu recurs.

Python a obținut o restricție la adâncimea maximă pe care o puteți merge cu recurs, dar aceeași problemă am putut să o rezolv cu iterație.

Python are restricții împotriva problemei de revărsare. Python nu este optimizat pentru recurgerea la coadă, iar recursiunea necontrolată determină o revărsare de stivă.

Funcția „sys.getrecursionlimit ()” îți va spune limita pentru recurs.

Limita de recurs este modificată, dar nu este recomandat că ar putea fi periculoasă.

Concluzie - Funcția recurentă Python

  • Recursiunea este o soluție la îndemână pentru unele probleme, cum ar fi traversarea copacilor și alte probleme.
  • Python nu este un limbaj de programare funcțional și putem vedea că stiva de recursivitate nu este atât de optimizată în comparație cu iterația.
  • Ar trebui să folosim iterarea în algoritmul nostru ca fiind mai optimizat în Python și vă oferă o viteză mai bună.

Articole recomandate

Acesta este un ghid pentru funcția recurentă în Python. Aici vom discuta despre ce este funcția recursivă, funcția recursivă în Python, algoritmul pentru factori, etc. Puteți parcurge și alte articole sugerate pentru a afla mai multe -

  1. Factorial în Python
  2. Comandele Spark Shell
  3. Cele mai bune compilatoare C
  4. Tipuri de algoritmi
  5. Programul factorial în JavaScript
  6. Ghid pentru lista de comenzi Unix Shell
  7. Tipuri de formulare în reacție cu exemple