Recursivitate

Este mecanismul de autoaparare al unuio subprogram. O functie sau un subprogram are intotdeauna un pas de oprire al recursivitatii si un pas de continuare de autoapel.

Un subprogram recursive, la fel ca un subprogram normal, foloseste o zona de memorie numita stiva in care se pastreaza adresa de revenire din functie, parametrii formali si variabilele locale.

Formule de implementare

1) Functie

Int x; Int f(int i)

{if(x>=12) return x-1;

Else return f(f(x+2));}

Int main()

{cin>>x; cout<<f(x);}

2) Cmmdc

Int a,b; int cmmdc(int a,int b)

{if(a==b) return a;

Else if(a>b) return cmmdc(a-b;b);

Else return cmmdc(a;b-a);}

Int main()

{cin>>a>>b; cout<<cmmdc(a,b);}

3) Suma si produs

Int n; int suma(int n);

If(n==0) return 0; else return n%10+suma(n/10);}

Int prod(int n)

{if(n==0) return 1; else return n%10*prod(n/10);}

int main()

{cin>>n; cout<<”suma cifrelor”<<suma(n)<<endl;

cout<<”produsul cifrelor”<<prod(n);}

Aplicatii

1) Sa se afle cmmdc a n numere

int n,v[100],I,dc;

int cmmdc(int a,int b)

{if(b!=0) return cmmdc(b,a%b);

else return a;}

int main()

{cin>>n; for(i=1;i<=n;i++) cin>>v[i];

d=v[i]; for(i=2;i<=n;i++) dc=cmmdc(dc,v[i]);

cout<<dc;

2) Sa se afle suma/produsul cifelor pentru n numere

int n,v[100],I;

int suma(int n) {if(n==0) return 0;

else return n%10+suma(n/10);}

int prod(int n) {if(n==0) return 1;

else return n%10*prod(n/10);}

int main()

{cin>>n;

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

{cin>>v[i];

cout<<”suma”<<suma(v[i])<<” produs”<<prod(v[i])<<endl;}

Recursivitatea pe vectori

Se da un vector v cu n elemente intregi. Sa se afle:

a) suma elementelor

b) produsul elementelor pare

c) cate nr 3

d) sa se afiseze elem care au ultima cifra 4

e) cate elemente impare sunt

f) produsul elementelor div cu 5

int n,v[100];

a)int suma(int i)

{if(i>=n) return 0;

else return v[i]+suma(i+1);}

b)int produs(int i)

{if(i>n) return 1;

else if(v[i]%2==0) return v[i]*produs(i+1);

else return produs(i+1);}

c)int cate(int i)

{if(i>n) return 0;

else if (v[i]%3==0) return 1+cate(i+1);

else return 0+cate(i+1);}

d)void afis(int i);

{if(i>n);

else if(v[i]%10==4) cout<<v[i]<<” “;

afis(i+1);}}

e)int cate2(int i)

{if(i>n) return 0;

else if(v[i]%2==1) return 1+cate2(i+1);

else return 0+cate2(i+1);}

f)int produs2(int i)

{if(i>n) return 1;

else if(v[i]%5==0) return v[i]*produs2(i+1);

else return produs(i+1);

int main()

{cin>>n; int I; for(i+1;I<=n;i++) cin>>v[i];

cout<<suma(1)<<produs(1)<<cate(1)<<afis(1)<<cate2(1)<<produs2(1)<<endl;

Recursivitate ape cifrele unui numar

Se da un numar n. Sa se afle:

a) suma cifrelor

b) suma cifrelor pare

c) produsul cifrelor impare

d) cate cifre 3 sunt in n

e) afiseze cifrele<=5

f) suma cifrelor divizibile cu 3

int n;

a)int suma1(int n)

{if(n==0) return 0;

else return n%10+suma1(n/10);}

b) int suma2(int n)

{if(n==o) return 0;

else if(n%10%2==0) return n%10+suma2(n/10);

else return suma2(n/10);}

c)int produs(int n) {if(n==0) return 1;

else if(n%10%2==1) return n%10*produs(n/10);}

else return produs(n/10);}

d)int cate(int n)

{if(n==0) return 0; else if(n%10==3) return 1_cate(n/10);

else return cate(n/10);}

e) void afis(int n)

{if(n==0); else if(n%10<5) cout<<n%10; afis(n/10);}

f)int suma3(int n)

if(n==0) return 0; else if(v[i]%3==0) return n%10+suma(n/10); else return suma(n/10);}

int main()

{cin>>n;

cout<<suma1(n)<<suma2(n)<<produs(n)<<” “<<cate(n)<<” “<<suma3(n)<<” “; afis();}

Recursivitate cu nr prime

Se da n. Sa se verifice daca e prim.

int n;

int prim(int n,int i)

{if(i==n) return 1;

else if(n%i==0) return 0;

else return prim(n,i+1);}

int main(){cin>>n; if(prim(n,2)==1) cout<<”prim”;

else cout<<”nu e prim”;}

Recursivitatea la matrici

1) Se da o matrice a(m,n) citita recursiv. Se cere:

a) sa se afiseze matricea

b) sa se afle suma elem

c) sa se afle prod elem

int m,n,a[100][100];

void citire(int i,int j)

{if(i<=m) if(j<=n){cin>>a[i][j]; citire(i+1,j);}

else citire(i+1,1);}

void afisare(int I,int j)

{if(i<=m) if(j<=n){cout<<a[i][j]<<” ”; afisare(i,j)}

else {cout<<endl; afisare(i+1,1)}

int suma(int i,int j) {if(i<=m) if(j<=n) return a[i][j]+suma(1,j+1);

else return suma(i+1,1);

else return 0;

int produs(int i, int j) {if(i<=m) if(j<=n) return a[i][j]*produs(1,j+1);

else return produs(i+1,1);else return 0;

int main()

{cin>>m>>n; citire(1,1); afisare(1,1); cout<<suma(1,1)<<” “<<produs(1,1);}

2) Se da o matrice a(m,n). Sa se afle suma el pare de pe fiecare linie si cate el positive pe fiecare coloana.

int m,n,a[100][100];

void citire(int i,int j)

{if(i<=m) if(j<=n){cin>>a[i][j]; citire(i+1,j);}

else citire(i+1,1);}

int sumal(int I,int k) {if(k<=n) return a[i][k]+sumal(I,k+1); else return 0;

int prodcol(int k,int j) {if(k<=m) return a[k][j]*prodcol(k+1,j);

else return 1;} void return 1;}

void parclin()

{if(i<=m){cout<<”linia”<<i<<”are suma”<<sumal(I,1)<<endl; parclin(i+1;}}

void prodcol()

{if(j<=n) cout<<”col”<<j<<”are prod”<<prodcol(I,j)<<endl;}

int main()

{cin>>m>>n; citire(1,1);

parclin();

parcol();}

Operatii cu matrici patratice

1) Diagonala principala

Sa se afle suma elementelor de pe, de sub si de deasupra diagonalei principale.

int n,a[100][100];

void citire(int i,int j)

{if(i<=n) if(j<=n){cin>>a[i][j]; citire(i+1,j);}

else citire(i+1,1);}

int suma1dp(int i)

{if(i<=n) return a[i][j]+suma1dp(i+1);

else return 0;}

int suma2dp(int i,int j)

{if(i<=n)

if(j<=i-1) return a[i][j]+suma2dp(I;j+1);

else return suma2dp(i+1,1);

else return 0;}

int suma3dp(int i,int j)

{if(i<=n-1)

if(j<=n) return a[i][j]+suma3dp(I,j+1);

else return suma3dp(i+1,i+2);

else return 0;}

int main()

{cin>>n; citire(1,1);

cout<<”suma pe dp”<<suma1dp(1);

cout<<”suma de sub dp”<<suma2dp(2,1);

cout<<suma de deasupra dp”<<suma3dp(1,2);}

2) Diagonala secundara

Sa se calculeze suma de pe, de sub si de deasupra diagonalei secundare.

int m,n,a[100][100];

void citire(int i,int j)

{if(i<=m) if(j<=n){cin>>a[i][j]; citire(i+1,j);}

else citire(i+1,1);}

int suma1ds(int i)

{if(i<=n) return a[i][n-i+1]+suma1ds(i+1);

else return 0;}

int suma2ds(int i,int j)

{if(i<=n)

if(j<=i-1) return a[i][j]+suma2ds(I;j+1);

else return suma2ds(i+1,n-1+1);

else return 0;}

int suma3ds(int i,int j)

{if(i<=n-1)

if(j<=n-1) return a[i][j]+suma3ds(I,j+1);

else return suma3ds(i+1,1);

else return 0;}

int main()

{cin>>n; citire(1,1);

cout<<”suma pe ds”<<suma1ds(1);

cout<<”suma de sub ds”<<suma2ds(2,1);

cout<<suma de deasupra ds”<<suma3ds(1,1);}