subprograme - recursie

1.

DISCIPLINA: Informatică, anul III
PROFESOR: Bînzari Oxana
MODULUL 1: SUBPROGRAME.
Lecția 4: Recursia
Tipul lecţiei: mixtă.
Locul de desfăşurare: LABORATORUL DE INFORMATICA

2.

La finele lecției
veți cunoaște termenii - cheie:
Tehnici de programare;
Recursie directă;
Recursie indirectă;
Regula de consistență;
Definție consistentă;
Definție inconsistentă;

3.

Sarcină de recapitulare

4.

Multe probleme de o reală importanță practică pot fi rezolate cu
ajutorul unor metode standard, denumite tehnici de programare.
TEHNICI DE PROGRAMARE
Recursia
Trierea
Metoda reluări
Metoda euristică
Metoda Greedy
Metoda desparte și
stăpînește

5.

RECURSIA
Una din cele mai răspîndite tehnici de
TEHNICI
programare este recursia;
Se definește ca o situație în care un
subprogram se autoapelează fie direct
Recursia
directă
fie prin intermediul altui subprogram.
Recursia directă - atunci cînd subprogramul se auto-apelează
din propriul bloc de instrucțiuni.
Recursia indirectă - atunci cînd auto-apelarea se face prin
intermediul unui alt subprogram.
Recursia
indirectă

6.

Regula de consistență
Soluția
problemei
Calculabilă cu
ajutorul unor
valori direct
calculabile.
Direct calculabilă
În procesul derulării
programelor într-un
algoritm recursiv
trebuie să existe:
cazuri elementare care se rezolvă
direct.
cazuri care nu se rezolvă direct,
însă procesul de calcul în mod
obligatoriu progresează spre un
caz elementar.

7.

RECURSIA
Recursia este un mecanism general de elaborare a programelor.
Recrsivitatea s-a utilzat inițial pentru transcrierea formulelor matematice
descrise recursiv, ulterior extinzîndu-se pentru elaborarea multor
algoritmi.
DEFINIȚIE
Recursia este o situaţie în care un subprogram se autoapelează fie direct, fie
prin intermediul altei funcţii sau proceduri. Subprogramul care se
autoapelează se numeşte recursiv.
În programare, instrumentul necesar și suficient pentru a exprima programe
recursive este subprogramul deoarece doar el dă un nume unei acțuni care
poate fi reapelată prin numele respectiv.

8.

REȚINE: în cazul subprogamelor recursive, fiecare apel va
avea propriile copii ale variabilelor locale, inclusiv proprii
parametri formali.
Autoapelul provoacă o nouă activare a aceluiași subprogram,
ceea ce presupune execuția instrucțiunilor subprogramului,
începând cu prima instrucțiune a acestuia și pînă la auto apel, cînd
se activează din nou subprogramul și așa la infinit. Pentru a evita
o asemenea situație trebuie ca autoapelul programului să fie
condiționat de îndeplinirea unei anumite condiții.

9.

IMPORTANT
În elaborarea algoritmilor recursiv se aplică raționamentul: ce se
întîmplă la un nivel, se întîmplă la orice nivel;
Pentru orice algoritm recursiv există unul iterativ care rezolvă
aceași problemă;
Nu întotdeauna alegerea unu algoritm recursiv reprezintă un
avantaj;

10.

Exemplul 1: cea mai simplă
funcție recursivă este factorialul:
În definiția recursivă a funcției factorial fact:N N,
deosebim:
Cazul elementar n=0. În acest caz fact(0) este direct calculabilă
și anume fact(0)=1
Cazul neelementar n>0. În astfel de cazuri valorile fact(n) nu
sunt direct calculabile, însă procesul de calcul progresează către
calculul elementar fact(0).
De exemplu, pentru n=3 obținem:
fact(3) = 3*fact(2) = 3*2*fact(1) = 3*2*1*fact(0) = 3*2*1*1 =6.
Prin urmare, definiția recursivă a funcției fact(n) este o definiție
consistentă.

11.

Funcția fact(n) poate fi exprimată în PASCAL, urmînd direct
definiția:
Varianta iterativă a funcției fact(n)

12.

Exemplul 2:
șirul Fibonacci:
Șirul Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... în care primii doi termeni
sunt 0 și 1, iar în rest fiecare termen se obține însumînd cei doi termeni
care îl preced.
Definiția recursivă a
numerelor Fibonacci:
Urmînd definiția,
obținem:

13.

IMPORTANT !!!
La orice apel de subprogram, în memoria calculatorului vor fi
depuse următoarele informaţii:
valorile curente ale parametrilor transmişi prin valoare;
locaţiile (adresele) parametrilor-variabilă;
adresa de retur, adică adresa instrucţiunii ce urmează după apel.
Prin urmare, la apeluri recursive spaţiul ocupat din memorie va creşte
rapid, riscînd depăşirea capacităţii de memorare a calculatorului. Astfel de
cazuri pot fi evitate, înlocuind recursia prin iteraţie (instrucţiunile for,
while, repeat).

14.

Studiul comparativ al iterativității și recursivității:

15.

Rezolvarea exercițiilor:
1) Elaborați un program recursiv care va afișa valoarea numărul n din șirul lui
Fibonacci utilizînd un subprogram funcție.

16.

Rezolvarea exercițiilor:
3) Elaborați un program recursiv care va calcula n! utilizînd un subprogram
funcție.

17.

TEMA PENTRU ACASA
2)
Scrieţi un subprogram recursiv care calculează suma:
P(n) = 2 + 4 + 6 + ... + 2n

18.

TEMA PENTRU ACASA
Exercițiul 1, 2, 4(a,b,d) pagina 25