FUNCTII RECURSIVE

FUNCTII RECURSIVE

Limbajul C permite recursivitatea , adica admite ca o functie sa se autoapeleze fie direct , fie indirect prin intermediul altei functi 151e48b i . A

La fiecare apel recursiv se aloca pe stiva intr-o zona distincta fata de apelul precedent sau urmator , urmatoarele informatii :

n       valorile parametrilor ;

n       variabilele locale functiei;

n       adresa de revenire .

Acestea , evident, implica un consum mai mare , atit de memorie , cat si de timp .

Deci , atunci cand ne intereseaza un consum redus de memorie si o executie mai rapida, recomandam utilizarea de variante nerecursive pentru functiile in cauza . Totusi , sunt situatii cand varianta de functie recursiva este mai compacta si mai usor de urmarit .

De asemenea , lucrul cu functii recursive cere o anumita experienta in programare , in sensul estimarii memoriei necesare si a conditiilor de oprire pentru procesul recursiv . Un exemplu in acest sens este functia urmatoare :

int func - rec ( int a )

functie care nu face nimic altceva decat ca se autoapeleaza .

Este o situatie tipica de eroare ce poate sa apara la un apel recursiv, anume atunci

cand nu se prevad si conditiile de oprire . Astfel, la executia functiei de mai sus , se produce o buclare infinita . Daca aceasta buclare nu ar impune consum de memorie , procesul nu s-ar termina niciodata, dar totusi la fiecare autoapel este nevoie sa se aloce pe stiva adresa de revenire si valoarea parametrului , si de aceea , procesul respectiv se va termina cu eroarea de depasire de stiva .

In continuare , sunt prezentate cateva exemple de functii recursive , unele de acum clasice . In cateva vom da si varianta nerecursiva ,

iar la celelalte invitam cititorul sa elaboreze forma nerecursiva si sa compare cele doua modalitati .

Exemplu 4.5.1.

Calculul factorialului n! = n * ( n - 1 )! :

long unsigned fact ( unsigned n)

if ( n<= 1) /* Conditia de * /

return 1 ; /* oprire * /

return n * fact (n - 1 ) ;

}

Exemplu 4.5.2.

Calculul celui de-al n-lea termen al sirului lui Fibonacci :f_n = f_n-1 + f_n-2 ; n=3,4,........si f₁ = f₂ = 1 .

Varianta de functie recursiva :

unsigned long fib -rec (unsigned n )

Varianta nerecursiva :

unsigned long fib - norm (unsigned n)

return f₃ ;

}

Observati ca, in cazul functiei recursive , este nevoie de toti termenii f_1, f₂, ...............,f_n-₁ , de dinaintea lui f_n , pe cand in cazul functiei nerecursive este nevoie doar de trei termeni f_k , f_k-1 , f_k-2 care basculeaza intre ei . Deci, varianta nerecursiva consuma mult mai putina memorie si este si mai rapida, si de a pregati n - 1 apeluri pentru fib-rec.I

Exemplul 4.5.3.

In capitolul precedent am prezentat un program care calculeaza in varianta nerecursiva. Folosind formulele de calcul , in care se observa cum se exprima, functie de

, se poate scrie si varianta recursiva ;   

unsigned long comb ( unsigned n, unsigned k )

Exemplu 4.5.4.

Iata acum un exemplu de functie recursiva ceva mai complicat, care converteste si afiseaza in zecimal un numar intreg. Se stie ca acest lucru se realizeaza prin impartiri succesive cu 10 cu retinerea restului, numai ca cifrele zecimale astfel obtinute sunt de la dreapta spre stinga si ele trebuie afisate invers, de la stinga spre dreapta. Deci, cifrele ar trebui sa fie mai intii memorate intr-un sir si apoi sa fie scrise invers, de la sfirsit spre inceput.

Acest dezavantaj se poate elimina utilizind urmatoarea functie recursiva :

void afis - zec ( long n )

if ( ( m = n/10 ) ! = 0 )

afis-zec (m) ;

putchar ( n%10 + ` 0 `) ;

}

La fiecare autoapel a lui afis-zec se trateaza mai intii cifrele din fata, adica m = n/10, si apoi se afiseaza ultima cifra.

Functia putchar este functia standard care scrie un caracter la dispozitivul standard de intrare / iesire. Prototipul acestei functii se gaseste in " stdio-h ".

Exemplu 4.5.5.

Fie ecuatia de gradul doi : ax² + bx + c = 0 cu radacinile x₁ si x₂ . Pentru a calcula sume de forma :

s_k = se foloseste relatia as_k + bs_{k - 1} +cs_k-2=0.

sau s _k = -b/a * s _{k - 1} - c / a * s _{k - 2} cu k > = 2 si s ₀ = 2 , s ₁ = -b / a.

Aceste relatii pot face obiectul unei functii recursive : double sum ( double a, double b, double c, unsigned k )

Exercitii propuse

Sa se scrie o functie care determina prima aparitie a sirului de caractere a in sirul b. Functia va returna pozitia in sirul b la succes si -1 la insucces.

Scrieti o functie care sa returneze produsul scalar a doi vectori.

Scrieti o functie care sa determine numarul de numere prime din intervalul [ a, b ] .

Fie un sir de caractere si c un caracter oarecare. Scrieti o functie care sa returneze numarul de aparitii ale caracterului c in sirul a.

Scrieti o functie care sa calculeze numarul de zile dintre doua date calendaristice de forma zz.11.aaaa.

Scrieti o functie care sa calculeze puterea la care apare numarul prim p in dezvoltarea in factori primi a numarului natural n.

Sirul de caractere a contine un text intr-o limba oarecare. Scrieti o functie care sa calculeze numarul de cuvinte din sirul dat. Un cuvint poate contine : majuscule, minuscule, cifre, liniuta de unire si liniuta de subliniere.

Fie sirul de numere x ₁ , x ₂ , ... , x _n . Scrieti o functie care sa calculeze media aritmetica a elementelor sirului.

Scrieti o functie care calculeaza folosind formula recurenta :

= +.

Scrieti o functie care sa analizeze sirul de numere x ₁ , x ₂ , . . . , x _n si sa returneze :

- 1 daca sirul este o progresie aritmetica ;

+ 1 daca sirul este o progresie geometrica ;

0 nici progesia aritmetica si nici geometrica .

Scrieti o functie nerecursiva care sa calculeze cel de-al n - lea termen al sirului lui Fibonacci .

Sa se scie o functie care converteste caracterul c din litera minuscula in litera majuscula .

Sa se determine o radacina a ecuatiei f _(x) = 0 in intervalul a , b prin metoda injumatatirii intervalului , utilizind o functie recursiva .