R E C U R S I A

RECURSIA DIRECTĂ1

CONTINUAŢI ENUNŢURILE: Un subprogram este……. Subprogramele sunt de 2 tipuri ……….. Funcţia este ……. Procedura este …. Apelul unei subprogram se face prin

intermediul ... Tipul rezultatului unei funcţii poate fi ... Funcţia returnează rezultatul prin…. Procedura returnează rezultatul prin… Parametri actuali sunt ….. Corespondenţa între un parametru actual şi un

parametru formal se face…. 2

Lista parametrilor formaliNume Variabile localeRezultatul se întoarce prin numeRezultatul se intoarce prin parametru variabilă Returnează un singur rezultat

Returnează 0,1sau mai multe rezultate

FUNCŢII comune PROCEDURE

CARACTERISTICILE

Extinde noţiunede expresieEstinde noţiuneade instrucţiune

Se defineşte în parteadeclarativă a programului

Poate fi apelat de el însuşi

4

Tema: “RECURSIA”Subcompetenţe:Prelucrarea datelor cu ajutorul subprogramelor predefinite şi a subprogramelor elaborate de către utilizator.Organizarea comunicării între programul / subprogramul apelant şi subprogramul apelatProiectarea structurală a algoritmului şi a programului. Utilizarea recursiei pentru rezolvarea problemelor 

Obiective operaţionale:

O1 – să definească termenii: program, subprogram, funcţie 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 funcţiei pentru anumite date de intrare;O4 – să explice algoritmul subprogramului recursiv, modul de execuţie al subprogramului recursiv;O5 – să elaboreze programe în care se utilizează subprograme recursive

DEFINIŢII ŞI IDEI ANCORĂ Un subprogram se numeşte recursiv dacă el se

autoapelează pe el însuşi.

În matematică relaţiile recursive se numesc relaţii de

recurenţă. (Unele şiruri pot fi definite cu ajutorul unor

formule în funcţie de termenul sau termenii precedenţi).

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 următor terme va fi egal cu suma a doi termeni

precedenţi)

5

Scrieţi o funcţie 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

6

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

7

5!= 5*4!

4!=4*3!

3!=3*2!

2!=2*1!

1!=1*0!

0!=1

1!=1*1=1

2!=2*1=2

3!=3*2=6

4!=4*6=24

5!=5*24=120

Calculul lui N! recursiv

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

0!=1

8

Scrieţi un program care utilizează funcţia 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.

Analizaţi execuţia programului , dacă condiţia va fi N<0Pentru lecţia practică : Executaţi pentru N=0, 5, 7, 8,10

9

Se consideră funcţia 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;

a)-28b)28c)-4d)4e)0

10

Să se scrie un program ce calculează suma primilor n termeni din şirul numerelor naturale utilizînd o funcţie recursivă / iterativă

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

11

Concluzii:

Un algoritm recursiv are acelaşi efect ca şi un ciclu: repetă execuţia unei anumite secvenţe de instrucţiuni

E necesar ca repetarea să nu fie la infinit, adică trebuie să existe o condiţie de oprire, cazul elementar ce poate fi calcul direct

În majoritatea cazurilor algoritmii recursivi pot fi înlocuiţi cu algoritmi nerecursivi (iterativi), la dorinţa programatorului.

Varianta recursivă este recomandată în special pentru problemele definite prin relaţii de recurenţă, care permite o formulare a rezultatelor mult mai clară şi mai concisă:

Avantajele recursiei:

1.Structura programului – simplă

2.Volumul de scriere a programului - mic

Dezavantajele recursiei:

1.Necesarul de memorie – mare

2.Testarea şi depănarea programelor - complicat