= Racket: Recursivitate =


* Responsabil: [[popabogdan97@gmail.com|Bogdan Popa]]
* Data publicării: 24.02.2020
* Data ultimei modificări: 24.02.2020


== Obiective ==


Scopul acestui laborator este studierea diverselor **tipuri** de recursivitate, într-o manieră comparativă, și a modalităților de **eficientizare** a proceselor recursive.


Aspectele urmărite sunt: 
* diferențele dintre mai multe **tipuri** de recursivitate, din perspectiva resurselor utilizate și, deci, a eficienței:
  * pe stivă
  * pe coadă
  * arborescentă
* modalități de **transformare** între diversele tipuri.


Arhiva de [[#Resurse|resurse]] conține un fișier cu **exerciții rezolvate**, la care textul face trimitere.
== Recursivitate ==


Citiți secțiunea **//[[https://web.mit.edu/alexmv/6.037/sicp.pdf#subsection.1.2.1|1.2.1 Linear Recursion and Iteration]]//** a cărții //[[https://web.mit.edu/alexmv/6.037/sicp.pdf|Structure and Interpretation of Computer Programs]]//, ediția a doua, până la //Example: Counting change//. Apoi, parcurgeți **rezumatul** următor, alături de **exercițiile rezolvate**.


În timpul rulării, un program utilizează o zonă de memorie, denumită **stivă**, cu informațiile de care (mai) are nevoie, în diferite momente. La fiecare **apel** de funcție, spațiul ocupat pe stivă **crește**. La fiecare **revenire** dintr-un apel, cu o anumită valoare, spațiul ocupat pe stivă **scade**. Când recursivitatea este foarte adâncă --- există multe apeluri de funcție realizate, din care nu s-a revenit încă --- spațiul ocupat pe stivă devine mult prea mare. Acest lucru **influențează**:
* **Memoria**, **principala** resursă afectată. În unele situații, trebuie reținute foarte multe informații. De exemplu, pentru o implementare particulară a funcției ''factorial'', ar putea fi necesară reținerea tuturor înmulțirilor care trebuie efectuate la revenirea din recursivitate. Observați exercițiile rezolvate 1 și 2. De obicei, stiva are o dimensiune **maximă**, iar, atunci când aceasta este epuizată, programul se termină brusc, cu o **eroare** de tip „stack overflow”.
* **Timpul**, care, în locul **redimensionării** stivei, ar putea fi utilizat pentru alte calcule, programul rezultat fiind, astfel, mai rapid.

=== Recursivitate pe stivă ===
O funcție este recursivă **pe stivă** dacă apelul recursiv este parte a unei expresii mai complexe, fiind necesară **reținerea** de informații, pe stivă, pe avansul în recursivitate. 

==== Exemplu ====
<code racket>
(define (factorial n)
      (if (= n 0)
          1
          (* n (factorial (- n 1)))))
</code>

=== Recursivitate pe coadă ===
O funcție este recursivă **pe coadă** dacă valoarea întoarsă de apelul recursiv constituie valoarea de retur a apelului curent, i.e. apelul recursiv este un //[[http://en.wikipedia.org/wiki/Tail_call|tail call]]//, **nefiind** necesară reținerea de informație pe stivă.


Când o funcție este recursivă **pe coadă**, i se poate aplica **//tail call optimization//**. Din moment ce valoarea întoarsă de apelul curent este aceeași cu valoarea întoarsă de apelul recursiv, nu mai este necesară reținerea de informație pe stivă, pentru apelul curent, iar zona aferentă de stivă poate fi **înlocuită**, complet, de cea corespunzătoare apelului recursiv. Astfel, nu mai este necesară stocarea stării fiecărei funcții din apelul recursiv, **spațiul** utilizat fiind **O(1)**. Implementarea de Racket pe care o folosim conține această optimizare, ca parte a specificației.


**Optimizarea** menționată mai sus se poate aplica și în situații **mai relaxate**, precum //[[http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons|Tail recursion modulo cons]]//. Aici este permisă antrenarea valorii întoarse de apelul recursiv în anumite operații de **construcție**, cum este ''cons'' pentru liste. Pentru mai multe detalii, citiți informațiile de la adresa precedentă.


Pornind de la cele de mai sus, consumul de resurse poate fi **redus** semnificativ, prin **transformarea** recursivității **pe stivă** în recursivitate **pe coadă** (numită și transformare a recursivității în iterație). Metoda de transformare prezentată în laborator constă în utilizarea unui **acumulator**, ca **parametru** al funcției, în care rezultatul final se construiește treptat, pe **avansul** în recursivitate, în loc de revenire.

==== Exemplu ====
<code racket>
(define (tail-recursion n acc)
  (if (= n 0)
      acc
      (tail-recursion (- n 1) (* n acc))))

(define (factorial n)
      (tail-recursion n 1))
</code>

Este important să aveți în vedere faptul că **funcțiile** recursive pe coadă **nu sunt definite** de prezența unui **acumulator**, precum nici funcțiile recursive pe stivă nu sunt definite de absența acestui acumulator. **Diferența** dintre cele două tipuri de funcții constă în **necesitatea** funcțiilor recursive **pe stivă** de a se **întoarce** din recursivitate pentru a **prelucra rezultatul**, respectiv **capacitatea** funcțiilor recursive **pe coadă** de a **genera** un rezultat **pe parcursul** apelului recursiv.

==== Exemplu ====
<code racket>
(define (member x L)  ;; O posibilă implementare a funcției member
  (if (null? L) #f  ;; Caz de bază, lista vidă nu conține elemente
      (if (equal? x (car L)) (cdr L)  ;; Verificăm dacă elementul căutat este primul termen din listă
          (member x (cdr L)))))  ;; Dacă nu, căutăm în restul listei
</code>

=== Recursivitate arborescentă ===
Recursivitatea arborescentă apare în cazul funcțiilor care conțin, în implementare, cel puțin două apeluri recursive care se execută necondiționat.

==== Exemplu ====
<code racket>
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
</code>

{{  19:laboratoare:racket:fibonacci.png  }}

Se poate observa **ineficiența** implementării recursive pe stivă, atât din punct de vedere **temporal** (datorată **apelurilor duplicate**, precum apelul funcției pentru n = 3), cât și din punct de vedere **spațial** (datorată **stocării de "stack frames"** necesare pentru revenirea din recursivitate).

În cadrul [[#Resurse|exercițiilor rezolvate]] puteți observa mai în detaliu diferențele dintre recursivitatea pe stivă si cea pe coada (inclusiv în contextul funcției ''fib'').
== Resurse ==


Citiți exercițiile **rezolvate**; apoi, rezolvați exercițiile **propuse**.

* {{:20:laboratoare:racket:recursivitate-ex.zip | Exerciții rezolvate și propuse}}
* {{ :20:laboratoare:racket:recursive-images-sol.zip | Soluții}}
* {{ :20:laboratoare:racket:recursivitate-cheatsheet.pdf |Cheatsheet}} (Nu uitați și de {{ :20:laboratoare:racket:intro-cheatsheet.pdf |cheatsheet}}-ul de la primul laborator)


== Referințe ==


* //[[https://web.mit.edu/alexmv/6.037/sicp.pdf|Structure and Interpretation of Computer Programs]]//, ediția a doua
* //[[http://en.wikipedia.org/wiki/Tail_call|Tail call]]//