Înțelegerea recursivității

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Definiție

  • Funcție care se apelează pe sine
  • Aproape toate situațiile unde folosim bucle
    • înlocuiește buclele cu recursivitate
  • Poate rezolva probleme aparent complexe
Structuri de date și algoritmi în Python

Exemplu - factorialul

$n!$

Structuri de date și algoritmi în Python

Exemplu - factorialul

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Structuri de date și algoritmi în Python

Exemplu - factorialul cu recursivitate

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • Se execută la infinit!
Structuri de date și algoritmi în Python

Exemplu - identificarea cazului de bază

  • Adaugă o condiție
    • asigură că algoritmul nu se execută la infinit
  • Cazul de bază factorial -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • Calculatorul folosește o stivă pentru a urmări funcțiile
    • Stiva de apeluri
Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(5) pornește
  • Înainte ca factorial(5) să termine -> factorial(4) pornește
  • Înainte ca factorial(4) să termine -> factorial(3) pornește

Imagine a unei stive cu un element ce reprezintă o funcție.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(5) pornește
  • Înainte ca factorial(5) să termine -> factorial(4) pornește
  • Înainte ca factorial(4) să termine -> factorial(3) pornește
  • Înainte ca factorial(3) să termine -> factorial(2) pornește

Imagine a unei stive cu două elemente ce reprezintă două funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(5) pornește
  • Înainte ca factorial(5) să termine -> factorial(4) pornește
  • Înainte ca factorial(4) să termine -> factorial(3) pornește
  • Înainte ca factorial(3) să termine -> factorial(2) pornește
  • Înainte ca factorial(2) să termine -> factorial(1) pornește

Imagine a unei stive cu trei elemente ce reprezintă trei funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(5) pornește
  • Înainte ca factorial(5) să termine -> factorial(4) pornește
  • Înainte ca factorial(4) să termine -> factorial(3) pornește
  • Înainte ca factorial(3) să termine -> factorial(2) pornește
  • Înainte ca factorial(2) să termine -> factorial(1) pornește

Imagine a unei stive cu patru elemente ce reprezintă patru funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină

Imagine a unei stive cu patru elemente ce reprezintă patru funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină
    • returnează 2

Imagine a unei stive cu patru elemente ce reprezintă patru funcții. Ultima funcție este însoțită de valoarea returnată.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină
    • returnează 2
  • factorial(3) se termină
    • returnează 6

Imagine a unei stive cu trei elemente ce reprezintă trei funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină
    • returnează 2
  • factorial(3) se termină
    • returnează 6
  • factorial(4) se termină
    • returnează 24

Imagine a unei stive cu două elemente ce reprezintă două funcții.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină
    • returnează 2
  • factorial(3) se termină
    • returnează 6
  • factorial(4) se termină
    • returnează 24
  • factorial(5) se termină
    • returnează 120

Imagine a unei stive cu un element ce reprezintă o funcție.

Structuri de date și algoritmi în Python

Cum funcționează recursivitatea

  • factorial(1) se termină
    • returnează 1
  • factorial(2) se termină
    • returnează 2
  • factorial(3) se termină
    • returnează 6
  • factorial(4) se termină
    • returnează 24
  • factorial(5) se termină
    • returnează 120

Imagine a unei stive goale.

Structuri de date și algoritmi în Python

Programare dinamică

  • Tehnică de optimizare
  • Aplicată în principal recursivității
  • Poate reduce complexitatea algoritmilor recursivi
  • Utilizată pentru:
    • Orice problemă divizibilă în subprobleme mai mici
    • Subproblemele se suprapun
  • Soluțiile subproblemelor sunt salvate, evitând recalcularea
    • Memoizare
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...