NOTIUNI DESPRE RECURSIVITATE
Recursivitatea este una din notiunile fundamentale ale informaticii.Utilizarea frecventa a recursivitatii s-a facut dupa anii '80.Multe din limbajele de programare evoluate si mult utilizate(Fortran ,Cobol) nu permiteau scrierea programelor recursive.
In linii mari,recursivitatea este un mecanism general de elaborare a programelor .Ea a aparut din necesitati practice (transcrierea directa a formulelor matematice recursive) si reprezinta acel mecanism prin care un subprogram(procedura,functie) se autoapeleaza.
Daca lucrurile par usor de inteles in cazul functiilor,nu tot atat de simplu este sa aplicam recursivitatea utilizand proceduri.Astfel vom vedea ca putem genera recursiv probleme de genul permutarilor.
Un algoritm recursiv are la baza un mecanism de gandire diferit de cel cu care ne-am obisnuit deja.Atunci cand scriem un algoritm recursiv este suficient sa gandim ce se intampla la un anumit nivel pentru ca la orice nivel se intampla exact acelasi lucru.
Un algoritm recursiv corect trebuie sa se termine ,contrar programul se va termina cu eroare si nu vom primi rezultatul asteptat.Conditia de terminare va fi pusa de programator.
Un rezultat matematic de exceptie afirma ca pentru orice algoritm iterativ exista si unul recursiv echivalent(rezolva aceeasi problema) si invers,pentru orice algoritm recursiv exista si unul iterativ echivalent.
In continuare, raspundem la intrebarea:care este mecanismul intern al limbajului care permite ca un algoritm recursiv sa poata fi implementat?
Pentru a putea implementa recursivitatea ,se foloseste structura de date numita stiva.
Mecanismul unui astfel de program poate fi generalizat cu usurinta pentru obtinerea recursivitatii.Atunci cand o procedura sau o functie se autoapeleaza se depun in stiva:
valorile parametrilor transmisi prin valoare
adresele parametrilor transmisi prin referinta
valorile tuturor variabilelor locale(declarate la nivelul procedurii sau functiei)
Din punct de vedere al modului in care se realizeaza autoapelul ,exista doua tipuri de recursivitate:direct si indirecta.
Recursivitatea directa a fost deja prezentata.Recursivitatea indirecta are loc atunci cand o procedura (functie) apeleaza o alta procedura(functie),care la randul ei o apeleaza pe ea.
Un astfel de exemplu ar fi urmatorul:
Se considera doua valori reale,pozitive a0,b0 si n un numar natural.
Definim sirul:
an=(an-1+bn-1)/2 bn=an-1bn-1
Vom folosi doua functii a(n) si b(n).Fiecare dintre ele se autoapeleaza dar o apeleaza si pe cealalalta.
