– recursivitate si iterativitate ; – functii recursive in C/C++; mecanismul prin care functiile se pot autoapela; – recursivitate directa ; -… [623101]

1 Cuvinte importante :
– recursivitate ;
– recursivitate si iterativitate ;
– functii recursive in C/C++; mecanismul prin care functiile se
pot autoapela;
– recursivitate directa ;
– recursivitate indirect a;
– Ce este mai indicat de utilizat : recursivitate sau iterativitate ?

2 Recursivitate
Un obiect sau un fenomen se define ste in mod recursiv daca in defini tia sa exist a o
referire la el insusi.
Utilitatea practic a a recursivit atii: posibilitatea de a defini un set infinit de obiecte
printr -o singură rela tie sau printr -un set finit de rela tii.
Recursivitatea s -a impus în programare a calculatoarelor odata cu apari tia unor
limbaje de nivel înalt, ce permit scrierea de subprograme ce se autoapelează:
PASCAL, LISP, ADA, ALGOL, C – limbaje recursive
FORTRAN,BASIC,COBOL – limbaje nerecursive
Cum gandim in termeni de recursivitate?
Un exemplu ar fi definirea conceptului de stra mos al unei persoane:
• Un p arinte este str amosul copilului. ("Baza"')
• Parintii unui str amos sunt si ei str amosi ("Pasul de recursie").
O gandire recursiva exprima concentrat o anumita stare, care se repeta la infinit.

3 Cunoastem ca, un algoritm este o succesiune de pasi care transforma multimea
datelor de intrare in date de iesire (rezultatele dorite ).
Plecand de la aceasta definitie , sa enumeram cateva proprietati ale unui algoritm :
-sa posede date de intrare ;
-sa posede date de iesire ;
-determinismul , adica la executarea oricarui pas, trebuie sa cunoastem succesorul
acestuia;
-corectitudinea datelor de iesire (a rezultatelor ) in raport cu datele de intrare ;
-finitudinea , adica pentru orice set de date de intrare posibile ale problemei ,
solutia este furnizata intr-un numar finit de pasi.
Un algoritm este implementat recursiv atunci cand in interiorul sau exista
subprobleme care apeleaza la acelasi algoritm . Rezuta ca recursivitatea este un
mecanism general de elaborare a unui algoritm implementat recursiv .
Rezuta ca, o gandire recursiva se aplica in elaborarea algoritmilor implementati
recursiv cu o modificare esentiala : adaugarea conditiei de terminare . In absenta
acestei conditii nu se poate vorbi despre un algoritm deoarece acesta poseda
proprietatea de finitudine .
Din acest punct de vedere , exemplul din slide -ul precedent nu este corect .

4 Recursivitate si iterativitate

•Iterativitatea inseamna execu tia repetat a a unei port iuni de program, pa na la
indeplinirea unei conditii (folosind instructiuni ca: while, do -while , for din
C/C++). Deci , iterativitatea inseamna folosirea structurilor de control
repetitive “ executa un set de instructiuni pana cand ”.

•Recursivitatea inseamna :
– executia repetata a unui intreg subprogram, functie sau metoda
– in cursul execut iei lui se verific a o condi tie (if din C/C++)
– nesatisfacerea conditiei implica reluarea executiei subprogramului de
la inceput, fa ra ca execu tia curent a a acestuia sa se fi terminat
– in momentul satisfacerii conditiei se revine in ordine inversa in lant ul
de apeluri, relua ndu-se si încheindu-se apelurile suspendate .
In concluzie , recursivitatea inlocuieste structurile de control repetitive .
O precizare importanta :
Algoritmii implementati iterativ se pot transforma in algoritmi implementati
recursiv (pentru o structura repetitiva se creaza un suprogram recursiv) si invers
(se poate folosi structura de date stiva care simuleaza apelurile recursive ).

5 Functii recursive in C/C++
Recursivitatea se exprima cu ajutorul functiilor deoarece ele au un nume care este
specificat in apeluri .
O functie se numeste recursiva daca ea se autoapeleaza.
Dupa tipul apelului , o functie recursiva se autoapeleaza:
-fie direct (in definitia ei, se face apel la ea insasi ),
-fie indirect (adica functia X apeleaza functia Y , care apeleaza functia X).
Orice functie recursiva poate fi scrisa si in forma nerecursiva (folosind structurile
de control repetitive).
Mecanismul prin care functiile se pot autoapela
Se stie ca la apelul fiecarei functii , se genereaza un nou nivel in segmentul de stiva ,
corespunzator acelui apel. Pe acel nivel se memoreaza :
– valorile parametrilor transmisi prin valoare ;
– adresele parametrilor transmisi prin referinta ;
– variabilele locale;
– adresa de revenire din functie .
De fiecare data cand o functie se autoapeleaza, se creeaza un nou nivel in
segmentul de stiva care se suprapune peste vechiul nivel .

6 Recursivitate directa
Exista mai multe feluri de func tii recursive directe:
– functii cu un singur apel recursiv (in definitie); de exemplu: calculul factorialului,
suma cifrelor unui numar etc;
– functii cu doua sau mai multe apeluri recursive (in definitie); de exemplu
numerele Fibonacci, turnurile din Hanoi etc.
Func tii cu un singur apel recursiv (in definitie)
De exemplu: sa se calculeze n!
Se observa ca n !=(n-1) !*n si se stie ca 0 !=1.

Definitia recursiva a lui n ! este :

7 Functia recursiva se va scrie astfel:

long factorial(int n) {if(n==0) return 1;
else return factorial(n-1)*n;} void main() {cout<<factorial(5) ;}
Se observa ca functia factorial se autoapeleaza. Autoapelul se realizeaza
prin instructiunea return factorial(n -1)*n .
Functia nerecursiva se va scrie astfel:
int fact_it (int n) { int i, f; for( i=f=1; i<=n; i++ ) f *= i;
return f;
}

8 In figura de mai jos este prezentat fiecare nivel de apel in segmentul de stiva
pentru functia recursiva factorial(n) , unde n=5.
primul nivel de apel
Observatie:
Fiecare apel de functie lucreaza cu datele aflate pe nivelul corespunzator acelui
apel din segmentul de stiva. La iesirea din apelul unei functii, nivelul respectiv se elibereaza si datele aflate acolo se pierd.

9 Un alt exemplu:
Sa se scrie o functie recursiva care calculeaza si returneaza suma cifrelor unui numar
natural care este primit ca parametru (suma_cifre.cpp). Formula folosita pentru
recursie este: suma_cifre (n) = suma_cifre (n/10)+n%10.
#include< iostream.h >
#include< conio.h>
int sumacif (long n)
{int static i=0;
if(n==0) return 0;
else
{cout<<"n="<<n<<" "<<" nr. apel ="<<++i<<endl ;
return sumacif (n/10)+n%10;}}
void main()
{int nr;
cin>>nr;
cout<<"Suma cifrelor nr. ="<<sumacif (nr);
getch();}
Dupa executia programului , pe ecran se afiseaza:
introduceti numarul:23562
n=23562 nr. apel =1
n=2356 nr. apel =2 n=235 nr. apel =3 n=23 nr. apel =4
n=2 nr. apel =5
Suma cifrelor nr. =18

In figura de mai jos este prezentat fiecare nivel de apel in segmentul de stiva pentru
functia recursiva sumacif (nr) , unde nr=23562.
n=0

n=2, sumacif (2/10)+2%10

n=23, sumacif (23/10)+23%10
n=235, sumacif (235/10)+235%10

n=2356, sumacif (2356/10)+2356%10

n=23562, sumacif (23562/10)+23562%10
cout <<sumacif (23562); sumacif(0)=0
sumacif(2)=0+2
sumacif(23)=2+3
sumacif(235)=5+5
sumacif(2356)=10+6
sumacif(23562)=16+2 Apel Returnat
main()

11 Daca rezolvam aceeasi problema in varianta nerecursiva (folosind instructiuni
repetitive), programul arata astfel:
#include<iostream.h>
#include<conio.h>
void main(){ int nr;
int suma = 0;
cout<<"Introduceti numarul:" ;
cin>>nr;
do { suma=suma+nr%10; //aflare ultima cifra a numarului si ada ugare la suma
nr/=10; // eliminare ultima cifra
cout<<nr<<endl;
} while (nr);
cout<<"Suma cifrelor nr. ="<< suma;
getch();
}

12 Un alt exemplu (sir_invers.cpp) de functie recursiva este inversarea unui sir de
caractere. Dandu -se un sir de caractere citit de la tastatura, functia recursiva
creez_invers () va crea un nou sir care este inversul sirului citit si apoi va afisa pe
ecran sirul de caractere creat in ordine inversa. Functia recursiva este de tip void.
#include <iostream.h>
void creez_invers(char *sir, char *sir1) {static int i =0;
cout << "Sunt in functia creez_invers cu "<< sir << endl;
if (*sir) {
creez_invers(sir+1, sir1);
sir1 [i] = *sir;
i++;
sir1 [i] = ' \0';
cout << "Sfarsit apel recursiv cu " << sir1 << endl; }
}

13 void main()
{char sir_sursa[64];
char sir_destinatie[64];
cout << "Introduceti sirul de inversat: \n";
cin.getline (sir_sursa, sizeof(sir_sursa));
creez_invers(sir_sursa, sir_destinatie);
cout << sir_destinatie;}
Dupa executia programului, pe ecran se afiseaza:
Introduceti sirul de inversat:
adriana
Sunt in functia creez_invers cu adriana Sunt in functia creez_invers cu driana Sunt in functia creez_invers cu riana Sunt in functia creez_invers cu iana
Sunt in functia creez_invers cu ana
Sunt in functia creez_invers cu na Sunt in functia creez_invers cu a Sunt in functia creez_invers cu // ultimul apel al functiei recursive
Sfarsit apel recursiv cu a Sfarsit apel recursiv cu an
Sfarsit apel recursiv cu ana Sfarsit apel recursiv cu anai Sfarsit apel recursiv cu anair
Sfarsit apel recursiv cu anaird
Sfarsit apel recursiv cu anairda anairda

14 In figura de mai jos este prezentat fiecare nivel de apel in segmentul de stiva pentru
functia recursiva creez_invers (sir_sursa , sir_destinatie ) , unde sir_sursa = “adriana ”
iar continutul variabilei sir_destinatie se formeaza din revenirile din apelurile
recursive ale functiei .
Apeluri stiva La revenire din apeluri
i=0, creez_invers (“\0”, sir1) S-a indeplinit conditia de iesire
din apeluri – terminat
i=0, creez_invers (“a”, sir1) sir1[0] = ‘a’, i=1, sir1[1] = ‘\0’
i=0, creez_invers (“na”, sir1) sir1[1] = ‘n’, i=2, sir1[2] = ‘\0’
i=0, creez_invers (“ana”, sir1) sir1[2] = ‘a’, i=3, sir1[3] = ‘\0’
i=0, creez_invers (“iana”, sir1) sir1[3] = ‘i’, i=4, sir1[4] = ‘\0’
i=0, creez_invers (“riana ”, sir1) sir1[4] = ‘r’, i=5, sir1[5] = ‘\0’
i=0, creez_invers (“driana ”, sir1) sir1[5] = ‘d’, i=6, sir1[6] = ‘\0’
i=0, creez_invers (“adriana ”, sir1) sir1[6] = ‘a’, i=7, sir1[7] = ‘\0’
creez_invers (“adriana ”, sir_destinatie ); sir_destinatie = “anairda” main()

15 Daca rezolvam aceeasi problema in varianta nerecursiva (folosind instructiuni
repetitive), programul arata astfel:
#include<iostream.h>
#include<conio.h>
void main(){ int i, j ; char sir_sursa [64];
char sir_destinatie[64];
cout<<"Introduceti sirul de inversat"<<endl;
cin.getline(sir_sursa,sizeof(sir_sursa));
j = strlen(sir_sursa)-1;
for (i = 0; i < strlen(sir_sursa); i++) { sir_destinatie[i]=sir_sursa[j];
j–;
} sir_destinatie[i]=' \0';
cout<<sir_destinatie;
getch();
}

16 Exemplu de functii ce calculeaza produsul primelor n numere naturale :
Functia in varianta nerecursiva
#include<iostream.h>
int f(int n)
{int i=1, P=1;
while (i<=n)
{P=P*i ;
i++ ;}
return P ;} void main() {int n=5;
cout<<f(n);} Functia recursiva 1
#include<iostream.h>
int n;
int f(int i)
{if (i<=n) return i*f(i+1);
else return 1 ;} void main() {n=5;
cout<<f(1)<<endl;
Functia recursiva 2
#include<iostream.h>
int f(int i)
{if (i>1) return i*f(i -1);
else return 1 ;} void main() {int n=5;
cout<<f(n);} Se observa ca la primele doua subprograme conditia de continuare (a instructiunii repetitive respectiv a autoapelului) este aceeasi. Recomandare : inainte de elaborarea functiilor
recusive este de preferat sa se creeze mai intai functia nerecursiva apoi sa se realizeze functia recursiva.

17 Programul urmator (nr_patru_recursiv.cpp) construieste pentru un numar natural, citit
de la tastatura, succesiunea de numere care duce la numarul 4. Succesiunea de numere
se afiseaza la ecran. Functia recursiva se numeste numar_patru().
De exemplu, pentru numarul 12, succesiunea de numere naturale afisate la ecran pana la numarul 4 este: 4->2 ->24->12 sau
4->2 ->1->10->5 ->50->504->252->2524
#include<iostream.h>
#include<conio.h>
void numar_patru(int);
void main() { int n;
cout<<"Introduceti numarul: ";
cin>>n;
cout<<"4" ;
numar_patru(n);
getch(); }
void numar_patru(int nr){ if(nr !=4){
switch (nr%10) {
case 0: numar_patru(nr/10); break;
case 4: numar_patru(nr/10); break;
default: numar_patru(nr*2); }
cout<<" ->"<<nr; }
}

18 Programul urmator (recursie_pozitive_matrice.cpp) calculeaza suma elementelor
pozitive dintr -o matrice folosind varianta recursiva.
Functia recursiva se numeste calcul_pozitive() si returneaza din fiecare apel suma
elementelor de pe linia i la care se adauga suma returnata din ultimile apeluri ale
functiei pana se ajunge la linia n-1.
#include<iostream.h>
#include<conio.h>
int calcul_pozitive(int [][10], int,int);
void main(){ int i, j, suma, n, m;
int a[10][10];
cin>>n;
m=n;
for (i = 0; i < n; i++) {
for(j=0;j<n;j++)
cin>>a[i][j];
}
suma = calcul_pozitive(a,n -1, m);
cout<<suma;
getch();
}

19 int calcul_pozitive(int matr[][10],int i,int m) {
int j=0;
int s=0;
if(i>=0) {
for (j = 0;j<m; j++)
if(matr[i][j]>=0)
s=s+matr[i][j]; //calcul suma pe fiecare linie
cout<<s<<endl;
return s+calcul_pozitive(matr,i -1,m) ;
}
else
return 0;
}

20 Observa tii:

•Orice func tie recursiva trebuie s a contina (cel put in) o instruc tiune if (de obicei
chiar la inceput), prin care se verific a dacă (mai) este necesar un apel recursiv
sau se iese din functie ;
•Absenta instructiunii if conduce la o recursivitate infinita (la autoapeluri fara
conditie de terminare) si segmentul de stiva se ocupa total; in acest caz
programul se va termina cu eroarea «Stack overflow»;
•Apelul functiei recursive este de obicei conditionat astfel:
void f_recursiva( ){
if (condiție) f_recursiva(); // apel finit condiționat
}
•In func tiile recursive repetarea operatiilor este ob tinută prin apelul recursiv;
•Pe parcursul unui apel, sunt accesibile doar variabilele locale si parametrii
pentru apelul respectiv, nu si cele pentru apelurile anterioare, chiar dacă acestea
poart a acelas i nume ;
•Atenție! Pentru fiecare apel recursiv al unei func tii se creaza copii locale ale
parametrilor valoare s i ale variabilelor locale, ceea ce poate duce la risip a de
memorie!

21 Func tii cu doua sau mai multe apeluri recursive in definitie

Fie sirul lui Fibonacci, definit astfel:
fibo(n) = 0 , dacă n=0
fibo(n) = 1 ,daca n=1
fibo(n) = fib(n-1) + fib(n-2) , dacă n>1
Adica: 0, 1, 1, 2, 3, 5, 8, 13, …. Fie n un numar natural citit de la tastatura. Sa se calculeze folosind o functie
nerecursiva si o functie recursiva cel de -al n-lea termen din sirul Fibonacci.
#include<stdio.h>
#include<conio.h>
int fibo_it (int); //functia nerecursiva
int fibo(int); //functia recursiva
int main (){ int n;
printf("Introduceti n=");
scanf ("%d", &n);
printf ("recursiv=%d nerecursiv=%d", fibo(n), fibo_it(n));
getch ();
return 0;
}

22 int fibo_it (int n) // varianta nerecursiva
{
int f1=0,f2=1,fn=1, i;
if (n==0)return 0;
if (n==1) return 1;
for (i=2; i<=n; i++) { fn=f1+f2;
f1=f2;
f2=fn;
} return fn;
} int fibo (int n) // varianta recursiva
{int static i=1; printf("Apel %d ",i++);
if ( n==0) {printf("n=%d \ n",n);return 0;}
if ((n==1)){printf("n=%d \n",n);return 1; }
printf("n=%d \n",n);
return fibo(n -1)+ fibo(n -2) ;
}

23 In figura de mai jos este prezentat fiecare nivel de apel in segmentul de stiva
pentru functia recursiva fibo(n).
n=0 n=1
n=2, fibo(1)+ fibo(0)

n=3, fibo(2)+ fibo(1)

n=4, fibo(3)+ fibo(2)
n=5, fibo(4)+ fibo(3)

printf ("recursiv=%d
nerecursiv=%d", fibo(5), fibo_it(5)); 1
1+fibo(0)=1+0=1
1+fibo(1)=1+1=2
2+fibo(2)=2+fibo(1)+fibo(0)=2+1+0=3
3+fibo(3)=3+fibo(2)+fibo(1)=
3+fibo(1)+fibo(0)+1=3+1+0+1=5 Apel
initial Returnat si apeluri intermediare
main()

24 Dupa executia programului, pe ecran se afiseaza:
Introduceti n=5
Apel 1 n=5 Apel 2 n=4 Apel 3 n=3 Apel 4 n=2 Apel 5 n=1 Apel 6 n=0 Apel 7 n=1 Apel 8 n=2 Apel 9 n=1 Apel 10 n=0 Apel 11 n=3 Apel 12 n=2 Apel 13 n=1 Apel 14 n=0 Apel 15 n=1 recursiv=5 nerecursiv=5

25 Exemplu de a lgoritm de divizare – "divide et impera “ care
implementeaza functii cu doua apeluri recursive in definitie

Algoritmul de divizare general c onsta in:
– descompunerea unei probleme complexe in mod recursiv in mai multe
subprobleme a caror rezolvare e mai simpl a;
– rezolva subproblemele;
– combina solutiile subproblemelor pentru obtinerea solutiei problemei
initiale.
Astfel:
void rezolva (problema x) {
if (x poate fi descompus în subprobleme) {
//divide pe x în parti x1,…,xk
rezolva(x1);
//…
rezolva(xk);
//combina solutiile partiale intr -o solutie }
else
//rezolva pe x direct}
Exemple: determinarea minimului si maximului valorilor elementelor unui tablou;
cautarea binara; turnurile din Hanoi .

26 Programul urmator (hanoi_recursiv.cpp) ilustreaza modul de rezolvare prin
recursivitate a problemei turnurilor din Hanoi.
Problema turnurilor din Hanoi este un joc vechi de origine asiatica, in care un anumit numar de discuri este plasat pe trei tije A, B, C. Discurile au diametre diferite si sunt gaurite la mijloc, astfel incat sa poata intra pe cele trei tije.
Initial, toate discurile sunt situate pe tija A (sursa) .
Obiectivul jocului este de a transfera toate discurile de pe tija A (sursa) pe tija C (destinatia).
Restrictiile jocului sunt:
a) la un moment dat, se poate deplasa numai un singur disc;
b) nici un disc nu poate fi asezat deasupra unui disc mai mic decat el.

27 Algoritmul recursiv de rezolvare a problemei turnurilor din Hanoi.

Dorim sa deplasam toate discurile de pe un turn sursa (notat cu S ) pe unul destinatie
(notat cu D). Dispunem de un turn intermediar (notat cu I ).
Presupunem ca avem n discuri pe turnul S , asezate de jos in sus in ordinea marimii
discurilor (discul cel mai mare – n este la baza si discul cel mai mic – 1 este in varf).
Algoritmul de rezolvare este:
1. Primele n-1 discuri se deplaseaza de pe S pe I;
2. Discul ramas (cel mai mare) se deplaseaza de pe S pe D.
3. Primele n-1 discuri se deplaseaza de pe I pe D.
Initial , turnul sursa este A, turnul intermediar este B, iar cel de destinatie este C. Sa
presupunem ca pe turnul initial se gasesc 3 discuri.

28
Solutia se construieste pornind de la urmatoarea observatie: pentru a muta n discuri
de pe turnul A pe turnul C cu ajutorul turnului B, se muta mai intai n-1 discuri de pe
turnul A pe turnul B prin intermediul turnului C, dupa care se executa mutarea
discului cel mai mare (de la baza) de pe discul A pe discul C, urmata de mutarea a n-1 discuri de pe turnul B pe turnul C prin intermediul turnului A.
Astfel se defineste functia recursiva hanoi:

hanoi (n, A,B,C) =
A C daca n=1 (conditia de terminare a functiei)
hanoi(n-1, A, B, C), daca n>1(mutare pe discul intermediar) A C , daca n>1(mutarea discului de la baza)
Hanoi (n-1, B, A, C) daca n>1 (mutare pe discul destinatie)
In programul prezentat in slide -ul urmator parametrii de apel ai functiei hanoi sunt
apelati in ordinea : A este turnul sursa, B este turnul intermediar si C este turnul destinatie.
Functia hanoi() este un exemplu de functie recursiva de tip void cu doua apeluri
in definitia functiei.

29 #include <iostream.h>
void hanoi (int, char, char, char);
void main()
{int nr;
cout << "Introduceti numarul de discuri: " ;
cin >> nr;
hanoi (nr, 'A', 'B', 'C');}

void hanoi (int n, char sursa, char inter, char desti) {
cout << "In functia hanoi cu n = " << n << " " <<endl;
cout << sursa << inter << desti << endl;
if (n==1)
cout << "Discul 1 de pe " << sursa << " pe " << desti << endl;
else
{hanoi (n- 1, sursa, desti, inter); //muta discurile de pe sursa pe turnul intermediar
cout <<"Discul "<<n<<" de pe "<< sursa<<" pe "<<desti<<endl; //muta discul de la
baza pe destinatie hanoi (n- 1, inter, sursa, desti); //muta discurile de pe turnul intermediar la destinatie
}
getch();
}

30 Dupa executia programului pe ecran se afiseaza:

Introduceti numarul de discuri: 3 In functia hanoi cu n = 3 ABC
In functia hanoi cu n = 2 ACB
In functia hanoi cu n = 1 ABC
Discul 1 de pe A pe C
Discul 2 de pe A pe B
In functia hanoi cu n = 1 CAB
Discul 1 de pe C pe B
Discul 3 de pe A pe C
In functia hanoi cu n = 2 BAC
In functia hanoi cu n = 1 BCA
Discul 1 de pe B pe A
Discul 2 de pe B pe C
In functia hanoi cu n = 1 ABC
Discul 1 de pe A pe C

31 Niveluri de apel din segmentul de stiva pentru functia recursiva hanoi()
Apeluri pe stiva
n=1 hanoi (1,A,B,C)

hanoi (1, C, A, B)

hanoi (1, B, C, A )

hanoi (1, A, B, C )
“Discul 1 de pe A->C”
(terminat)
“Discul 1 de pe C->B”
(terminat)
“Discul 1 de pe B->A”
(terminat)
“Discul 1 de pe A->C”
(terminat)
n=2 hanoi (2, A,C,B)
“Discul 2de pe A->B”
hanoi (1, C, A, B)
hanoi (1, B, C, A)
“Discul 2de pe B->C”
Hanoi(1, A, B, C)
n=3 hanoi (3, A, B, C)
“Discul 3de pe A->C”
hanoi (2, B, A, C)
main() hanoi (nr, 'A', 'B', 'C');

32 Recursivitate indirect a

Recursivitatea se poate realiza si in mod indirect , atunci ca nd in cadrul “corpului”
unei func tii apare apelul unei alte func tii care la r andul s au apeleaza direct sau
indirect func tia respectiv a.
De exemplu, s a presupunem c a in func tia f1() intervine un apel al func tiei f2(). In
functia f2() intervine un apel al func tiei f1(). Se observa ca functia f1() se
autoapeleaza , prin intermediul func tiei f2(). Prin urmare func tia f1() este indirect
recursiv a.
f1 f2
Observatie:
Functiile apelate trebuie declarate, deoarece nu se pot evita declarat iile prin
ordinea in care sunt definite func tiile.

33 Exemplu:

void f1 ( )
{ void f2 ( ); // functia apelata de f1 trebuie declarata
…
f2( ); // apel f2
} void f2 ( )
{ void f1 ( ); // functia apelata de f2 trebuie declarata
…
f1( ); // apel f1
} void main() { ……… }

34 Altă variantă de scriere mai eleganta:

// declaratii func tii
void f1 ( );
void f2 ( );
void main() { ……… } // defini tii func tii
void f1 ( ) { …
f2( ); // apel f2
} void f2 ( ) { …
f1( ); // apel f1
}

35 Exemplu de recursivitate indirecta

Fie sirul: a0, b0, a1, b1, a2, b2….., an, bn, unde: an > 0 si bn > 0
Urmatorul program (recursie_indirecta1.cpp) calculea za an , bn si n termeni din sir,
pentru a, b, n citite de la tastatura .

Pentru rezolvarea problemei se folosesc doua functii fa() si fb(). Fiecare dintre ele
se autoapeleaza, dar o apeleaza si pe cealalta. ,n>0
a0 = a b0 = b , n>0

36 #include<iostream.h>
#include<conio.h>
double a0,b0;
double fa(int n);
double fb(int n);
void main() { int n;
cout<<"n=";
cin>>n;
cout<<"a0=";
cin>>a0;
cout<<"b0=";
cin>>b0;
cout<<endl<<"a["<<n<<"]="<<fa(n)<<endl;
cout<<"b["<<n<<"]="<<fb(n)<<endl;
for(int i=0;i<=n;i++){ cout<<"a["<<i<<"]="<<fa(i)<<endl;
cout<<"b["<<i<<"]="<<fb(i)<<endl; }
getch();
}

37 double fa(int n)
{
static j = 1; cout<<"Sunt in functia fa "<<"Apelul " << j++<<" n= "<< n<<endl;
if (n==0) return a0;
else
return (fa(n-1)+fb(n-1))/2;
} double fb(int n)
{ static k = 1; cout<<"Sunt in functia fb "<<"Apelul " << k++<<" n= "<< n<<endl;
if (n==0) return b0;
else
return fa(n-1)*fb(n-1);
}

38 Dupa executia programului pe ecran se afiseaza:
n=2
a0=2
b0=4 Sunt in functia fa Apelul 1 n= 2 Sunt in functia fa Apelul 2 n= 1 Sunt in functia fa Apelul 3 n= 0 Sunt in functia fb Apelul 1 n= 0 Sunt in functia fb Apelul 2 n= 1 Sunt in functia fa Apelul 4 n= 0 Sunt in functia fb Apelul 3 n= 0 a[2]=5.5 Sunt in functia fb Apelul 4 n= 2 Sunt in functia fa Apelul 5 n= 1 Sunt in functia fa Apelul 6 n= 0 Sunt in functia fb Apelul 5 n= 0 Sunt in functia fb Apelul 6 n= 1 Sunt in functia fa Apelul 7 n= 0 Sunt in functia fb Apelul 7 n= 0 b[2]=24
Apelurile din main() pentru
a[n], b[n]

39 Sunt in functia fa Apelul 8 n= 0
a[0]=2 Sunt in functia fb Apelul 8 n= 0 b[0]=4 Sunt in functia fa Apelul 9 n= 1 Sunt in functia fa Apelul 10 n= 0 Sunt in functia fb Apelul 9 n= 0 a[1]=3 Sunt in functia fb Apelul 10 n= 1 Sunt in functia fa Apelul 11 n= 0 Sunt in functia fb Apelul 11 n= 0 b[1]=8 Sunt in functia fa Apelul 12 n= 2 Sunt in functia fa Apelul 13 n= 1 Sunt in functia fa Apelul 14 n= 0 Sunt in functia fb Apelul 12 n= 0 Sunt in functia fb Apelul 13 n= 1 Sunt in functia fa Apelul 15 n= 0 Sunt in functia fb Apelul 14 n= 0 a[2]=5.5 Sunt in functia fb Apelul 15 n= 2 Sunt in functia fa Apelul 16 n= 1 Sunt in functia fa Apelul 17 n= 0 Sunt in functia fb Apelul 16 n= 0 Sunt in functia fb Apelul 17 n= 1 Sunt in functia fa Apelul 18 n= 0 Sunt in functia fb Apelul 18 n= 0 b[2]=24
Apelurile din main() din ciclul for pentru a[i], b[i] unde i=0, 1, 2

40 Daca rezolvam aceeasi problema in varianta nerecursiva (folosind instructiuni
repetitive), programul arata astfel:
#include<iostream.h>
#include<conio.h>
void main() {double a0,b0;
double an, bn;
int n;
cout<<"n=";
cin>>n;
cout<<"a[0]=";
cin>>a0;
cout<<"b[0]=";
cin>>b0;
for(int i=1;i<=n;i++){ an=(a0+b0)/2;
bn=a0*b0;
a0=an;
b0=bn;
cout<<"a["<<i<<"]="<<an<<endl;
cout<<"b["<<i<<"]="<<bn<<endl;}
getch();}

41 Ce este mai indicat de utilizat: recursivitatea sau iterativitatea ?
•Recursivitatea este potrivita pentru:
– probleme care utilizeaza relatii de recurenta ;
– prelucrarea structurilor de date definite recursiv (liste, arbori);
•Recursivitatea permite crearea de cod mai simplu de înțeles și verificat;
•Uneori insa este mai greu de dedus rela tia de recuren ta.
•Iterativitatea este preferată (uneori) din cauza :
– vitezei mai mari de execuție;
– memoriei mai reduse .
Este de preferat ca atunci cand programul recursiv poate fi transformat cu usurinta
intr-unul nerecursiv , sa se faca apel la cel din urma .
De exemplu, asa cum am aratat , varianta recursiva a functiei Fibonacci duce la 15
apeluri pentru n=5, in timp ce varianta nerecursiva (cu utilizarea structurii
repetitive for) este mult mai performantă.

42 De aceea, la implementare a unei solutii , poate fi necesară transformarea
algoritmului recursiv in unul nerecursiv, i n situa tii precum :
– solutia problemei trebuie scrisa intr -un limbaj nerecursiv; un caz
particular sunt compilatoarele ce "traduc" un program recursiv dintr-un limbaj de
nivel inalt in cod ma sină (nerecursiv);
– varianta recursiva ar duce la o viteza de executie si spatiu de memorie
prea mari, transformarea in una nerecursiva eliminând dezavantajele .
In scrierea unei variante nerecursive, trebuie parcursi toti pasii implica ti in
varianta recursiva , prin tehnici nerecursive.
Functiile recursive cu mai multe apeluri sau cu un apel care nu este ultima
instruc tiune pot fi rescrise iterativ prin folosirea structurii de date stiva
(implementata utilizand un vector si adaugand si extragand de la sfarsitul
vectorului).

43 Functiile recursive sunt lente pentru ca la fiecare apel se introduce in program o
suprasarcina de apel a functiei (overhead).
Suprasarcina de apel reprezinta intervalul de timp necesar calculatorului pentru a incarca si a descarca informatiile din stiva. Desi, calculatorul poate executa rapid aceste operatii de incarcare si descarcare, totusi ele consuma timp.
Apelul functiei recursive de un numar prea mare de ori va determina cresterea
considerabila a duratei de executie a programului.
De asemenea, utilizarea apelului recursiv necesita atentie la necesarul de stiva. Daca numarul de apeluri recursive ale functiei este prea mare, s -ar putea depasi capacitatea
stivei (stack overflow).

44 Problema de rezolvat:

Sa se deduca valoarea functiei f pe care o afiseaza programul de mai jos. Sa se
descrie valorilor stocate pe niveluri de apel in stiva:
#include<iostream.h>
#include<conio.h>
int f(int n) { if((n==0) || (n==1)) return n;
else return f(n-1)+2*f(n-2);
} void main() { cout<<f(5);
getch();
}