Procesul recursiv este procesul care, în timpul execuţiei, generează apariţia unor procese identice, aflate în legătură directă cu procesul ce le generează.Un proces poate fi descris printr-un subprogram
În limbajul C++ se pot defini funcții procedurale ( void ) sau operand. Ambele tipuri de funcții se pot autoapela dar în mod diferit. În cazul funcţiilor procedurale, autoapelul se realizează prin apelul funcţiei respective, din interiorul ei iar în cazul funcțiilor operand se utilizează instrucțiunea return:
| void f(int n) { if (n!=0) { cout<<n<<ʹ ʹ; f(n-1); } } int main() { f(5);} Se vor afișa numerele 5 4 3 2 1 |
int f (int n) { if (n!=0) return n+f(n-1);}int main() { cout<<f(5);} Se calculează suma 1+2+3+4+5 |
Într-o funcție recursivă recurența este realizată prin autoapelul funcției. În algoritmul recursiv sunt necesare două elemente:
- formula de recurență (autoapelul)
- o valoare inițială cunoscută (condiția de terminare a apelului).
Fiecare autoapel al funcției duce spre soluția finală care corespunde valorii inițiale cunoscute.
Exemplu: Factorialul unui număr n. Funcția matematică recursivă a acestui proces este:
fact(n)=n,
Funcția recursivă este:
int fact(int n)
{if(n==0)
return 1;
else return n*fact(n-1);
}
unde n == 0 reprezintă condiția de terminare a autoapelului iar return n*fact(n-1) conține autoapelul.
Pentru memorarea parametrilor, subprogramele folosesc zona de memorie numită stivă. La apelul subprogramului se vor depune în stivă, în ordine, parametrii transmişi și se rezervă spaţiu pentru variabilele locale. În cazul în care subprogramul se autoapelează pe un al doilea nivel, se depun din nou parametrii transmişi şi se rezervă un nou spaţiu pentru variabilele locale. În acest exemplu, calculele se efectuează la revenirea din apel. Valorile au fost reţinute în stivă, iar la revenire au fost folosite pentru înmulţire.
| 4! = 4 * 3! | 4! = 4 * 6 = 24 | Rezultat final | ||
| 3! = 3 * 2! | 3! = 3 * 2 = 6 | |||
| 2! = 2 * 1! | 2! = 2 * 1 = 2 | |||
| 1! = 1 * 0! | 1! = 1 * 1 = 1 | |||
| 0! = 1 | ||||
| Valoare cunoscută |
Figura 2.1. Factorialul unui număr n
Regulile pentru construirea unei funcții recursive sunt următoarele:
– Corpul unei funcții recursive cuprinde două elemente :cazul general al soluției care conține operații necesare pentru reducerea dimensiunii problemei, cea mai importantă operație fiind autoapelul. În exemplul funcției fact cazul general al soluției este format din instrucțiunea return n*fact(n-1) și cazul de bază al soluției care conține o operație care rezolvă un caz particular al problemei, în exemplul funcției fact, cazul de bază al soluției este instrucțiunea return 1;
– Într-o funcție recursivă este obligatoriu să existe o condiție de oprire a repetiției exprimată printr-o expresie logică. În exemplul funcției fact , expresia logică este (n= =0). Aceasta expresie logică este folosită pentru a face trecerea de la cazul general la cazul de bază al soluției.
-O funcție recursivă trebuie să asigure condiția de consistență, modificarea parametrilor și sau a variabilelor locale, de la o activare la alta trebuie să asigure condiția de ieșire din recursivitate.
Observații:
-în elaborarea algoritmilor recursivi se aplică raţionamentul că ce se întâmplă la un nivel, se întâmplă la orice alt nivel;
-pentru orice algoritm recursiv există unul iterativ care rezolvă aceeaşi problemă;
-nu întotdeauna alegerea unui algoritm recursiv reprezintă un avantaj.
Exemple de functii recursive:
Suma numerelor naturale <= n
int suma (int n)
{ if(n==0)return 0;
else return suma (n-1) + n; }
int main()
{ int n;
cin>>n;
cout<<suma(n);
return 0;
}
Probleme propuse:
-Determinati produsul numerelor pare mai mici sau egale cu n
-Detrminati media aritmetica a numerelor divizibile cu 3 mai mici sau egale cu n
Suma a n numere citite de la tastatura
int suma (int n)
{int a;
if(n==0)return 0;
else {cin>>a;
return suma (n-1) + a;}
}
int main()
{
int n; cin>>n;
cout<<suma(n);
return 0;
}
Probleme propuse:
-Determinati produsul numerelor cu 2 cifre
-Determinati cate numere impare s-au citit
-Determinati suma numerelor care nu sunt multipli numarului 5
Suma cifrelor unui numar
int suma (int n)
{
if(n==0)return 0;
else
return suma (n/10) + n%10;
}
int main()
{
int n; cin>>n;
cout<<suma(n);
return 0;
}
Probleme propuse:
-Determinati produsul cifrelor mai mari decat 2
-Determinati cate cifre 0 contine numarul n
-Determinati cifra maxima din n
Suma elementelor unui vector
int v[50],n,i;
int vector(int v[50], int n)
{
if(n==0) return 0;
else return v[n-1]+vector(v, n-1);
}
int main()
{
int i;
cin>>n;
for (i=0; i<n; i++)
cin>>v[i];
cout<<vector(v,n);
return 0;
}
Algoritmi si Programare 