R E C U R S I ARECURSIA DIRECT

*

CONTINUAI ENUNURILE:

Un subprogram este.Subprogramele sunt de 2 tipuri .. Funcia este .Procedura este .Apelul unei subprogram se face prin intermediul ...Tipul rezultatului unei funcii poate fi ...Funcia returneaz rezultatul prin.Procedura returneaz rezultatul prinParametri actuali sunt ..Corespondena ntre un parametru actual i un parametru formal se face.

*

Lista parametrilor formaliNume Variabile localeRezultatul se ntoarce prin numeRezultatul se intoarce prin parametru variabil Returneaz un singur rezultatReturneaz 0,1sau mai multe rezultateFUNCIIcomunePROCEDURECARACTERISTICILEExtinde noiunede expresieEstinde noiuneade instruciuneSe definete n parteadeclarativ a programuluiPoate fi apelat de el nsui

*Tema: RECURSIASubcompetene:Prelucrarea datelor cu ajutorul subprogramelor predefinite i a subprogramelor elaborate de ctre utilizator.Organizarea comunicrii ntre programul / subprogramul apelant i subprogramul apelatProiectarea structural a algoritmului i a programului. Utilizarea recursiei pentru rezolvarea problemelorObiective operaionale:

O1 s defineasc termenii: program, subprogram, funcie procedur, apel, parametri valoare, parametri variabil, parametri formali, parametri actuali, variabile globale, variabile locale, O2 s determine corectitudinea antetelor i apelurilor de subprograme; O3 s poat evalua programe ce utilizeaz subprograme recursive, s determine valoarea funciei pentru anumite date de intrare;O4 s explice algoritmul subprogramului recursiv, modul de execuie al subprogramului recursiv;O5 s elaboreze programe n care se utilizeaz subprograme recursive

DEFINIII I IDEI ANCORUn subprogram se numete recursiv dac el se autoapeleaz pe el nsui.n matematic relaiile recursive se numesc relaii de recuren. (Unele iruri pot fi definite cu ajutorul unor formule n funcie de termenul sau termenii precedeni). Spre exemplu irul numerelor naturale: 1,2,3 irul numerelor pare: 2,4,6,8,10... irul Fibonacci 1,1,3,5,8,13,21...(primii doi termeni sunt egali cu 1, iar fiecare urmtor terme va fi egal cu suma a doi termeni precedeni)

*

Scriei o funcie nerecursiv care calculeaz valoarea lui N!

Function fact(N:integer):integer;Var P, i: integer;BeginP:=1; For i:=1 to N do P:=P*iFact:=P;End;

Pentru N=5* P=1 i=1 P:=P*i P=1*1=1i=2 P:=P*i P=1*2=2i=3 P:=P*i P=2*3=6i=4 P:=P*i P=6*4=24 i=5 P:=P*i P=24*5=120

*5!= 5*4!4!=4*3!3!=3*2!2!=2*1!1!=1*0! 0!=11!=1*1=12!=2*1=23!=3*2=64!=4*6=245!=5*24=120Calculul lui N! recursiv

Function fact(N:integer):integer;BeginIf N=0 then fact:=1 else fact:=N* fact(N-1);End; 0!=1

*Scriei un program care utilizeaz funcia recursiv de calcul a lui N!Program p1;Var x,f: integer;

Function fact(N:integer):integer;BeginIf N=0 then fact:=1 else fact:=N* fact(N-1);End;

BeginWrite(da valoarea lui x); readln (x);f:= fact (x);Writeln (f);End.

Analizai execuia programului , dac condiia va fi N

*Se consider funcia F de mai jos definit recursiv. Ce va returna apelul F(7)?

Function F (n:integer):integer;BeginIf n=0 then F:=0 else if (n mod 2=0) then F:=F(n-1)+n else F:=F(n-1) - n End;

-2828-440

*S se scrie un program ce calculeaz suma primilor n termeni din irul numerelor naturale utiliznd o funcie recursiv / iterativProgram suma_recursiv;Var n: integer;Function S(k: integer):integer;BeginIf k=0 then S:=0 else S:=k+S(k-1);End;BeginWrite( n=); readln(n);Writeln(suma este , S(n));End.Program suma_iterativ;Var n: integer;Function S(k: integer):integer;Var i:integer;BeginS:=0; For i:= 1 to k do S:=S+iEnd;BeginWrite( n=); readln(n);Writeln(suma este , S(n));End.

*

Concluzii:Un algoritm recursiv are acelai efect ca i un ciclu: repet execuia unei anumite secvene de instruciuniE necesar ca repetarea s nu fie la infinit, adic trebuie s existe o condiie de oprire, cazul elementar ce poate fi calcul directn majoritatea cazurilor algoritmii recursivi pot fi nlocuii cu algoritmi nerecursivi (iterativi), la dorina programatorului.Varianta recursiv este recomandat n special pentru problemele definite prin relaii de recuren, care permite o formulare a rezultatelor mult mai clar i mai concis:Avantajele recursiei:Structura programului simplVolumul de scriere a programului - mic Dezavantajele recursiei:Necesarul de memorie mare Testarea i depnarea programelor - complicat