curs16-pc

Programarea calculatoarelor

Universitatea Constatin Brncui Trgu-Jiu Facultatea de Inginerie

Departamentul de Automatic, Energie i Mediu

Lect.dr. Adrian Runceanu

Curs 16

Recursivitate

18.12.2011 Programarea calculatoarelor 2

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relaia dintre recursivitate i iteraie

5. Exemple de programe recursive



Un obiect sau un fenomen este definit n mod recursiv dac n definitia sa se face referire la el nsusi.

Conceptul de recursivitate ofer posibilitatea definirii unei infinitti de obiecte printr-un numr finit de relatii.

O functie este recursiv atunci cnd executarea ei implic cel putin nc un apel ctre ea nssi.



Tipuri de recursivitate:

Recursivitate direct apelul recursiv se face chiar din functia invocat.

Recursivitate indirect (mutual) apelul recursiv se realizeaz prin intermediul mai multor functii care se apeleaz circular.


Exemplul 1

Definirea numerelor naturale:

1 este numr natural

succesorul unui numr natural este un numr natural

Se presupune cunoscut definiia succesorului unui numr: acel numr obinut din numrul dat prin adugarea unei uniti.


Exemplul 2

Algoritm de calcul pentru factorialul unui numr N. (notatie N!):

dac N = 0 atunci N! = 1

dac N > 0 atunci N! = N * (N-1)!

Astfel spus, factorialul unui numr N > 0 se obine prin nmulirea numrului cu factorialul predecesorului.


Coninutul cursului




4. Relatia dintre recursivitate si iteratie



Recursivitate direct

n limbajul C++ functiile se pot apela pe ele nsele, adic sunt direct recursive.

Pentru o functionare corect (din punct de vedere logic), apelul recursiv trebuie s fie conditionat de o decizie care, la un moment dat n cursul executiei, s mpiedice continuarea apelurilor recursive si s permit astfel revenirea din sirul de apeluri.


Recursivitate direct

Lipsa acestei conditii sau programarea ei gresit va conduce la executarea unui sir de apeluri a crui terminare nu mai este controlat prin program si care, la epuizarea resurselor sistemului, va provoca o eroare de executie:

Depsirea stivei de date.


Exemplu

void p (list de parametri){

lista variabile locale

...

p(list de parametri);

}

Conditia care trebuie testat este specific problemei de rezolvat.

Programatorul trebuie s o identifice n fiecare situatie concret si, pe baza ei, s redacteze corect apelul recursiv.

Revenirea din apeluri se face n ordine invers.


if (cond) p(list de parametri) ... sau:

while (cond) { ...p(list de parametri) } sau:

do ... p(list de parametri)... while (cond)

Coninutul cursului







Recursivitate indirect

Un subprogram S, n corpul cruia apar apeluri la S (la el nsui) se numete subprogram direct recursiv iar un subprogram P, pentru care exist un subprogram Q, astfel nct P face apeluri la Q, iar Q conine apelul la P se numete subprogram indirect recursiv.

n acest ultim caz, subprogramele P i Q se mai numesc i mutual recursive.


Recursivitate indirect

Procedur direct recursiv

functia S;

{

S; // apel la functia S

}


Proceduri mutual recursive functia P; { Q ; // apel la functia Q } functia Q; { P ; // apelul functiei P }

Coninutul cursului







Relaia dintre recursivitate i iteraie - Comparaie

Iteraia

executia repetat a unei secvente de instructiuni

o nou iteratie se execut doar n urma evalurii unei conditii (la nceput sau sfrsit)

fiecare iteratie se execut pn la capt si apoi se trece, eventual, la o nou iteratie

se recomand atunci cnd algoritmul de calcul este exprimat printr-o formul iterativ


Recursivitatea

executia repetat a unei functii

un nou apel recursiv se execut tot n urma evalurii unei conditii (pe parcurs)

functia recursiv se apeleaz din nou, nainte de terminarea apelului precedent

se recomand doar atunci cnd problema este prin definitie recursiv (recursivitatea consum resurse n exces)

Coninutul cursului







Probleme rezolvate

1. Se dau doua numere intregi a si b si se cere sa se calculeze cel mai mare divizor comun. (Algoritmul lui EUCLID prin mpriri repetate).

Formularea recursiv, n cuvinte, a algoritmului:

Dac unul dintre numere este zero, c.m.m.d.c. al lor este cellalt numr.

Dac nici unul dintre numere nu este zero, atunci c.m.m.d.c. nu se modific dac se nlocuieste unul dintre numere cu restul mprtirii sale cu cellalt.


Algoritmul poate fi implementat sub forma urmtoarei functii recursive:

int cmmdc (int n, int m)

{

if (n==0) return m;

else return cmmdc(n, m % n);

}


Codul sursa al implementarii (varianta prin scaderi succesive) este urmatorul:

#include

int cmmdc(int a,int b)

{

if(a==b) return a;

else if(a>b) return cmmdc(a-b, b);

else return cmmdc(a, b-a);

}


int main(void) { int a, b; char c; do { couta; coutb; cout

Executia programului pentru cateva date de test:

Programarea calculatoarelor 18.12.2011 22

2. S se calculeze suma primelor n numere naturale.


#include long int suma(long int i) { if(i==1) return 1; else return suma(i-1)+i; } int main(void) { long int n; coutn; cout

Executia programului pentru o valoare de test:


3. S se afle elementul maxim dintr-un vector dat.

Soluia este dat de relaia de recuren :

maxim(a1, a2 , . . . ,an) =

maxim(an, maxim(a1, a2, . . . , an-1))


#include int a[100],n,i; int max(int x, int y) { if(x > y) return x; else return y; } int maxim(int a[ ],int n) { if(n==1) return a[1]; else return max(a[n],maxim(a,n-1)); } int main(void) { coutn; for(i=1;i

Executia programului pentru cateva valori de test:


4. Sa se transforme un numar n, dat in baza 10, intr-o alta baza b (2

#include int n,b; void baza(int n) { if(n

Executia programului pentru cateva valori de test:


5. Se citeste un numar intreg ca un sir de caractere cu cel mult 255 cifre.

Sa se afiseze numarul cu cifrele in ordine inversa.


#include #include char n[255],i,l; void invers(int i) { if(i

Executia programului pentru o valoare de test:


6. Suma puterilor rdcinilor

Fie ecuaia x2 - Sx + P = 0 cu S, P R si x1, x2 rdcinile ecuaiei.

S se calculeze Sn= x1n + x2

n , n N.


Cutm relaia de recuren pentru Sn, tiind c x1, respectiv x2 sunt rdcinile ecuaiei date i deci ndeplinesc relaiile:

x12 - Sx1 + P = 0 | * x1

n-2

x22 - Sx2 + P = 0 | * x2

n-2

nmulim aceste relaii cu x1n-2 i x2

n-2 i adunm relaiile obinute i rezult:

Sn = x1n + x2

n =

= S * (x1n-1 + x2

n-1 ) P * (x1n-2 + x2

n-2 ) =

= S * Sn-1 - P * Sn-2.


Astfel am obinut o relaie de recuren:

S0 = x11 + x2

1 = 1 + 1 = 2, pentru n=0

S1 = x11 + x2

1 = S, pentru n=1

Sn = S * Sn-1 - P * Sn-2, pentru n 2.


#include int n; float s,p,r; float suma(int n) { if(n==0) return 2; else if(n==1) return s; else return(s*suma(n-1)-p*suma(n-2)); } int main(void) { cout

Executia programului pentru un set de valori de test:


Probleme propuse spre rezolvare

1. S se scrie un program care s calculeze al n-lea termen din irul lui Fibonacci, care este definit recursiv astfel:

fib[1]=0

fib[2]=1

fib[n]=fib[n-1] + fib[n-2], pentru n>2

2. S se caute o soluie nerecursiv pentru irul lui Fibonacci.


ntrebri?


curs16-pc

Documents