proiectul recursia
DESCRIPTION
PrezentareTRANSCRIPT
-
Harea NataliaCiumas Alina
-
Ce este recursia?
-
Un obiect sau un fenomen se defineste in mod recursiv daca in definitia sa exista o referire la el insusi.
-
Prin urmare un algortim sau un program se numete recursiv dac conine cel puin un subprogram care se autoapeleaz.
-
n matematic i informatic, recursivitatea -un mod de a defini unele funcii. Funcia este recursiv, dac definiia ei folosete o referire la ea nsi, crend la prima vedere un cerc vicios, care ns este numai aparent, nu i real. Nota! Nu toate funciile matematice pot fi definite recursiv; cu alte cuvinte exist i funcii nerecursive.
-
Exemplu de definitii matematice recursive:
Definitia functiei Ackermann
Definitia functiei Fibonacci Definitia functiei factorial
-
O form de recursie vizual cunoscut sub numele de efectul Droste.
-
Utilitatea practica a recursivitatii rezulta din posibilitatea de a defini un set infinit de obiecte printr-o singura relatie sau printr-un set finit de relatii.
-
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 inceput, fara ca executia curenta sa se fi terminat.In momentul satisfacerii conditiei se revine in ordine inversa din lantul de apeluri, reluandu-se si incheindu-se apelurile suspendate.
-
Elaborarea unui program recursiv este posibila numai cind se respecta regula de consistenta.
-
Regula de consistentaSolutia trebuie sa fie direct calculabila ori calculabila cu ajutorul unor valori direct calculabileExemplu:
-
Regula de inconsistenta
Procesul de calcul dureaza la nesfirsitExemplu:
Incons(3)=3*icons(4)=3*4*icons(5)=.
Nota!!!! Gasiti greseala comisa !
-
Ce este iteraia?
-
Iteratia este executia repetata a unei portiuni de program, pina la indeplinirea unei conditii (while, do-while , for din C).
-
Ce este mai indicat de utilizat: recursivitatea sau iteratia?
-
Algoritmii recursivi sunt potriviti pentru a descrie probleme care utilizeaza formule recursive sau pentru prelucrarea structurilor de date definite recursiv ( liste, arbori ), fiind mai eleganti si mai simplu de inteles si verificat.
-
Iteratia este uneori preferata din cauza vitezei mai mari si a memoriei mai reduse. Spre exemplu varianta recursiva a functiei Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativa este mult mai performanta.
-
Studiul comparativ al iteratiei i recursivitaii
Interativitatea Caracteristici Recursivitatea MicNecesarul de memorieMare Acelasi Tipul executieiAcelasi Complicata Structura programuluiSimpla Mare Volumul de munca necesar pentru scrierea programuluiMic Simpla Testarea si depanarea programelorComplicata
-
Exemple de probleme:Program iter2;Var a,n:integer;Function p:integer;Var produs,i:integer;beginprodus:=1;For i:=1 to n doProdus:=p*aP:=produs;End;
Program rec1;Var a,n:integer;Function p (a,n:integer):integer;beginIf n=1 then p:=a elseP:=a*p(a,n-1);end;
-
Sa se calculeze recursiv n!
-
program factorial; var n:integer; function factorial (n : integer) : integer; begin if n=0 then factorial:=1 else factorial:=n * factorial(n-1); end; begin write (n= ); readln (n); writeln (factorial(n)); readln; end.
-
Tema pentru acasaRezolva problema urmatoare folosind:Metoda iterativaMetoda recursivaMedia aritmetica a n numere.
-
SfrsitMultumesc pentru atentie
************