Conţinutul principal

Îmbunătățirea eficienței funcțiilor recursive

Recursivitatea poate fi o manieră elegantă de rezolvare a unei probleme; mulți algoritmi se bazează pe soluții recursive. Totuși, algoritmii recursivi pot fi ineficienți în raport de timp și spațiu. Vom explora câteva tehnici de îmbunătățire a eficienței acestora.

În provocarea de implementare recursivă a factorialului unui număr, ți s-a cerut să apelezi funcția de mai multe ori, cu diferite valori.

De exemplu, codul JavaScript următor apelează factorial() de 4 ori:

factorial(0);
factorial(2);
factorial(5);
factorial(10);

Hai să analizăm ce face calculatorul când se execută cele 4 instrucțiuni:

Instrucțiunea	Apeluri recursive	Total apeluri
`factorial(0)`		1 apel
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 apeluri
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	6 apeluri
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)` → `factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	11 apeluri

Observăm că factorial(10) trebuie să execute 11 apeluri, iar 6 dintre ele au exact aceleași argumente și returnează valori la fel ca apelurile funcției din timpul execuției lui factorial(5).

Memoizarea factorialului

Putem folosi o tehnică numită memoizare cu ajutorul căreia putem salva timp când se fac apeluri identice ale unei funcții. Memoizarea (o formă de păstrare în cache) își amintește rezultatul unui apel de funcție pentru un anumit parametru, căutându-l într-un tabel ("memo"-ul) și returnează acel rezultat atunci când funcția este re-apelată cu același parametru.

O memoizare a funcției factorial arată astfel:

Dacă $n$ ‍ = 0, returnează 1
Altfel, dacă $n$ ‍ este în memo, returnează valoarea pentru $n$ ‍
Altfel,
- Calculează $(n - 1)! \cdot n$ ‍
- Memorează rezultatul în memo
- Returnează rezultatul

Acest algoritm caută valoarea argumentului în memo înainte de a face apeluri recursive costisitoare. Memo-ul ar trebui să fie o structură de date eficientă la căutări, de exemplu o tabelă hash cu timp de căutare

O (1)

Dacă vrei să vizualizezialgoritmul de memoizare implementat în JavaScript, urmărește acest video sau rulează chiar tu vizualizarea. Înainte de a urmări, ai putea să te provoci chiar tu însuți la implementarea algoritmului în limbajul tău preferat.

Având implementată memoizarea, calculatorul poate fae mai puține apeluri în total, căci nu le mai repetă pe cele identice ale funcției factorial():

Instrucțiune	Apeluri recursive	Total apeluri
`factorial(0)`		1 apel
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 apeluri
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)`	3 apeluri
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)`	6 apeluri

Memoizarea este un compromis între timp și spațiu. Atât timp cât căutarea este eficientă și funcția repetă unele apeluri, calculatorul poate salva timp cu costul folosirii memoriei pentru memo.

Memoizarea funcției Fibonacci

În cazul funcției factorial, algoritmul memoizat beneficiază de optimizare numai când se repetă apeluri ale funcției în timpul execuției. În alte cazuri, totuși, memoizarea poate salva timp chiar pentru un singur apel la o funcție recursivă.

Hai să vedem un exemplu simplu - algoritmul pentru generarea numerelor lui Fibonacci.

Secvența Fibonacci este o renumită serie de numere în care fiecare număr este egal cu suma celor 2 numere anterioare lui. Primele două numere din secvență sunt precizate ca fiind

0

și

1

. După aceea, următorul număr este

1

(calculat din

0 + 1

), iar numărul de după acesta este

2

(calculat din

1 + 1

) și tot așa.

Primele 10 numere Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

O funcție recursivă simplă pentru generarea celui de-al

n

-lea număr arată astfel:

Dacă $n$ ‍ este 0 sau 1, returnează $n$ ‍
Altfel, returnează $fibonacci (n - 1) + fibonacci (n - 2)$ ‍

Acest algoritm este un exemplu de recursivitate multiplă, deoarece se auto-apelează de mai multe ori. Pentru a înțelege apelurile multiple pe care le face calculatorul, ne-ar ajuta să vizualizăm apelurile ca pe un arbore.

Când

n = 5

, calculatorul face 15 apeluri:

Acoperirea video Khan Academy

Recursive Fibonacci Calls (Diagrammed)Vezi transcrierea video

Observăm apelurile multiple ale funcției Fibonacci pentru argumentele 3, 2, 1 și 0. Pe măsură ce argumentul crește, algoritmul devine ineficient. Ca urmare a unui apel la fibonacci(30), calculatorul apelează fibonacci(2) de peste o jumătate de milion de ori.

Aici putem folosi memoizarea, pentru a preveni recalcularea unui număr Fibonacci care a fost deja calculat.

Versiunea memoizată a algoritmului recursiv Fibonacci arată astfel:

Dacă $n$ ‍ este 0 sau 1, returnează $n$ ‍
Altfel, dacă $n$ ‍ este în memo, returnează valoarea din memo pentru $n$ ‍
Altfel,
- Calculează $fibonacci (n - 1) + fibonacci (n - 2)$ ‍
- Se reține rezultatul în memo
- Returnează rezultatul

Dacă vrei să vizualizezi execuția algoritmului memoizat implementat în JavaScript, urmărește acest video sau rulează vizualizarea chiar tu.

Pentru

n = 5

, calculatorul face 9 apeluri:

Acoperirea video Khan Academy

Memoized Recursive Fibonacci Calls (Diagrammed)Vezi transcrierea video

Versiunea originală a algoritmului necesita 15 apeluri ale funcției, deci prin memoizare s-au eliminat 6 apeluri.

Acest tabel arată numărul de apeluri pentru

n = 5

până la

n = 10

$n$ ‍	Original	Memoizat
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

Numărul total de apeluri ale funcției crește exponențial pentru algoritmul original, dar mult mai încet, liniar, pentru algoritmul memoizat.

Totuși, algoritmul memoizat necesită mai mult spațiu; suficient pentru un memo care stochează fiecare valoare returnată a lui

n

Bottom-up

Uneori, cea mai bună soluție de a îmbunătăți eficiența unui algoritm recursiv este să nu folosim recursivitatea deloc.

În cazul generării numerelor Fibonacci, o tehnică iterativă numită abordarea bottom-up poate salva atât timp cât și spațiu. Când folosim maniera bottom-up, calculatorul rezolvă mai întâi subproblemele și apoi folosește rezultatele parțiale pentru a ajunge la rezultatul final.

Maniera bottom-up pentru generarea numerelor Fibonacci arată astfel:

Dacă $n$ ‍ este 0 sau 1, returnează $n$ ‍
Altfel,
- Se creează variabila $twoBehind$ ‍ care memorează rezultatul pentru $(n - 2)$ ‍ și se inițializează cu 0
- Se creează variabila $oneBehind$ ‍ care memorează rezultatul pentru $(n - 1)$ ‍ și se inițializează cu 1
- Se creează variabila $result$ ‍ pentru a reține rezultatul final și se inițializează cu 0
- Se repetă de $(n - 1)$ ‍ ori:
  - Se actualizează $result$ ‍ cu valoarea sumei $twoBehind$ ‍ plus $oneBehind$ ‍
  - Se actualizează $twoBehind$ ‍ pentru a memora valoarea curentă a lui $oneBehind$ ‍
  - Se actualizează $oneBehind$ ‍ pentru a memora valoarea curentă a lui $result$ ‍
  - Returnează $result$ ‍

Această abordare nu face niciun apel recursiv; în schimb, folosește iterația pentru a însuma rezultate parțiale și pentru a calcula numărul.

Dacă vrei să vizualizezi execuția unui algoritm bottom-up implementat în JavaScript, urmărește acest video sau rulează chiar tu vizualizarea.

Algoritmul buttom-up are aceeași complexitate de timp

O (n)

ca algoritmul memoizat, dar spațiu doar

O (1)

, deoarece el memorează doar trei numere simultan.

Programare dinamică

Atât memoizarea cât și bottom-up sunt tehnici ale programării dinamice, o strategie de rezolvare a problemelor folosită în matematică și informatică.

Programarea dinamică poate fi folosită pentru probleme care au substructuri optime și subprobleme care se suprapun. Substructuri optime înseamnă că soluția optimă a problemei poate fi determinată pe baza soluțiilor optime ale subproblemelor sale. Cu alte cuvinte, fib(5) poate fi rezolvată cu fib(4) și fib(3). Suprapunerea subproblemelor are loc atunci când o subproblemă se rezolvă de mai multe ori, asă cum am văzut că fib(5) face mai multe apeluri recursive la fib(3) și fib(2), care sunt și ele recursive.

Programarea dinamică poate fi folosită pentru o gamă largă de probleme și implică tehnici mai evoluate decât cele învățate de noi aici. Ori de câte ori lucrezi la o problemă cu substructuri optime și subprobleme care se suprapun, gândește-te dacă nu cumva s-ar putea rezolva cu programarea dinamică.

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.

Computer science theory

Curs: Computer science theory > Unitatea 1

Memoizarea factorialului

Memoizarea funcției Fibonacci

Bottom-up

Programare dinamică

Vrei să te alături conversației?