A. Consideratii teoretice

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.


B. Exemple

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:

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)


C. Teme

  1. 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.

  2. * Sa se scrie un program care citeste expresii in notatie poloneza (postfix) si le transforma in notatie infix, adaugand - evident - si parantezele necesare.