ReCuRsIvItAtEReCuRsIvItAtE

SuBpRoGrAmESuBpRoGrAmE

Recursivitatea În matematică şi informatică, recursivitatea sau recursia este un mod de a defini unele funcţii. Funcţia este recursivă, dacă definiţia ei foloseşte o referire la ea însăşi, creând la prima vedere un cerc vicios, care însă este numai aparent, nu şi real.Recursivitatea e strins legata de iteratie, dar daca iteratia e executia repetata a unei portiuni de program, pana la indeplinirea unei conditii (while, repeat, for), recursivitatea presupune executia repetata a unui modul, insa in cursul executiei lui (si nu la sfirsit, ca in cazul iteratiei), se verifica o conditie a carei nesatisfacere, implica reluarea executiei modulului de la inceputul sau. Atunci un program recursiv poate fi exprimat: P=M(Si,P) , unde M este multimea ce contine instructiunile Si si pe P insusi. Structurile de program necesare si suficiente in exprimarea recursivitatii sint procedurile si subrutinele ce pot fi apelate prin nume. In PASCAL, exista doua tipuri de parametri formali (ce apar in antetul unei proceduri sau functii) : valoare si variabila (ultimii au numele precedat de cuvintul cheie var).

Apelul recursiv al unei proceduri (functii) face ca pentru toti parametrii-valoare sa se creeze copii locale apelului curent (in stiva) , acestea fiind referite si asupra lor facindu-se modificarile in timpul executiei curente a procedurii (functiei). Cind executia procedurii (functiei) se termina, copiile sint extrase din stiva, astfel incit modificarile operate asupra parametrilor-valoare nu afecteaza parametrii efectivi de apel, corespunzatori.De asemenea pentru toate variabilele locale se rezerva spatiu la fiecare apel recursiv.

De retinut:-pentru fiecare apel recursiv al unei

proceduri (functii) se creaza copii locale ale parametrilor valoare si variabilelor locale, ceea ce poate duce la risipa de

memorie;-orice In cazul parametrilor-variabila, nu se creaza copii locale, ci operarea se

face direct asupra spatiului de memorie afectat parametrilor efectivi, de apel.parametru-variabila poate fi suprimat

prin referirea directa in procedura (functie) a variabilei ce figura ca

parametru de apel.

REGULI PENTRU SCRIEREA SUBPROGRAMELOR RECURSIVE:

Orice subprogram recursiv trebuie să se execute, cel puţin o dată, fără a se autoapela. Condiţia de oprire se va scrie pentru valori extreme ale mulţimii valorilor de testat.Autoapelurile trebuie să conducă spre situaţia (situaţiile ) în care subprogramul se execută direct (fără autoapel).

TEHNICA ELIMINARII RECURSIVITATII

Orice program recursiv poate fi transformat in unul iterativ, dar algoritmul sau poate deveni mai complicat si mai greu de inteles. De multe ori, solutia unei probleme poate fi elaborata mult mai usor, mai clar si mai simplu de verificat, printr-un algoritm recursiv.Dar pentru implementare, poate fi necesara transformarea algoritmului recursiv in unul nerecursiv, in situatiile:-solutia problemei trebuie scrisa intr-un limbaj nerecursiv; un caz particular sint compilatoarele ce "traduc" un program recursiv dintr-un limbaj de nivel inalt in cod masina (nerecursiv)-varianta recursiva ar duce la o viteza de executie si spatiu de memorie prea mari, transformarea in una nerecursiva, eliminind dezavantajele.

Se va prezenta una din metodele de eliminare a recursivitatii ce foloseste o structura de date de tip stiva.In scrierea unei varianta nerecursive, trebuie parcursi toti pasii implicati in varianta recursiva, prin tehnici nerecursive.Recursivitatea implica folosirea a cel putin unei stive. La fiecare apel recursiv sint depuse in stiva niste date, care sint extrase la revenirea din acel apel. E simplu daca datele pentru un apel se organizeaza intr-un record, un apel insemnind introducerea in stiva a unui record, revenirea, extragerea lui.

Se prezinta eliminarea recursivitatii pentru un program simplu, care

citeste caracterele tastate pe o linie, tiparindu-le apoi in ordine inversa program var_recursiva;

procedure prel_car; var car:char; begin read(car); if not eoln then prel_car; write(car) end; begin prel_car end.

program var_nerecursiva; begin *initializeaza stiva while not eoln do begin read(car); push(car) end; while not stiva_goala do begin pop(car); write(car) end end.

TIPURI DE RECURSIVITATE

Din punct de vedere al modului in care se realizeaza autoapelul ,exista doua tipuri de recursivitate:1.subprograme direct recursive: - un subprogram Q în corpul căruia există cel puţin un autoapel (Q apelează pe Q) se numeşte subprogram direct recursiv2.subprograme indirect recursive: - două subprograme A şi B se numesc indirect recusrive dacă se apelează reciproc (A apelează pe B şi B apelează A) .

Pentru a putea fi executat, orice subprogram (nerecursiv sau recursiv) trebuie să fie declarat înaintea modulului apelant. Dacă dorim să scriem suprogramul după modulul apelant,atunci trebuie să facem o declaraţie anticipată a suprogramului respectiv ,cu directiva forward.Presupunem că avem două proceduri A şi B care se apelează reciproc ,scrise în această ordine.Procedura A apelează procedura B,dar modulul apelat B se află după cel apelant A. În consecinţă, pentru ca acest apel să poată fi executat, trebuie să facem o declaraţie anticipată a procedurii B,folosind directiva `forward`:

procedure B(….);forward;procedure A(….);

………………….Begin

…………………b(….);

…………………end;

procedure B(….);…………………

begin…………………

A(….);…………………

end;

EXEMPLE DE ALGORITMI RECURSIVI

Algoritmi de traversare si inversare a unei structuriTraversarea si inversarea unei structuri inseamna efectuarea unor operatii oarecare asupra tuturor elementelor unei structuri in ordine directa, respectiv in ordine inversa.Desi mai uzuale sint variantele iterative, caz in care inversarea echivaleaza cu doua traversari directe (o salvare in stiva urmata de parcurgerea stivei), variantele recursive sint mai elegante si concise. Se pot aplica structurilor de tip tablou, lista, fisier si pot fi o solutie pentru diverse probleme (transformarea unui intreg dintr-o baza in alta, etc).

Intr-o forma generala, algoritmii se pot scrie:

procedure traversare(element:tip_element); {apelul initial} {al procedurii se face cu primul element al structurii} begin prelucrare(element); if element <> ultimul_din_structura then traversare(element_urmator) end; procedure inversare(element:tip_element); {apelul initial} {al procedurii se face cu primul element al structurii} begin if element <> ultimul_din_structura then traversare(element_urmator); prelucrare(element)

end; De observat importanta ca parametrul formal al celor doua proceduri sa fie de tip valoare, pentru a nu fi alterat de apelul recursiv.

O definitie recursiva e cea in care un obiect se defineste prin el insusi. Definitia contine o conditie de terminare, indicind modul de parasire a definitiei si o parte ce precizeaza definirea recursiva propriu-zisa.

Ca exemple: algoritmul lui Euclid de aflare a c.m.m.d.c., factorialul, ridicarea la o putere intrega (prin inmultiri repetate), definirea recursiva a unei expresii aritmetice, curbele recursive, un mod de a privi permutarile, etc.

Algoritmi care implementeaza definitii recursive

Algoritmi de divizare

Tehnica divizarii ("divide and conquer"), fundamentala in elaborarea algoritmilor, consta in descompunerea unei probleme complexe in mai multe subprobleme a caror rezolvare e mai simpla si din solutiile carora se poate determina solutia problemei initiale (exemple: gasirea minimului si maximului valorilor elementelor unui tablou, cautarea binara, sortare Quicksort, turnurile din Hanoi).

Un algoritm de divizare general s-ar putea scrie:

procedure rezolva(x:problema); begin

if {x e divizibil in subprobleme} then begin {divide pe x in parti x1,...,xk}

rezolva(x1); {...} rezolva(xk); {combina solutiile partiale intr-o} {solutie pentru x} end else {rezolva pe x direct} end;

Algoritmi cu revenire (backtracking)

Metoda se aplica problemelor in care solutia se poate reprezenta sub forma unui vector x=(x1,x2,...xn) c S=S1 x S2 x...x Sn, unde multimile Si sint finite, S numindu-se spatiul solutiilor posibile. In particular, Si sint identice avind acelasi numar M de elemente. Pentru fiecare problema concreta sint date anumite relatii intre componentele vectorului x, numite conditii interne.Determinarea tuturor solutiilor rezultat se poate face generind toate solutiile posibile si verificind apoi care satisfac conditiile interne. Dar timpul de calcul ar fi foarte mare (daca multimile Si ar avea numai cite 2 elemente, timpul ar fi proportional cu 2**n).

Metoda backtracking urmareste evitarea generarii tuturor solutiilor. Elementele vectorului x primesc valori pe rind, lui x1 i se atribuie valori, doar daca x1,x2,...,xi-1 au primit deja, valorile atribuite trebuind sa verifice conditiile de continuitate referitoare la x1,x2,...,xi. Doar apoi se trece la calculul lui xi+1. In cazul neindeplinirii conditiilor de continuitate, se alege urmatoarea valoare posibila pentru xi, daca Si a fost epuizat, se micsoreaza i, incercind o alta alegere pentru xi-1.

procedure backtracking(i:integer); {gaseste valoarea lui xi}

var posibilitate:integer; {pentru toate valorile} {posibile ale lui xi}

begin for posibilitate:=1 to M do

begin if acceptabila then begin

inregisteaza_posibilitatea;

if i < n then backtracking(i+1)

else afiseaza_solutia: sterge_inregistrarea

end

end end;

Pe acesta metoda se bazeaza rezolvarea unor probleme clasice ca: "opt regine", a "relatiilor stabile", colorarea unei harti, taierea unui fir de lungime l in parti de lungimi date, etc.

O varianta a acestei metode este cea in care, pentru un xi c vector solutie , xi+1 poate fi ales dintr-un numar M de posibilitati:

procedure back1(i:posibilitate); begin if acceptabila then begin inregistreaza; if solutie_incompleta then for k:=1 to M do back1(posibilitate_k) else tipareste_solutia; sterge_inregistrarea

end

end; Aceasta varianta se foloseste la rezolvarea problemelor: "saritura calului", iesirea dint-un labirint, etc. Se preteaza atunci cind pasul initial este definit si/sau numarul de pasi ai solutie nu este cunoscut.

SUBPROGRAMESUBPROGRAME Subprogramele sunt parti din program identificate printr-un Subprogramele sunt parti din program identificate printr-un

nume, prin intermediul caruia vor fi apelate. nume, prin intermediul caruia vor fi apelate. Vom scrie subprograme atunci cand: Vom scrie subprograme atunci cand: -anumite instructiuni dintr-un program apar in mai multe locuri; -anumite instructiuni dintr-un program apar in mai multe locuri; -dorim sa impartim problema in subprograme; -dorim sa impartim problema in subprograme; Subprogramele pot fi: Subprogramele pot fi: functie-returneaza intotdeauna o singura valoare;functie-returneaza intotdeauna o singura valoare; proceduri-pot returna zero, una sau mai multe valori;proceduri-pot returna zero, una sau mai multe valori; Functiile si procedurile pot fi Functiile si procedurile pot fi standard(existente deja in limbajul Pascal) standard(existente deja in limbajul Pascal) definite de utilizator. definite de utilizator. Functii standard: int, trunc, sqr, sqrt, abs, chr, ord, pred, succ; Functii standard: int, trunc, sqr, sqrt, abs, chr, ord, pred, succ; Proceduri standard: read, readln, write, writeln, val, str, inc, Proceduri standard: read, readln, write, writeln, val, str, inc,

dec; dec; OBS!OBS! Atat procedurile,cat si functiile trebuie declarate inainte de a Atat procedurile,cat si functiile trebuie declarate inainte de a

fi apelate.fi apelate.

STRUCTURA DE BLOCSTRUCTURA DE BLOC Un bloc cuprinde: Un bloc cuprinde: o parte optionala, alcatuita din o parte optionala, alcatuita din

declaratiile de constante, declaratiile de constante, variabile, tipuri; variabile, tipuri;

o o parte obligatorie, ce cuprinde parte obligatorie, ce cuprinde instructiuniinstructiuni

OBS!OBS!Programele Pascal pot cuprinde mai multe Programele Pascal pot cuprinde mai multe blocuri imbricate(incluse unul in altul).Prin domeniul blocuri imbricate(incluse unul in altul).Prin domeniul de valabilitate al unui identificator se intelegede valabilitate al unui identificator se intelege zona de zona de program in care este valabila declaratia sau definitia program in care este valabila declaratia sau definitia acelui identificator. acelui identificator.

Entitatile definite intr-un bloc sunt valabile (vizibile) Entitatile definite intr-un bloc sunt valabile (vizibile) numai in interiorul blocului , motiv pentru care numai in interiorul blocului , motiv pentru care acestea se numesc entitati locale.Aceste entitati apar acestea se numesc entitati locale.Aceste entitati apar la lansarea in executie a blocului si dispar la la lansarea in executie a blocului si dispar la terminarea executiei blocului.Daca blocul cuprinde terminarea executiei blocului.Daca blocul cuprinde blocuri incluse atunci entitatile sunt vizibile si in blocuri incluse atunci entitatile sunt vizibile si in blocurile imbricate daca nu au fost redefinite , motiv blocurile imbricate daca nu au fost redefinite , motiv pentru care aceste entitati se numesc entitati globale.pentru care aceste entitati se numesc entitati globale.

OBS!OBS! Domeniul de valabilitate al unei variabile este Domeniul de valabilitate al unei variabile este blocului in care au fost declarate, inclusiv in blocurile blocului in care au fost declarate, inclusiv in blocurile incluse daca in acestea nu au fost redefinite.incluse daca in acestea nu au fost redefinite.

DECLARAREA DECLARAREA SUBPROGRAMELORSUBPROGRAMELOR

a)Proceduri a)Proceduri procedure nume(lista parametri formali), unde nume procedure nume(lista parametri formali), unde nume

reprezinta numele subprogramului , iar parametri reprezinta numele subprogramului , iar parametri formali reprezinta entitati cu care lucreaza formali reprezinta entitati cu care lucreaza

subprogramul si sunt cunoscuti numai in interiorul subprogramul si sunt cunoscuti numai in interiorul acestora.Lista parametrilor formali cuprinde atat acestora.Lista parametrilor formali cuprinde atat

numele parametrilor, cat si tipul lor.Este posibil ca o numele parametrilor, cat si tipul lor.Este posibil ca o partedein parametri sa fie precedati de cuvantul partedein parametri sa fie precedati de cuvantul

rezervat var. rezervat var. EX: procedure test(x,y:integer; var z: byte); x,y-date EX: procedure test(x,y:integer; var z: byte); x,y-date

de intrare z-date de iesire de intrare z-date de iesire procedure afis(x:integer); procedure afis(x:integer);

procedure suma(a,b:real;var s:real); procedure suma(a,b:real;var s:real); procedure p(m,n,t:real;var x: boolean, var s, u: real);procedure p(m,n,t:real;var x: boolean, var s, u: real);

OBS!OBS! Lista parametrilor formali poate fi vida. Lista parametrilor formali poate fi vida.

b)Functii b)Functii function nume(lista parametri formali):tip; function nume(lista parametri formali):tip;

unde nume reprezinta numele functiei, unde nume reprezinta numele functiei, lista parametri formali reprezinta lista parametri formali reprezinta

parametri formali , iar tip reprezinta tipul parametri formali , iar tip reprezinta tipul vlorii returnate de functie. vlorii returnate de functie.

EX: function suma(x,y:integer):integer; EX: function suma(x,y:integer):integer;

functie cu numele suma ,prametri formali functie cu numele suma ,prametri formali x si y si valoarea returnata de tip integer x si y si valoarea returnata de tip integer

function cmmdc(a,b: word):word; function cmmdc(a,b: word):word; function prim(n:real):boolean;function prim(n:real):boolean;

APELUL APELUL SUBPROGRAMELORSUBPROGRAMELOR

a)Apelul procedurilor: a)Apelul procedurilor: Apelul procedurilor se face printr-o Apelul procedurilor se face printr-o

instructiune de apel de forma instructiune de apel de forma `nume(lista prametri efectivi)`, unde `nume(lista prametri efectivi)`, unde `nume` reprezinta numele procedurii, `nume` reprezinta numele procedurii, iar lista parametri efectivi(actuali) iar lista parametri efectivi(actuali) reprezinta variabilele cu care lucreaza reprezinta variabilele cu care lucreaza efectiv subprogramul.efectiv subprogramul.

b)Apelul functiilor :Se face printr-o b)Apelul functiilor :Se face printr-o instructiune de apel de forma instructiune de apel de forma variab:=nume(lista parametri variab:=nume(lista parametri efectivi); unde `nume` reprezinta efectivi); unde `nume` reprezinta numele functiei ,lista parametri numele functiei ,lista parametri efectivi reprezinta parametri efectivi. efectivi reprezinta parametri efectivi.

OBS!OBS! Parametri efectivi trebuie sa Parametri efectivi trebuie sa corespunda ca numar, tip si ordine cu corespunda ca numar, tip si ordine cu parametri formali.parametri formali.