Functii recursive
O functie recursiva este o functie care se autoapeleaza, adica, cel putin una dintre instructiunile compoenete ale sale reprezinta apelul
aceleiasi functii, dar, cu o alta iteratie. Iteratia functiei este reprezentata de valoarea curenta a parametrului/prametrilor functiei.
Exemplu:
int suma (int x)
{
if (x==0)
return x;
else
return x+suma(x-1);
}
Explicatii:
- Corpul functiei suma contine apelul aceleiasi functii pe o iteratie inferioara: suma(x-1). Valoarea curenta a rezultatului
functiei depinde de valoarea anterioara a acestuia.
- Corpul functiei contine conditia de iesire din recursivitate: if (x==1). Rezultatul apelului functiei este conditionat de valoarea iteratiei functiei.
Pentru valoarea minima a iteratiei (x==1) se returneaza o valoare fixa (x), iar pentru restul iteratiilor se returneaza o valoare calculata, plecand de la
valoarea returnata de prima iteratie (x+suma(x-1)).
Reguli generale pentru utilizarea functiilor recursive
- Corpul unei functii recursive contine:
- valoarea de baza, de la care se pleaca in construirea solutiei;
- formula generala, dupa care se calculeaza valoarea functiei la fiecare iteratie; La acest nivel vom intalni autoapelul functiei recursive.
- conditia de iesire din recursivitate - in absenta acesteia, functia riscand sa intre intr-o bucla infinita
- Functiile recursive sunt functii care se autoapeleaza, in felul acesta creindu-se o structura repetitiva (atentie, a nu se confunda cu
structurile repetitive descrise in capitolele anterioare:
for, while, do..while).
- Functiile recursive trebuie sa aiba indeplinita conditia de consistenta. Conditia de consistenta presupune ca prelucrarea parametrilor locali ai functiei
recursive, conduc catre valoarea de baza, de la care se pleaca in construirea solutiei.
Exemplul 1: Sa se calculeze suma primelor n numere naturale (n va fi citit de la tastatura).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
using namespace std;
int n;
int suma (int x)
{
int ret;
if (x==0)
ret=x;
else
ret=x+suma(x-1);
cout<<ret<<endl;
return ret;
}
int main()
{
cout<<"n=";cin>>n;
int s=suma(n);
cout<<"Suma numerelor "<<n<<" numere naturale este: "<<s;
}
|
|
|
n=4
0
1
3
4
10
Suma primelor 4 numere naturale este: 10
|
Explicatii:
- Metoda:
- se pleaca de la solutia matematica - pentru n=4 avem:
- suma(4)=4+suma(3)
- suma(3)=3+suma(2)
- suma(2)=2+suma(1)
- suma(1)=1+suma(0)
- suma(0)=0
- recursiv (de la valoarea de baza - suma(0) - catre ultima valoare - suma(4)), vom calcula suma finala :
- suma(0)=0
- suma(1)=1+suma(0)=1+0=1
- suma(2)=2+suma(1)=2+1=3
- suma(3)=3+suma(2)=3+3=6
- suma(4)=4+suma(3)=4+6=10
- In program:
- se citeste variabila n
- se apeleaza functia suma(n) si se atribuie variabilei s;
- functia suma contine:
- declararea unei variabile locale ret care va returna valoarea functiei catre programul/functia apelanta - functia main;
- valoarea de baza, de la care se pleaca in construirea solutiei: 0;
- formula generala, dupa care se calculeaza valoarea functiei la fiecare iteratie: x+suma(x-1);
- conditia de iesire din recurenta: x==0;
- mod de lucru:
- parametrul formal x preia valoarea parametrului efectiv n: n=4 => x=4
- se testeaza valoarea lui x
- deoarece valoarea lui x este 4, deci x!=0 se merge pe varianta else a conditiei: ret=x+suma(x-1); ret va avea deci valoarea:
4+suma(x-1) => autoapel al functiei suma dar pentru iteratia x=x-1=3
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 3, deci x!=0 se merge pe varianta else a conditiei: ret=x+suma(x-1); ret va avea deci valoarea:
4 (din iteratia anterioara) + 3 + suma(x-1) => autoapel al functiei suma dar pentru iteratia x=x-1=2
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 2, deci x!=0 se merge pe varianta else a conditiei: ret=x+suma(x-1); ret va avea deci valoarea:
4 + 3 (din iteratiile anterioare) + 2 + suma(x-1) => autoapel al functiei suma dar pentru iteratia x=x-1=1
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 1, deci x!=0 se merge pe varianta else a conditiei: ret=x+suma(x-1); ret va avea deci valoarea:
4 + 3 + 2 (din iteratiile anterioare) + 1 + suma(x-1) => autoapel al functiei suma dar pentru iteratia x=x-1=0
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 0, deci x==0 se merge pe varianta adevarata a conditiei: ret=x=0; aceasta reprezinta
valoarea de baza: suma(0)=0, de la care se pleaca in construirea solutiei
- din acest punct se incepe, recursiv, construirea solutiei, conform formulelor de la punctul 1.2 :
- valoarea de baza:suma(0) se transmite functiei pe iteratia curenta:
suma(1)=1+suma(0)=1+0=1
- valoarea functiei pe iteratia anterioara: suma(1) se transmite functiei pe iteratia curenta:
suma(2)=2+suma(1)=2+1=3
- valoarea functiei pe iteratia anterioara: suma(2) se transmite functiei pe iteratia curenta:
suma(3)=3+suma(2)=3+3=6
- valoarea functiei pe iteratia anterioara: suma(3) se transmite functiei pe iteratia curenta:
suma(4)=4+suma(3)=4+6=10
- Valoarea 10 a functiei suma (preluata din variabila returnata: ret), va fi transmisa functiei main prin intermediul apelului functei
suma(n) si va fi staocata in variabila s: s=suma(n);
Exemplul 2: Sa se calculeze valoarea lui n factorial (n!) - n va fi citit de la tastatura.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
using namespace std;
int n;
int nfact (int x)
{
int ret;
if (x==1)
ret=1;
else
ret=x*nfact(x-1);
cout<<ret<<endl;
return ret;
}
int main()
{
cout<<"n=";cin>>n;
int nf=nfact(n);
cout<<n<<"!="<<nf;
}
|
|
|
n=4
1
2
6
24
4!=24
|
Explicatii:
- Metoda:
- se pleaca de la solutia matematica - pentru n=4 avem:
- nfact(4)=4+nfact(3)
- nfact(3)=3+nfact(2)
- nfact(2)=2+nfact(1)
- nfact(1)=1+nfact(0)
- nfact(0)=0
- recursiv (de la valoarea de baza - nfact(0) - catre ultima valoare - nfact(4)), vom calcula valoarea finala :
- nfact(0)=0
- nfact(1)=1+nfact(0)=1+0=1
- nfact(2)=2+nfact(1)=2+1=3
- nfact(3)=3+nfact(2)=3+3=6
- nfact(4)=4+nfact(3)=4+6=10
- In program:
- se citeste variabila n
- se apeleaza functia nfact(n) si se atribuie variabilei s;
- functia nfact contine:
- declararea unei variabile locale ret care va returna valoarea functiei catre programul/functia apelanta - functia main;
- valoarea de baza, de la care se pleaca in construirea solutiei: 1;
- formula generala, dupa care se calculeaza valoarea functiei la fiecare iteratie: x+nfact(x-1);
- conditia de iesire din recurenta: x==1;
- mod de lucru:
- parametrul formal x preia valoarea parametrului efectiv n: n=4 => x=4
- se testeaza valoarea lui x
- deoarece valoarea lui x este 4, deci x!=1 se merge pe varianta else a conditiei: ret=x*nfact(x-1); ret va avea deci valoarea:
4*nfact(x-1) => autoapel al functiei nfact dar pentru iteratia x=x-1=3
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 3, deci x!=1 se merge pe varianta else a conditiei: ret=x*nfact(x-1); ret va avea deci valoarea:
4 (din iteratia anterioara) * 3 * nfact(x-1) => autoapel al functiei nfact dar pentru iteratia x=x-1=2
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 2, deci x!=1 se merge pe varianta else a conditiei: ret=x*nfact(x-1); ret va avea deci valoarea:
4 * 3 (din iteratiile anterioare) * 2 * nfact(x-1) => autoapel al functiei nfact dar pentru iteratia x=x-1=1
- se retesteaza valoarea lui x
- deoarece valoarea lui x este 1, deci x==1 se merge pe varianta adevarata a conditiei: ret=x=1; aceasta reprezinta
valoarea de baza - nfact(1)=1 - de la care se pleaca in construirea solutiei
- din acest punct se incepe, recursiv, construirea solutiei, conform formulelor de la punctul 1.2 :
- valoarea de baza - nfact(1) - se transmite functiei pe iteratia curenta:
nfact(2)=2*nfact(1)=2*1=2
- valoarea functiei pe iteratia anterioara nfact(2) se transmite functiei pe iteratia curenta:
nfact(3)=3*nfact(2)=3*2=6
- valoarea functiei pe iteratia anterioara: nfact(3) se transmite functiei pe iteratia curenta:
nfact(4)=4*nfact(3)=4*6=24
- Valoarea 24 a functiei nfact (preluata din variabila returnata: ret), va fi transmisa programului apelant (functiei main)
prin intermediul apelului functei nfact(n) si va fi staocata in variabila nf: nf=nfact(n);
