1. Fie ecuaia x2 - Sx + P = 0 cu S, P R si x1, x2 rdcinile ecuaiei.

S se calculeze Sn= x1n x2n , n N.

Cutm relaia de recuren pentru Sn, tiind c x1, respectiv x2 sunt rdcinile ecuaiei date i
deci ndeplinesc relaiile :
x12 Sx1 P 0
x22 Sx2 P 0
nmulim aceste relaii cu x1n 2 i x 2n 2 i adunm relaiile obinute i rezult:
Sn = x1n x2n = S * ( x1n1 x2n1 ) P * ( x1n2 x2n2 ) = S*Sn-1 - P*Sn-2.

Astfel am obinut o relaie de recuren :

S0 = x0 + x0 = 2,
S1 = x1 + x2 = S,
Sn = S*Sn-1 - P*Sn-2, pentru n2.

#include<iostream.h>
using namespace std;
int n;
float s,p,r;
float suma(int n)
{
if(n==0) return 2;
else if(n==1) return s;
else return(s*suma(n-1)-p*suma(n-2));
}
int main(void)
{
cout<<"Introduceti valorile ecuatiei de gradul II "<<endl;
cout<<"Dati s = "; cin>>s;
cout<<"Dati p = "; cin>>p;
cout<<" N = "; cin>>n;
r = suma(n);
cout<<"Valoarea lui S("<<n<<") este "<<r;
}

1
2. S se afle elementul maxim dintr-un vector dat.

Soluia este dat de relaia recuren :

maxim(a1, a2 , . . . ,an) = maxim(an, maxim(a1, a2, . . . , an-1))

#include<iostream.h>
using namespace std;
int a[100],n,i;
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int maxim(int a[],int n)
{
if(n==1) return a[0];
else return max(a[n],maxim(a,n-1));
}
int main(void)
{

clrscr();
cout<<"Introduceti dimensiunea sirului n = ";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]=";
cin>>a[i];
}
cout<<"Elementul maxim din vector este = "<<maxim(a,n);
}

3. Sa se genereze toate submultimile unei multimi.

Se foloseste un vector a care indica selectia elementelor multimii:

a[i]=1 daca elem. b[i] face parte din submultime
a[i]=0,in caz contrar
Pentru generarea submultimilor vom defini functia recursiva submultime, care are un parametru
i ce reprezinta pozitia elementului care se va genera.
In cazul in care s-au generat toate elementele(i=n) se tipareste submultimea generata, in caz
contrar, se trece la generarea elem. urmator(aflat pe pozitia i+1).

2
#include<iostream.h>
using namespace std;

int a[40],b[40],n,i;
void tipar()
{
for(i=1;i<=n;i++)
if(a[i]==1) cout<<b[i]<<" ";
cout<<endl;
}
void submultime(int i)
{
int j;
for(j=0;j<=1;j++)
{
a[i]=j;
if(i==n) tipar();
else submultime(i+1);
}
}
int main(void)
{
cout<<"Dati numarul de elemente n = ";cin>>n;
cout<<"Dati elementele multimii "<<endl;
for(i=1;i<=n;i++) cin>>b[i];
submultime(1);
}

4. Sa se transforme un numar n, dat in baza 10, intr-o alta baza b (2<=b<=10).

#include<iostream.h>
using namespace std;
int n,b;
void baza(int n)
{
if(n<b) cout<<n;
else
{
baza(n/b);
cout<<n%b;
}
}
int main(void)
{
cout<<"Dati numarul in baza 10, n = ";cin>>n;
cout<<"Dati baza in care vreti sa se transforme "; cin>>b;

3
cout<<n<<" in baza "<<b<<" este ";
baza(n);
}

5. Se citeste un numar intreg cu cel mult 255 cifre. Sa se afiseze numarul cu cifrele in ordine
inversa.

#include<iostream.h>
using namespace std;
#include<string.h>
char n[255],i,l;
void invers(int i)
{
if(i<l) invers(i+1);
cout<<n[i];
}
int main(void)
{
cout<<"Dati numarul in n = ";cin>>n;
l=strlen(n);
cout<<"Numarul rasturnat este ";
invers(0);
}

6. Se dau doi vectori x si y cu n componente de tip cifra. Se cere sa se calculeze suma

x[0]^y[0] + x[1]^y[1] + . . . + x[n-1]^y[n-1].
Se vor utiliza doua functii recursive pentru calculul unui numar a la puterea b si respectiv
suma componentelor unui vector.

#include<iostream.h>
using namespace std;

int x[50],y[50],z[50],i,n;
long int putere(int a,int b)
{
long int i,p=1;
for(i=1;i<=b;i++) p*=a;
return p;
}
int suma(int t[50],int i)
{
if(i<n) return(t[i]+suma(t,i+1));
else return 0;
}
int main(void)
{
cout<<"Dati numarul de elemente n = ";cin>>n;

4
 cout<<"Dati elementele primului vector X "<<endl;
for(i=0;i<n;i++) cin>>x[i];
cout<<"Dati elementele celui de-al doilea vector Y "<<endl;
for(i=0;i<n;i++) cin>>y[i];
for(i=0;i<n;i++) z[i]=z[i]+putere(x[i],y[i]);
cout<<" suma este "<<suma(z,1);
}

7. Sa se determine si sa afiseze toate sufixele unui cuvant citit de la tastastura. Se numeste

sufix al unui cuvant, un cuvant format din minim o litera, maxim toate pornind de la sfarsitul
cuvantului.

#include<stdio.h>
#include<string.h>
using namespace std;

char s[50];
int n;
void afisare(char s[],int i)
{
int j;
if (i<=n-1)
{
for(j=i;j<=n-1;j++)
cout<<s[j]);
cout<<endl;
afisare(s,i+1);
}
}
int main()
{
cout<<"Cuvantul=";cin>>s;
n=strlen(s);
afisare(s,0);
}

5
 Probleme propuse spre rezolvare

1. S se ruleze programele prezentate mai sus, urmrind apelurile i valorile parametrilor de

apel.

2. S se scrie un program care s calculeze al n-lea termen din irul lui Fibonacci, care este
definit recursiv astfel:
fib[1]=0;
fib[2]=1;
fib[n]=fib[n-1] + fib[n-2]

3. S se caute o soluie nerecursiv pentru irul lui Fibonacci.

4. S se calculeze funcia Manna-Pnueli, dat de relaia :

| x-1, dac x>=12
f(x)= |
| f(f(x+2)), dac x<12

5. S se scrie un program recursiv care s compare dou iruri de caractere.

6. S scrie un program recursiv care s verifice dac dou iruri de caractere sunt anagrame.
Dou cuvinte sunt anagrame dac conin aceleai litere dar n ordine diferit.
Exemplu: irul DARIAN este anagrama pentru irul ADRIAN.

6
 Subprograme recursive mecanism de execuie
7. Pentru definiia de mai jos a subprogramului f, ce se afieaz ca urmare a apelului f(121,1);?
void f(long n, int i)
{
if(n==0) cout<<i;
if(n%3>0) f(n/3,i+1);
}

8. Pentru definiia alturat a subprogramului f, ce se afieaz ca urmare a apelului f(26);?

void f (int x)
{
if(x>0)
{
cout<<'x';
f(x/3);
cout<<'y';
}
}

9. Pentru subprogramul f definit alturat, ce se afieaz ca urmare a apelului f(15,2);?

void f (int n, int x)
{
if(x>n)
cout<<*;
else
{
f(n,x+4);
cout<<x%10;
}
}

10. Pentru definiia de mai jos a subprogramului f, ce se afieaz ca urmare a apelului f(10);?
void f (int b)
{
if(3<=b)
{
f(b-2);
cout<<*;
}
else cout<<b;
}

7
11. Se consider subprogramul cu definiia alturat. Ce valoare se va afia n urma executrii
instruciuni de mai jos?
cout<<f(12);
int f (int n)
{
int c;
if (n!=0)
{
if (n%2==1)
c=1+f(n/2);
else c=f(n/2);
cout<<n%2;
return c;
}
else return 0;
}
12. Se consider subprogramul cu definiia alturat. Ce se va afia n urma apelului f(12345);?

void f(long int n)

{
if (n!=0)
{
if (n%2==0)
cout<<n%10;
f(n/10);
if (n%2!=0)
cout<<n%10;
}
else cout<<endl;
}

13. Subprogramul recursiv alturat este definit incomplet. nlocuii punctele de suspensie cu o
expresie, astfel nct, n urma apelului, subprogramul f s returneze suma primelor dou cifre ale
numrului primit prin intermediul parametrului x?
Exemplu: n urma apelului f(2318) valoarea returnat este 5.

int f(int x)
{
if (...)
return x%10 + x/10;
else
return f(x/10);
}

8
14. Se consider subprogramul recursiv alturat, definit incomplet. Cu ce valoare trebuie
nlocuite punctele de suspensie, pentru ca funcia s returneze cifra minim a numrului natural
nenul transmis prin intermediul parametrului x?

int Min(int x)
{
int c;
if (x==0) return ...;
else {
c=Min(x/10);
if (c < x%10) return c;
else return x%10;
}
}

15. Se consider subprogramul recursiv alturat, S,definit incomplet.Cu ce expresie pot fi

nlocuite punctele de suspensie astfel nct, n urma apelului S(2), s se afieze 3 caractere * ?

void S(int x)
{
cout<<'*';
if (...) {
cout<<'*';
S(x-1);
}
}

16. Ce afieaz subprogramul F, descris alturat, la apelul F(5);?

void F(int x)
{
cout<<x;
if(x>=3)
F(x-2);
}