A. Considerații teoretice

Putem considera noțiunea de algoritm ca o exprimare specializată a unor definiții matematice, care ne ajută la construirea programelor în diverse limbaje de programare. În matematică, multe definții utilizează, pentru construirea unor concepte, o metodă specială numită recursivitate.

Se spune despre un concept că este recursiv dacă el este definit prin el însuși. În acest fel pot fi definite numerele naturale, șiruri de numere sau unele functii:

  1. numărul 1 este număr natural; succesorul unui număr natural este tot un număr natural (se presupune că este definită noțiunea de succesor);

  2. șirul numerelor triunghiulare (termenul de rang n se obține adunând pe n la termenul anterior)

    tri1 = 1;
    trin = n + trin-1, pentru n > 1

     

  3. funcția lui Ackermann:

    ack(m,n) = ack(m-1, ack(m, n-1));
    ack(0,n) = n+1; 
    ack(m,0) = ack(m-1,1); 
    

În acest fel se poate defini un set infinit de obiecte printr-un set finit de relații.

Cu ajutorul calculatorului, putem determina o submulțime finită a mulțimii acestor obiecte, transformând definițiile matematice recursive în algoritmi recursivi. Aceștia au particularitatea că, la un moment dat, se apelează pe ei înșiși. La modul general, algoritmul pentru calculul valorii unei funcții definite recursiv se poate exprima în felul urmator:

function f(x): <tip_functie>;
begin
    if p(x) then f := h(x)
    else f := f(g(x)) {apelul recursiv}
end;

Caracteristicile funcțiilor și procedurilor recursive:


B. Exemple

În continuare sunt prezentate câteva programe simple cu soluții recursive:

  1. Calculul celui mai mare divizor comun (algoritmul lui Euclid):

  2. cmmdc(a, b) = cmmd(b, a mod b), daca b <> 0,
    cmmdc(a, 0) = a
    

    Rezolvare:

    program CelMaiMareDivizorComun;
    var x, y, c: integer;
    
    function cmmdc(a, b: integer): integer;
    begin
      writeln('Intrare in CMMDC, a = ', a:1, ' b = ', b:1);
      readln;
      if b <> 0 then cmmdc := cmmdc(b, a mod b)
        else cmmdc := a;
      writeln('Iesire din CMMDC, a = ', a:1, ' b = ', b:1);
      readln;
    end;
    
    begin
      write(' x= '); readln(x);
      write(' y= '); readln(y);
      c := cmmdc(x, y);
      writeln(' cmmdc( ', x:1, ' , ', y:1,' ) = ', c:1);
    end.
    

    Click aici pentru sursa completă (ex03_1.pas)

  3. Calculul funcției modulo (restul împărțirii întregi):

    modulo(a, b) = modulo((a-b), b), daca a >= b,
    modulo(a, b) = a, daca a < b.
    

    Rezolvare:

    program FunctiaModulo;
    var
      x, y : integer;
      m: integer;
    
    function modulo (a, b : integer): integer;
    begin
      writeln(' Intrarea in MODULO, a = ', a:1, ' b = ', b:1);
      readln;
      if a >= b then modulo := modulo((a-b), b)
        else modulo := a;
      writeln(' Iesire din MODULO, a= ', a:1, ' b = ', b:1);
      readln
    end;
    
    begin
      write (' x= '); readln (x);
      write (' y= '); readln (y);
      m := modulo(x, y);
      writeln(' modulo(', x:1, ', ', y:1,' )= ', m:1 )
    end.
    

    Click aici pentru sursa completă (ex03_2.pas)

  4. Să se realizeze un program care citește o secvență de n caractere distincte și afișează toate aranjamentele luate câte m, cu repetiție, a celor n caractere.

    Rezolvare:
    Caracterele se vor citi în tabloul litere. În tabloul indici se va genera succesiunea de indici corespunzătoare aranjamentelor. Pentru patru caractere, de exemplu, în cazul în care se cer aranjamente cu repetiție luate câte două, se generează pe rând indicii:

    1,1	1,2	1,3	1,4	2,1	2,2	2,3	2,4 
    3,1	3,2	3,3	3,4	4,1	4,2	4,3	4,4

    Tipărirea indicilor se realizează "de la m la 1" deoarece și generarea lor a început de pe poziția m.

    program aranj_rep;
    
    const maxcar = 10; {numarul maxim de caractere acceptat}
    var
      litere: string[maxcar];
      indici: array[1..maxcar] of integer;
      m, n: integer;
    
    procedure tipareste;
    var i: integer;
    begin
      for i := m downto 1 do
        write(litere[indici[i]]);
      writeln
    end; {tipareste}
    
    procedure aranj_r(k: integer);
    var j: integer;
    begin
      if k = 0 then tipareste
      else
        for j := 1 to n do begin
          indici[k] := j;
          aranj_r(k-1)
        end
    end; {aranj_r}
    
    begin {programul principal}
      write('Numarul de caractere: ');
      readln(n);
      write('luate cate: ');
      readln(m);
      if (n > maxcar) or (m > n) then
        write('*** Date eronate ***')
      else begin
        write('Textul: ');
        readln(litere);
        aranj_r(m)
      end;
      readln
    end.
    

    Click aici pentru sursa completă (ex03_3.pas)

  5. Să se realizeze un program care citește o secvență de n caractere distincte și afișează toate aranjamentele luate câte m a celor n caractere.

    Rezolvare:
    În acest caz, la introducerea unei valori în tabloul indici, se verifică dacă ea mai este cumva prezentă în tablou; dacă da, atunci valoarea ei va fi înlocuită cu următoarea, înainte de a se încerca continuarea generări.

    program aranjamente;
              
    ...
              
    procedure aranj(k: integer);
    var j, t: integer;
    begin
      if k = 0 then tipareste
      else
        for j := 1 to n do begin
          indici[k] := j;
          t := m;
          while indici[t] <> j do
            t := t - 1;
          if t = k then aranj_r(k-1)
        end
    end; {aranj}
    
    begin {programul principal}
      write('Numarul de caractere: ');
      readln(n);
      write('luate cate: ');
      readln(m);
      if (n > maxcar) or (m > n) then
        write('*** Date eronate ***')
      else begin
        write('Textul: ');
        readln(litere);
        aranj(m)
      end;
      readln
    end.
    

    Click aici pentru sursa completă (ex03_4.pas)

  6. Să se realizeze un program care citește o secvență de n caractere distincte și afișează toate combinările de n luate câte m, cu repetiție, a celor n caractere.

    Rezolvare:
    Caracterele se vor citi în tabloul litere. În tabloul indici se va genera succesiunea de indici corespunzătoare combinărilor. Pentru patru caractere, de exemplu, în cazul în care se cer combinări cu repetiție luate câte două, se generează pe rând indicii:

    1,1	1,2	1,3	1,4	2,2	2,3	2,4 
    3,3	3,4	4,4

    În general grupările de indici sunt de așa natură încât un indice este urmat de altul mai mare sau cel puțin egal cu el.

    program comb_rep;
    
    const maxcar = 10; {numarul maxim de caractere acceptat}
    var
      litere: string[maxcar];
      indici: array[1..maxcar+1] of integer;
      m, n: integer;
    
    procedure tipareste;
    var i: integer;
    begin
      for i := m downto 1 do
        write(litere[indici[i]]);
      writeln
    end; {tipareste}
    
    procedure comb_r(k: integer);
    var j: integer;
    begin
      if k = 0 then tipareste
      else
        for j := indici[k+1] to n do begin
          indici[k] := j;
          comb_r(k-1)
        end
    end; {aranj_r}
    
    begin {programul principal}
      write('Numarul de caractere: ');
      readln(n);
      write('luate cate: ');
      readln(m);
      if (n > maxcar) or (m > n) then
        write('*** Date eronate ***')
      else begin
        write('Textul: ');
        readln(litere);
        indici[m+1] := 1;
        comb_r(m)
      end;
      readln
    end.

    Click aici pentru sursa completă (ex03_5.pas)


C. Teme

  1. Să se ruleze cele două programe, urmărind apelurile și valorile parametrilor de apel.

  2. Să se scrie un program recursiv care calculează valoarea funcției lui Ackermann pentru m și n citiți de la tastatură. Să se urmărească, prin intermediul ferestrei Watch, valorile parametrilor actuali de apel.

  3. Să se realizeze un program care citește o secvență de n caractere distincte și afișează toate combinările luate câte m a celor n caractere citite.

  4. * Să se caute o soluție nerecursivă pentru funcția lui Ackermann. Comparați efortul depus cu cel de la varianta recursivă.