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 unlanț 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ă.
Î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.
Cat despre stivă, aceasta 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.
Post a Comment