Recursivitate

1. Scrieti o functie recursiva cu numele cifre care primeste prin parametrul

n un numar natual si furnizeaza:
- prin parametrul p numarul format cu cifrele pare ale lui n,
- prin parametrul i numarul format cu cifrele impare ale lui n.
Exemplu:
In urma apelului cifre(4536597,p,i); variabila p va fi egala cu 46, iar i cu
53597.

void cifre(int n, int &p, int &i)

{
if(n<=9) if(n%2==0) { p=n; i=0; }
else { p=0; i=n; }
else
{
cifre(n/10,p,i);
if(n%2==0) p=p*10+n%10;
else i=i*10+n%10;
}
}

2. Sa se scrie o functie recursiva care calculeaza si returneaza diferenta dintre suma elementelor de pe
pozitii pare si cea a celor aflate pe pozitii impare dintr-un vector A primit ca parametru impreuna cu n
reprezentand numarul lui de elemente.

Elementele tabloului sunt indexate de la 1.

Exemplu:

Daca functia primeste tabloul A={4,5,6,3,2,9} cu n=6, atunci va returna 5 adica (5+3+9)-(4+6+2).

int dif_poz(int A[], int n)

if(n==0) return 0;

else if(n%2==0) return dif_poz(A,n-1)+A[n];

else return dif_poz(A,n-1)-A[n];

}
3.Scrieti o functie recursiva care primeste ca paramentru un numar natural n si returneaza numarul
obtinut din n prin eliminarea cifrelor impare.

Exemplu: daca n=234435, functia returna 244.

int stergimp(int n)

if(n==0) return 0;

else if(n%2==1) return stergimp(n/10);

else return stergimp(n/10)*10+n%10;

4. Citirea si afisarea unei matrici folosind functii recursive.

#include <iostream>

using namespace std;

void citire(int A[][101], int n, int m, int i, int j)

if(i<=n)

cin>>A[i][j];

if(j<m) citire(A,n,m,i,j+1);

else citire(A,n,m,i+1,1);

void afisare(int A[][101], int n, int m, int i, int j)

if(i<=n)

{
 cout<<A[i][j]<<" ";

if(j<m) afisare(A,n,m,i,j+1);

else

cout<<endl;

afisare(A,n,m,i+1,1);

int main()

int A[101][101],n,m;

cin>>n>>m;

citire(A,n,m,1,1);

afisare(A,n,m,1,1);

return 0;

5. Se citeste un vector cu n elemente numere naturale (n<=100).

Sa se inlocuiasca fiecare element al vectorului cu suma cifrelor cu aceeasi paritate ca si indicele

elementului. Indexarea elementelor incepe de la 1.

Se vor scrie si folosi functii recursive pentru:

- citirea vectorului

- afisarea vectorului

- calculul sumei cifrelor de o anumita paritate

- inlocuirea ceruta

Exemplu: Pentru datele de mai jos

7223 435 6667 24 55 662 122

Sirul rezultat este

3 4 7 6 10 14 1

#include <iostream>

using namespace std;

void citire(int A[], int n)

if(n>0)

citire(A,n-1);

cin>>A[n];

int sumcifp(int n, int p)

if(n==0) return 0;

else if(n%2==p) return sumcifp(n/10,p)+n%10;

else return sumcifp(n/10,p);

void inlocuire(int A[], int n)

if(n>0)

inlocuire(A,n-1);

A[n]=sumcifp(A[n],n%2);

}
void afisare(int A[], int n)

if(n>0)

afisare(A,n-1);

cout<<A[n]<<" ";

int main()

int A[101],n;

cin>>n;

citire(A,n);

inlocuire(A,n);

afisare(A,n);

return 0;

6. Se citeste un numar natural n cu cel mult 9 cifre. Afisati numarul de cifre distincte ale lui n. Se vor
folosi exclusiv subprograme recursive.

Exemplu:

Pentru n=38837 se afiseaza 3 (cifrele distinte sunt 3,7 si 8).

#include <iostream>

using namespace std;

int apcif(int n, int c)

{//numarul de aparitii ale lui c in n

if(n<=9) return n==c;

 else if(n%10==c) return apcif(n/10,c)+1;

else return apcif(n/10,c);

int dist(int n, int c)

{//numara cifrele distincte ale lui n

if(c==-1) return 0;

else if(apcif(n,c)) return dist(n,c-1)+1;

else return dist(n,c-1);

int main()

int n;

cin>>n;

cout<<dist(n,9);

return 0;

sau

#include <iostream>

using namespace std;

int apcif(int n, int c)

{//verific daca c apare in n

if(n<=9) return n==c;

else if(n%10==c) return 1;

 else return apcif(n/10,c);

int nrdist(int n)

{//numara cifrele distincte ale lui n

if(n==0) return 0;

else if(apcif(n/10,n%10)==0) return nrdist(n/10)+1;

else return nrdist(n/10);

int main()

int n;

cin>>n;

cout<<nrdist(n);

return 0;

7. Se citeste un numar natural n (n<=20). Afisati un desen format din caracterul * ca in exemplul de mai
jos. Se vor folosi exclusiv subprograme recursive.

Exemplu:

Pentru n=3 se afiseaza

***

*****

***

#include <iostream>

using namespace std;

void linie(int n, char c)

if(n>0)

linie(n-1,c);

cout<<c;

void sus(int n, int r)

if(r<=n)

linie(n-r,' ');

linie(2*r-1,'*');

cout<<endl;

sus(n,r+1);

void jos(int n, int r)

if(r<=n)

jos(n,r+1);

linie(n-r+1,' ');

linie(2*r-1,'*');

cout<<endl;
 }

int main()

int n;

cin>>n;

sus(n,1);

jos(n-1,1);

return 0;

8. Se citeste un numar natural n. Sa se descompuna ca suma de puteri crescatoare ale lui 2. Se vor folosi
doar prelucrari/calcule realizate cu ajutorul functiilor implementate recursiv.

Exemplu: Pentru n=84 va afisa 4 16 64 (84 se descompune ca 4+16+64)

#include <iostream>

using namespace std;

unsigned int pm2(int n, unsigned int p)

if(p*2>n) return p;

else return pm2(n,p*2);

void puteri2(int n)

if(n>0)

unsigned int p=pm2(n,1);

puteri2(n-p);
 cout<<p<<" ";

int main()

int n;

cin>>n;

puteri2(n);

return 0;

sau

#include <iostream>

using namespace std;

void puteri2(int n, int p)

if(n>0)

if(n%2==1)

cout<<p<<" ";

puteri2(n/2,p*2);

int main()

{
 int n;

cin>>n;

puteri2(n,1);

return 0;

9.

Se dau n bombe, numerotate de la 1 la n, pentru fiecare cunoscandu-se coordonatele (x,y) unde sunt plasate si raza
r. La explozia unei bombe se va distruge totul in interiorul si pe cercul de centru (x,y) si raza r, iar daca exista
aceasta zona, acestea vor exploda la randul lor. Se da indicele k al primei bombe care explodeaza si se cere sa se
bombe raman
Datele se citesc din fisierul bombe.in si rezultatele se vor afisa in fisierul
In fisierul bombe.in pe prima linie se afla numerele n si k, iar pe urmatoarele n linii coordonatele si razele de distrug
bombe. n si k sunt numere naturale, coordonatele numere intregi, iar razele nume
Exemplu:
bombe.in
8
4 5
-3 -4
4 1
2 1
2 2
1 1
-1 1
-3 3
bombe.out
3
Explicatie: Prima explodeaza bomba rosie (a 5-a), ea declanseaza cele doua bombe verzi, iar fiecare dintre cele ve
cate una albastra. Bombele negre raman neexplodate.
#include <fstream>

using namespace std;

ifstream fin("bombe.in");

ofstream fout("bombe.out");

struct bomba

int x,y,p,e;

};

bomba B[101];

int n,k;

double dist2(int x, int y, int a, int b)

return (x-a)*(x-a)+(y-b)*(y-b);

void explozie(int k)
{

B[k].e=1;

for(int i=1;i<=n;i++)

if(B[i].e==0 && dist2(B[k].x, B[k].y, B[i].x, B[i].y)<=B[k].p*B[k].p)

explozie(i);

int main()

int c=0;

fin>>n>>k;

for(int i=1;i<=n;i++)

fin>>B[i].x>>B[i].y>>B[i].p;

B[i].e=0;

explozie(k);

for(int i=1;i<=n;i++)

if(B[i].e==0) c++;

fout<<c;

fin.close();

fout.close();

return 0;

10. a) Scrieti o functie recursiva litera cu doi parametri s si c unde s e un cuvant, iar c este o litera si care
returneaza de cate ori apare litera c in cuvantul s.

b) Scrieti o functie recursiva litere cu trei parametri s, n si c unde s e un vector ce memoreaza cel mult 20
de cuvinte, n e numar natural reprezentand numarul de cuvinte din vectorul s, iar c este o litera si care
returneaza de cate ori apare litera c in total in cele n cuvinte din vectorul s (va folosi functia litera).
c) Se citeste un numar n si un vector s de n cuvinte. Folosind functia litere, determinati si afisati literele
care apar de un numar maxim de ori in cuvintele din vectorul s.

Exemplu: n=3, s={"ana", "are", "mere"} => a e

#include <iostream>

#include <cstring>

using namespace std;

int litera(char s[21], char c)

if(strlen(s)==0) return 0;

else if(s[0]==c) return 1+litera(s+1,c);

else return litera(s+1,c);

int litere(char s[21][21], int n, char c)

if(n==0) return 0;

else return litera(s[n],c)+litere(s,n-1,c);

int main()

char s[21][21],map=0;

int n;

cin>>n;

for(int i=1;i<=n;i++)

cin>>s[i];

for(char c='a';c<='z';c++)

if(litere(s,n,c)>map) map=litere(s,n,c);
 for(char c='a';c<='z';c++)

if(litere(s,n,c)==map) cout<<c<<" ";

return 0;

11. a) Scrieti o functie recursiva cifra cu doi parametri n si c unde n e numar natural, iar c este o cifra si
care returneaza de cate ori apare cifra c printre cifrele numarului n.

b) Scrieti o functie recursiva cifre cu trei parametri a, n si c unde a e un vector cu cel mult 100 de
elemente numere naturale, n e numar natural reprezentand numarul de elemente din vectorul a, iar c
este o cifra si care returneaza de cate ori apare cifra c in total in cele n numere din vectorul a (va folosi
functia cifra).

c) Se citeste un numar n si un vector a cu n elemente numere naturale. Folosind functia cifre determinati
si afisati cifrele care apar de un numar maxim de ori in numerele din vectorul a.

Exemplu: n=6, a={7, 9, 373, 127, 733, 661} => 3 7

#include <iostream>

using namespace std;

int cifra(int n, int c)

if(n<10) return n==c;

else if(n%10==c) return 1+cifra(n/10,c);

else return cifra(n/10,c);

int cifre(int a[], int n, int c)

if(n==0) return 0;

else return cifre(a,n-1,c)+cifra(a[n],c);

int main()
{

int n,a[101],c,map=0;

cin>>n;

for(int i=1;i<=n;i++)

cin>>a[i];

for(c=0;c<=9;c++)

if(cifre(a,n,c)>map) map=cifre(a,n,c);

for(c=0;c<=9;c++)

if(cifre(a,n,c)==map) cout<<c<<" ";

return 0;

12. Se citeste un vector a cu n elemente numere intregi. Construiti si afisati doi vectori b si c contruiti
astfel:

- vectorul b contine elementele pare din vectorul a

- vectorul c contine elementele impare din vectorul a

Se vor folosi functii recursive pentru citire si afisare, precum si pentru construirea celor doi vectori
ceruti.

Exemplu:

date.in

2579254

date.out

224

5795

#include <fstream>

using namespace std;

ifstream is("date.in");

ofstream os("date.out");
void citire(int a[], int n)

if(n>0)

citire(a,n-1);

is>>a[n];

void afisare(int a[], int n)

if(n>0)

afisare(a,n-1);

os<<" "<<a[n];

void split(int a[],int n,int b[],int &m,int c[],int &k)

if(n>0)

split(a,n-1,b,m,c,k);

if(a[n]%2==0)

b[++m]=a[n];

else

c[++k]=a[n];

}
}

int main()

int a[200],b[100],c[100],n,m=0,k=0;

is>>n;

citire(a,n);

split(a,n,b,m,c,k);

afisare(b,m);

os<<endl;

afisare(c,k);

is.close();

os.close();

return 0;

13. Sortare cu metoda selectiei (metoda elevului) - implementare recursiva (tabloul este indexat
incepand cu 0)

#include <fstream>

using namespace std;

ifstream is("date.in");

ofstream os("date.out");

void elev_rec(int a[], int n, int i, int j)

if(i<n-1)

if(a[i]>a[j]) {int aux=a[i]; a[i]=a[j]; a[j]=aux;}

if(j<n-1) elev_rec(a,n,i,j+1);
 else elev_rec(a,n,i+1,i+2);

int main()

int a[100],n;

is>>n;

for(int i=0;i<n;i++)

is>>a[i];

elev_rec(a,n,0,1);

for(int i=0;i<n;i++)

os<<a[i]<<" ";

is.close();

os.close();

return 0;

16. Sortare cu metoda selectiei (metoda elevului) - implementare recursiva (tabloul este indexat
incepand cu 0)

#include <fstream>

using namespace std;

ifstream is("date.in");

ofstream os("date.out");

void elev_rec(int a[], int n, int i, int j)

if(i<n-1)

if(a[i]>a[j]) {int aux=a[i]; a[i]=a[j]; a[j]=aux;}

 if(j<n-1) elev_rec(a,n,i,j+1);

else elev_rec(a,n,i+1,i+2);

int main()

int a[100],n;

is>>n;

for(int i=0;i<n;i++)

is>>a[i];

elev_rec(a,n,0,1);

for(int i=0;i<n;i++)

os<<a[i]<<" ";

is.close();

os.close();

return 0;

17.Sortare cu metoda bulelor - implementare recursiva (tabloul este indexat incepand cu 0)

#include <fstream>

using namespace std;

ifstream is("date.in");

ofstream os("date.out");

void bule_rec(int a[], int n)

int gata=1;

for(int i=0;i<n-1;i++)

if(a[i]>a[i+1])
 {

int aux=a[i]; a[i]=a[i+1]; a[i+1]=aux;

gata=0;

if(!gata) bule_rec(a,n-1);

int main()

int a[100],n;

is>>n;

for(int i=0;i<n;i++)

is>>a[i];

bule_rec(a,n);

for(int i=0;i<n;i++)

os<<a[i]<<" ";

is.close();

os.close();

return 0;

18. Se citeste un numar natural n si apoi un vector a cu n elemente naturale. Stergeti din vectorul a
toate aparitiile elementului minim

Se vor scrie si folosi functii recursive pentru urmatoarele operatii:

- citirea celor n elemente ale vectorului a

- afisare celor n elemente ale vectorului a

- gasirea elementului minim al vectorului

- stergerea elementului de la o pozitie i dintr-un vector

- stergerea tuturor aparitiilor elementului minim

Exemplu:
date.in

12315618

date.out

23568

(1 este elementul minim si este sters de 3 ori)

#include <fstream>

using namespace std;

ifstream is("date.in");

ofstream os("date.out");

void citire(int a[], int n) // citeste elementele vectorului

if(n>0)

citire(a,n-1);

is>>a[n];

void afisare(int a[], int n) //afiseaza elementele vectorului

if(n>0)

afisare(a,n-1);

os<<a[n]<<" ";

}
}

int minim(int a[],int n) //returneaza minimul din vector

if(n==1) return a[1];

else return min(a[n],minim(a,n-1));

void del(int a[], int &n, int i) //sterge pozitia i

if(i==n) n--;

else

{ a[i]=a[i+1];

del(a,n,i+1);

void delmin(int a[], int &n, int i, int min) //sterge toate aparitiile elementului minim

if(i<=n)

if(a[i]==min)

del(a,n,i);

delmin(a,n,i,min);

else delmin(a,n,i+1,min);

int main()
{

int a[100],n;

is>>n;

citire(a,n);

delmin(a,n,1,minim(a,n));

afisare(a,n);

is.close();

os.close();

return 0;

19. Se citeste un numar natural n. Sa se descompuna numarul n in toate modurile ca suma de doua
numere a si b care au proprietatea ca b este rasturnatul lui a. Se vor scrie si folosi doua functii recursive
pentru:

- calculul rasturnatului

- descompunerea ceruta

Exemplu: numarul 787 se descompune ca 146+641, 245+542 sau 344+443

#include <iostream>

using namespace std;

int rast(int n, int r)

if(n==0) return r;

else return rast(n/10,r*10+n%10);

void desc(int x, int i)

if(i<=x/2)

{
 if(i+rast(i,0)==x) cout<<i<<"+"<<rast(i,0)<<endl;

desc(x,i+1);

int main()

int x;

cin>>x;

desc(x,1);

return 0;

20. Sa se scrie o functie recursiva care numara cate vocale mici are un cuvant transmis ca parametru.

#include<iostream>

using namespace std;

int vocale(char s[20])

{
if(strlen(s)==0) return 0;
else if(strchr("aeiou",s[0])) return 1 + vocale(s+1);
else return vocale(s+1);
}

int main()
{ cout<<vocale("anamaria");
return 0;
}
int main()
{ cout<<vocale("anamaria");
return 0;
}