Recursivitate subprograme recursive simple

RECURSIVITATE

• Subprograme recursive simple

Ce este recursivitatea ?

• Un algoritm se numește recursiv dacă se autoapelează adică, dacă în corpul său există un modul care se autoapeleză. Recursivitatea se realizează cu ajutorul subprogramelor. Un subprogram care se autoapelează se numește subprogram recursiv.

• Prin urmare un algortim se numește recursiv sau un program se numește recursiv dacă conține cel puțin un subprogram care se autoapelează.

• Î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.

• Nu toate funcțiile matematice pot fi definite recursiv; cu alte cuvinte există și funcții nerecursive.

Recursivitatea se realizează în felul următor:

• -          Din afara subprogramului facem un apel al subprogramului

• -          Dacă nu este îndeplinită o condiție (numită condiție de oprire), algoritmul se autoapelează de un anumit număr de ori (până când e îndeplinită condiția). La fiecare nouă autoapelare a subprogramului se reexecută secvența de instrucțiuni din corpul său, eventual cu alte date, creându-se un lanț de autoapeluri recursive. Dacă condiția de oprire nu este îndeplinită niciodată sau nu există, algoritmul va avea un rezultat asemănător intrării într-un ciclu infinit.

• Prin urmare orice subprogram recursiv trebuie să îndeplinească următoarele condiții:

• -          să se poată executa cel puțin o dată fără a se autoapela (când apare condiția de oprire);

• -          toate autoapelurile să se producă astfel încât la un moment dat să se ajungă la îndeplinirea condiției de oprire.

• Cea mai mare parte a algoritmilor repetitivi se pot implementa într-o variantă nerecursivă (numită variantă iterativă) folosind instrucțiuni recursive, cât și într-o variantă recursivă atunci când conțin un modul definit recursiv.

• Recursivitatea s-a impus in programare, odata cu apariția unor limbaje de nivel înalt, ce permit scrierea de module ce se autoapelează (PASCAL, LISP, ADA, ALGOL, C sunt limbaje recursive, spre deosebire de FORTRAN,BASIC,COBOL, nerecursive).

"Ce este mai indicat de utilizat: recursivitatea sau iteraţia?"

• Algoritmii recursivi sunt potriviți pentru a descrie probleme care utilizează formule recursive sau pentru prelucrarea structurilor de date definite recursiv ( liste, arbori ), fiind mai eleganți şi mai simplu de înțeles şi verificat. Iterația este uneori preferată din cauza vitezei mai mari şi a memoriei mai reduse. Spre exemplu varianta recursivă a funcției Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativă este mult mai performantă.

Funcția factorial

• Forma funcției:

Rezolvare:

• Program problema;

• function factorial (n:integer):longint;

• begin

• if n=0 then fact :=1

• else fact :=n* fact (n-1);

• end;

• Begin

• write(‘n=‘); readln(n);

• writeln(factorial(n));

• readln;

• End.

Să se calculeze suma primelor numere impare:

Rezolvare:

• a)Function cmmdc (a,b: integer) :integer ;

• begin

• if b=0 then

• cmmdc:=a

• else

• cmmdc:=cmmdc(b, a mod b);

• end;

• var a,b:integer ;

• begin

• write('a='); readln(a);

• write('b='); readln(b);

• writeln('cmmdc=' ,cmmdc(a,b));

• readln;

• end.

Se dau coeficienţii a,b,c ai ecuaţiei de gradul 2: ax² + bx + c=0. Notăm cu . Să se calculeze

Procedură

• Recursiv

• Program pr;

• s:=1;

• procedure exp(a:real, n:integer)

• begin

• S:=s*a

• if n>=1 then exp(a,n-1);

• end;

• Begin

• write(‘a=’);readln(a);

• write (‘n=’);readln(n);

• writeln(exp(a,n));

• readln;

• end.

Funcţia Manna Pnueli

Funcţia lui Ackermann