Recursivitate

Un algoritm se numește recursiv dacă se autoapelează adică, dacă în corpul său există un modul care se autoapeleză. Recursivitatea se realizează cu ajutorul subprogramelor. Un subprogram care se autoapelează se numește subprogram recursiv.

Prin urmare un algortim se numește recursiv sau un program se numește recursiv dacă conține cel puțin un subprogram care se autoapelează.

Recursivitatea se realizează în felul următor:

-          Din afara subprogramului facem un apel al subprogramului

-          Dacă nu este îndeplinită o condiție (numită condiție de oprire), algoritmul se autoapelează de un anumit număr de ori (până când e îndeplinită condiția). La fiecare nouă autoapelare a subprogramului se reexecută secvența de instrucțiuni din corpul său, eventual cu alte date, creându-se un lanț de autoapeluri recursive. Dacă condiția de oprire nu este îndeplinită niciodată sau nu există, algoritmul va avea un rezultat asemănător intrării într-un ciclu infinit.

Intuitiv, putem spune că un algoritm recursiv are același efect ca și o buclă (ciclu, instrucțiune repetitivă) – repetă execția unui set de instrucțiuni. În mod analog, deducem că repetarea nu trebuie să se realizeze de un număr infinit de ori. De aici provine necesitatea existenței condiției de oprire.

Prin urmare orice subprogram recursiv trebuie să îndeplinească următoarele condiții:

-          să se poată executa cel puțin o dată fără a se autoapela (când apare condiția de oprire);

-          toate autoapelurile să se producă astfel încât la un moment dat să se ajungă la îndeplinirea condiției de oprire.

Cea mai mare parte a algoritmilor repetitivi se pot implementa într-o variantă nerecursivă (numită variantă iterativă) folosind instrucțiuni recursive, cât și într-o variantă recursivă atunci când conțin un modul definit recursiv.

Varianta de implementare rămâne la latitudinea programatorului.

Varianta recursivă este recomandată în cazul în care problemele sunt definite printr-o relație de recurență însă acest timp de algoritmi sunt mai greu de urmărit și de obicei necesită un timp de execuție mai mare.

În viața de zi cu zi ne putem întâlni cu șiruri de elemente definite recurent ca de exemplu:

-          șirul numerelor naturale (primul număr este 0; celelalte se obțin din precedentul adăugându-se 1)

-          suma numerelor naturale (inițial suma este 0; fiecare element care trebuie adăugat se adaugă la suma obținută din elementele aflate înaintea lui)

-          șirul lui Fibonacci

-          cmmdc dintre 2 numere

-          etc

De asemenea ne înâlnim și cu alte elemente și fenomene care pot permite o reprezentare recursivă:

-          succesiunea zilelor și nopților

-          o cameră de luat vederi care este îndreptată spre o oglindă. Vă propun să vă gândiți  ce se vede în cameră.

Etc.

După cum am mai spus execuția subprogramelor recursive seamănă cu execuția instrucțiunilor repetitive. Difereța constă în faptul că autoexecuția, în cazul programelor recursive, nu se poate realiza de un număr infinit de ori deoarece la fiecare autoapel se păstrează în stiva calculatorului variabilele locale și parametrii trimiși prin valoare iar stiva are o dimensiune limitată.

Reamintim că Stiva reprezintă o succesiune ordonată de elemente, delimitată de două capete, în care adăugarea și eliminarea elementelor se poate face pe la un singur capăt, numit vârful stivei. Extragerea elementelor se realizează în ordine inversă introducerii lor.

În cazul unui subprogram recursiv (care este în același timp modul apelat și apelant) acest mecanism al stivei este de o foarte mare importanță: atunci când se execută un lanț de autoapeluri recursive, la fiecare autoapel variabilele locale și parametrii subprogramului recursiv se salvează pe stivă, iar la revenirea aceste valori sunt preluate din stivă în ordinea inversă a introducerii lor.

Cum lucrează un subprogram recursiv?

Presupunem că dorim să găsim valoarea celui de-al n-lea termen din șirul lui Fibonacci. șirul este definit în felul următor:

F(0)=0, dacă n=0

F(1)=1, dacă n=1

F(n)=F(n-1)+F(n-2), dacă n>=2.

Ne propunem să găsim cât este f(7), adică cel de-al șaptelea termen din șirul lui Fibonacci.

Apelăm funcția cu parametru 7 dar observăm că nu putem calcula decât dacă știm valorile termenilor al șaselea și al cincelea. Termenul al șaselea nu-l putem calcula decât dacă știm valorile termenilor al cincelea și al patrulea șamd.

F(7)=F(6)+F(5)

F(6)=F(5)+F(4)

F(5)=F(4)+F(3)

F(4)=F(3)+F(2)

F(3)=F(2)+F(1)

F(2)=F(1)+F(0)

F(1)=1

F(0)=0

Ne întoarcem preluând din stivă rezultatele salvate.

Vom calcula mai întâi pe F(2) pentru că știm cât este F(1) și F(0). F(2)=1+0=1.

Știind cât este F(2) putem calcula pe F(3). F(3)=F(2)+F(1)=1+1=2.

Acum putem calcula și pe F(4)=F(3)+F(2)=2+1=3.

Avem toate elementele pentru a calcula și F(5)=F(4)+F(3)=3+2=5.

Ne întoarcem și la F(6)=F(5)+F(4)=5+3=8.

Acum putem să aflăm cât este al șaptelea termen din șirul lui Fibonacci: F(7)=F(6)+F(5)=8+5=13.

După câte se observă autoapeluri tind să se execute până se ajunge la condiția de oprire (adică condiția în cazul în care rezultatele sunt cunoscute, în cazul nostru pentru n=0 și pentru n=1) și apoi se preiau rezultatele intermediare din stiva calculatorului în calculând termenii intermediari.