Burdea David si Catalin Negulescu 1

RECURSIVITATE

Burdea David si Catalin Negulescu

Burdea David si Catalin Negulescu 2

Definita procesului de recursivitate

Recursivitatea reprezinta o tehnica de programare de o importanta deosebita. Ea permite o exprimare extrem de concisa si clara a algoritmilor de rezolvare a unor probleme complexe.

Un subprogram este recursiv daca se autoapeleaza pe el insusi .

Burdea David si Catalin Negulescu 3

Observatii

1) Orice f recursiva trebuie sa contina o conditie de oprire,respectiv de continuare.

2)la fiecare apel al f. se executa aceasi secventa de instructiuni.

3)tinand seama de observatia anterioara pentru a scrie un program recursiv problema trebuie sa contina o functie care sa contina relatia de recurenta

4)la fiecare apel in zona de stiva a memoriei se creeaza un nivel sau pe stiva se memoreaza val parametrilor formali transmisi prin valoare, adresa param. formali transmisi prin referinta, adresa de revenire, variabilele locale cu val din mom respectiv.

5)toate instructiunile din subprogram se executa pentru fiecare reapel.

Burdea David si Catalin Negulescu 4

Limbajul C/C++

for(i=1;i<=n;i++) {secventa de operatii} while(cond_logica) {secventa de operatii}

Burdea David si Catalin Negulescu 5

unsigned fib(unsigned n) {if (n <= 1) return 1;else return fib(n-1)+fib(n-

2);}Unsigned

fib_smart(unsigned n) {unsigned f2 = 1, f1 = 1, f;if (n <= 1) return 1;while (--n) { f = f1 + f2;f2 = f1; f1 = f;}return f;}

unsigned fib_nonrec(unsigned n)

{int i, *f, res;if (n <= 1) return 1;f = malloc(n * sizeof(int));f[1] = f[0] = 1;for (i = 2; i < n; i++)f[i] = f[i-1] + f[i-2];res = f[n-1] + f[n-2];free(f);return res;}

Atentie ! Traducerea directa a formulei rezulta ın apeluri redundante !(se apeleaza din nou fib(n-2) si ın fib(n-1), etc.)⇒nr. de apeluri (cate pt. fib(5)?) e exponential ın n (f. ineficient)