| Referate informatica | Bac 2008 informatica | Recomanda unui prieten

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.





























CAPITOLUL 3

Backtracking recursiv

In capitolul 1 am prezentat rutina de backtracking clasica,nerecursiva.In acest capitol prezentam rutina de backtracking recursiva.Procedurile si functiile folosite sunt in general aceleasi,cu doua mici exceptii:
 SUCCESOR nu mai este procedura ci functie booleana ;
 rutina backtracking se transforma in procedura,care se apeleaza prin BACK(1)
Principiul de functionare al procedurii BACK,corespunzator unui nivel k este urmatorul:
• in situatia in care avem o solutie,o tiparim si revenim pe nivelul anterior
• in caz contrar se initializeaza nivelul si se cauta un succesor
• cand am gasit unul verificam daca este valid;procedura se autoapeleaza pentru (k+1) , in caz contrar urmand a se continua cautarea succesorului;
• daca nu avem succesor,se trece pe nivel inferior (k-1) prin iesirea din procedura BACK

Vom explica in continuare utilizarea backtrackingului recursiv prin generarea permutarilor:

program permutari;
type stiva=array[1..9] of integer;
var st:stiva;
ev:boolean;n,k:integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
function succesor(var st:stiva;k:integer):boolean;
begin
if st[k]begin
st[k]:=st[k]+1;
succesor:=true;
end
else succesor:=false;
end;
procedure valid(var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if st=st[k] then ev:=false;
end;

function solutie(k:integer):boolean;
begin
solutie:=(k=n+1);
end;

procedure tipar;
var i:integer;
begin
for i:=1 to n do writeln(st);
writeln;
end;

procedure back(k:integer);
begin
if solutie (k) then tipar
else
begin
init(k,st);
while succesor(st,k) do
begin
valid(ev,st,k);
if ev then back(k+1);
end;
end;
end;

begin
write('n=');readln(n);
back(1);