Recursivitatea presupune executia repetata a unei portiuni de program. In
contrast cu iteratia, in cadrul recursivitatii, conditia de oprire este
verificata in cursul executiei secventei de program (si nu la sfarsit, ca la
iteratie). In caz de rezultat negativ (procedura nu s-a incheiat) intreaga
portiune de program este apelata din nou ca subprogram (procedura) de ea
insasi. In momentul satisfacerii conditiei de oprire, se reia executia
programului de la apelul recursiv in jos de atatea ori cate apeluri recursive
au fost facute.
Structurile de program necesare si suficiente in exprimarea recursivitatii
sunt procedurile care pot fi apelate prin nume (limbajul PASCAL oferind
aceasta posibilitate).
De regula unei proceduri i se asociaza un set de obiecte locale procedurii
(variabile, constante, tipuri si proceduri) si care nu exista si nu au inteles
inafara ei. De fiecare data cand o procedura este apelata recursiv se creeaza
un nou set de astfel de obiecte locale. Desi au acelasi nume ca si cele
corespunzatoare lor din instanta anterioara a procedurii, ele au valori
distincte si orice conflict de nume este evitat prin regulile care stabilesc
domeniul de existenta al identificatorilor. Identificatorii se refera
intotdeauna la setul cel mai recent creat de variabile. O mare atentie trebuie
acordata conditiei de terminare, fara de care un apel recursiv conduce la o
bucla de program infinita.
O problema aparent simpla este evaluarea expresiilor aritmetice. Dandu-se
astfel de expresii, de exemplu:
E1=(A+B*C-D)*I
E2=(A+B)*D+((A+C)*E-A)*I etc.
|
Se citesc valorile identificatorilor si se cer valorile expresiilor. O
metoda uzuala este transformarea expresiilor din format infix (operatorul
intre operanzi) in format postfix (operatorul dupa cei doi operanzi). De
exemplu:
E1 devine ABC*+D-I*
E2 devine AB+D*AC+E*A-I*+
|
Avantajul notatiei postfix (poloneze) este acela ca indica ordinea corecta
a executiei operatiilor fara a utiliza paranteze, iar expresia poate fi
evaluata printr-o simpla baleiere cu ajutorul urmatorului algoritm:
-
expresia este memorata intr-o variabila sir de caractere;
E : string
OP1,OP2 : real;
|
si valorile intr-un sir de numere reale:
VALOARE : array ['A'..'Z'] of real;
|
-
se va folosi si o structura de tip stiva cu elemente reale, cu
operatiile asociate push si pop:
begin
I := 1;
while I <= length (E) do
begin
if E[I] on LitereMari then push (VALOARE[E[I]])
else
begin
OP2 := pop;
OP1 := pop;
case E[I] of
'+' : OP1 := OP1 + OP2;
'-' : OP1 := OP1 - OP2;
'*' : OP1 := OP1 - OP2;
'/' : OP1 := OP1 / OP2;
end;
push (OP1);
end;
I := I+1
end
end;
|
Pentru a transforma expresiile din format infix in format postfix definim
in mod recursiv diagramele sintactice ale expresiilor infix:
Transformarea ceruta se poate realiza construind cate o procedura
individuala de conversie pentru fiecare constructie sintactica (expresie,
termen, factor). Acestea fiind definite recursiv, si in cadrul programului se
vor apela recursiv (indirect).
var
ExInfix, ExPostfix : string;
I: integer;
ch: char;
procedure AvansUnCaracter;
begin
repeat
ch := ExInfix[I];
I := I + 1;
until ch <> ' ' { eliminarea spatiilor nesemnificative }
end;
procedure Expresie;
var Operand : char;
procedure Termen;
var OperandTermen : char;
procedure Factor;
begin
if ch = '(' then begin
AvansUnCaracter;
Expresie; { ch va fi = ')' }
end else ExPostfix := ExPostfix + ch; { concatenare de siruri }
AvansUnCaracter
end;
begin { procedura termen }
Factor;
while ch in ['*','/'] do
begin
OperandTermen := ch;
AvansUnCaracter;
Factor;
ExPostfix := ExPostfix + OperandTermen
end;
end;
begin { procedura expresie }
Termen;
while ch in ['+','-'] do begin
Operand := ch;
AvansUnCaracter;
Termen;
ExPostfix := ExPostfix + Operand
end;
end;
begin { exemplu de initializare si apelare }
{...}
readln (ExInfix);
ExPostfix := ''; { sirvid }
I:=1;
AvansUnCaracter;
Expresie;
{ se obtine in variabila ExPostfix rezultatul conversiei care
poate fi evaluat cu baleierea prezentata }
writeln(ExPostFix);
end.
|
Click aici pentru sursa completa
(ex08_1.pas)
-
Sa se scrie un program care citeste un numar neprecizat de expresii
infix compuse din caracterele 'A'..'Z' ca simboluri, operanzii '+', '-',
'*', '/' si parantezele '(', ')' ronde, apoi citeste valorile tuturor
simbolurilor intalnite in expresiile citite intr-o forma interactiva si
afiseaza valoarea fiecarei expresii impreuna cu formula ce o denota.
-
* Sa se scrie un program care citeste expresii in notatie poloneza
(postfix) si le transforma in notatie infix, adaugand - evident - si
parantezele necesare.