Recursivitate

Putem considera notiunea de algoritm ca o exprimare specializata a unor definitii matematice, care ne ajuta la construirea programelor in diverse limbaje de programare. In matematica, multe defintii utilizeaza, pentru construirea unor concepte, o metoda speciala numita recursivitate.

Definitie

Se spune despre un concept ca este recursiv daca el este definit prin el insusi. In acest fel pot fi definite numerele naturale, siruri de numere sau unele functii:

Exemple

numarul 1 este numar natural; succesorul unui numar natural este tot un numar natural (se presupune ca este definita notiunea de succesor);

sirul numerelor triunghiulare (termenul de rang n se obtine adunand pe n la termenul anterior)

tri₁ = 1;

tri_n = n + tri_n-1, pentru n > 1

functia lui Ackermann:

ack(m,n) = ack(m-1, ack(m, n-1));

ack(0,n) = n+1;

ack(m,0) = ack(m-1,1);

Aceasta functie are o adancime mare din punctul de vedere al recursivitatii. Este utila in compararea eficientei compilatoarelor limbajelor de programare. De asemenea valoarea ei creste foarte rapid.

Caracteristicile functiilor recursive

double factrec(unsigned n)

Calculul timpului de executie

Performanta programelor depinde de doi factori esentiali: spatiul de memorie ocupat de program si timpul de executie. O varianta simpla de calcul a timpului de executie este prezentata in cele ce urmeaza.

#include <time.h>

#include <stdio.h>

int main()

Generarea de submultimi

Pentru multimea: se pot genera urmatoarele multimi:

Permutari :

Aranjamente de 2 elemente cu repetitie :

Combinari de 2 elemente cu repetitie :

Pentru determinarea acestor multimi se pot folosi cu succes functii recursive.

/* Generarea aranjamentelor de n elemente luate

cate m, cu repetitie. */

#include <stdio.h>

int n, m;

char caractere[20];

int indici[20];

/* Functia de tiparire a solutiei in care se face

asocierea dintre pozitia generata si caracter. */

void tipareste()

void aranj_r(int k)

else

}

int main()

while ((m<=0) || (m>n));

/* Apelul functiei recursive. Pornim de la ultima

pozitie (indice m-1). Apelurile recursive ne

vor duce spre indicii mai mici. */

aranj_r(m-1);

Functii cu numar variabil de argumente

In mod normal, cand scriem o functie C trebuie sa specificam exact numarul si tipul parametrilor pe care ii poate primi functia.

Sa ne reamintim exemplul de la lucrarea cu transmiterea parametrilor din linie de comanda, si anume programul care afisa pe ecran literele TP construite din stelute si spatii:

*****

* * *

* * *

* * *

* * *

* *****

* *

* *

* *

* *

* *

Daca vrem sa scriem un program C care sa afiseze literele TP in mod similar cu fisierul BAT de la laboratorul respectiv, o varianta este sa scriem o functie linie() care primeste ca si parametru o secventa de numere si afiseaza pe ecran, pe o singura linie, o alternanta de stelute si spatii, in functie de numerele specificate. Daca analizam literele TP pe care vrem sa le tiparim, vedem ca avem trei situatii posibile: cand trimitem 3 numere ca si parametri, cand trimitem 7 numere ca si parametri sau cand trimitem 5 numere ca si parametri.

O modalitate de implementare este sa scriem trei functii linie, cu 3, cu 5 si respectiv cu 7 parametri. Programul ar arata in felul urmator.

#include <stdio.h>

void stelute(int n)

void spatii(int n)

void linie3(int n1, int n2, int n3)

void linie5(int n1, int n2, int n3, int n4, int n5)

void linie7(int n1, int n2, int n3, int n4, int n5, int n6, int n7)

int main(int argc, char* argv[])

In urma rularii lui, pe ecran apare:

*****

* * *

* * *

* * *

* * *

* *****

* *

* *

* *

* *

* *

* *

Daca urmarim sursa programului, vom realiza ca ea nu este foarte bine structurata. Ce se intampla daca vrem sa transmitem 4 parametri la functia linie? Sau 6, sau 8? Ar trebui sa scriem noi variante ale functiei care sa accepte numarul dorit de parametri.

Limbajul C ne permite sa declaram functii cu numar variabil de parametri.

O functie cu numar variabil de parametri se declara asemanator cu orice functie, cu diferenta ca pe post de ultimul parametru al functiei apar caracterele ''  (trei puncte).

Vom da explicatii despre modul de folosire a functiilor cu numar variabil de parametri direct pe un cod care functioneaza:

#include <stdio.h>

#include <stdarg.h>

void stelute(int n)

void spatii(int n)

/* Functia are numar variabil de parametri.

Putem avea si parametri ficsi, important este

ca dupa ultimul parametru fix sa apara caracterele

''. In acest caz concret avem un singur parametru

fix, care va spune de fiecare data cati

parametri variabili urmeaza. Parametri variabili vor

fi numerele in functie de care se afiseaza

stelute sau spatii. */

void linie(int nr_param, )

/* Dupa ce am parcurs toti parametri variabili, apelam macro-ul

'va_end'. Acesta face operatii necesare pentru curatarea

memoriei. */

va_end(ap);

printf('n');

int main()

Efectul rularii acestui program este acelasi ca si la programul precedent. Observam ca programul in aceasta forma este mult mai flexibil. Acum putem apela functia linie in orice mod dorim, cu oricati parametri, fara sa fie nevoie sa mai scriem noi variante ale ei.

In schimb trebuie sa fim mult mai atenti la apelurile functiei, sa trimitem corect numarul de parametri. Compilatorul nu mai poate detecta situatii in care spre exemplu primul parametru are valoare 5, dar dupa el urmeaza doar 4 parametri variabili. Asemenea erori vor iesi la iveala doar la executia programului.

Probleme propuse

Implementati functia lui Ackermann recursiv.

Implementati functia factorial in varianta recursiva si iterativa. Comparati timpii de executie pentru 10000 de repetari ale calculului functiei factorial in varianta iterativa si cea recursiva.

Generati combinarile cu repetitie pentru o multime de caractere citite dintr-un fisier text. Multimea solutiilor se va scrie intr-un fisier text. Datele de intrare vor fi validate pentru a se asigura unicitatea caracterelor. In cazul in care datele de intrare sunt eronate se va genera o solutie pentru caracterele unice.

Scrieti o functie cu numar variabil de argumente care primeste ca prim parametru un numar N, iar ca urmatorii N parametri primeste N numere reale. Functia va returna suma celor N numere reale. Verificati functia prin cateva apeluri ale ei cu diverse seturi de parametri.