RECURSIVITATE
Spunem că o funcţie C este recursivă dacă ea se autoapelează înainte de a se reveni din ea. Funcţia se poate reapela fie direct, fie indirect (prin intermediul altor funcţii).
La fiecare apel al unei funcţii, parametrii şi variabilele locale se alocă pe stivă într-o zonă independentă. De asemenea, orice apel recursiv al unei funcţii va conduce la o revenire din funcţie la instrucţiunea următoare apelului respectiv. La revenirea dintr-o funcţie se realizează curăţarea stivei, adică zona de pe stivă afectată la apel parametrilor şi variabilelor automatice se eliberează.
Un exemplu simplu de funcţie apelata recursiv este funcţia de calcul al factorialului. Putem defini recursiv funcţia factorial astfel:
factorial(n)= 1, dacă n=0
factorial(n)=n*factorial(n-1), dacă n>0
În limbajul C avem :
double factorial (int)
{ if (n= = 0) return 1.0;
else return n*factorial(n-1);
}
Observaţii:
1o. În general, o funcţie recursivă se poate realiza şi nerecursiv, adică fără să se autoapeleze.
2o. De obicei, recursivitatea nu conduce nici la economie de memorie şi nici la execuţia mai rapidă a programelor. Ea permite însă o descriere mai compactă şi mai clară a funcţiilor. Acest lucru rezultă şi din exemplul de mai sus de calcul al factorialului.
3o. În general, funcţiile recursive sunt de preferat pentru procese care se definesc recursiv. Există şi excepţii. De exemplu algoritmul de generare a permutărilor de n obiecte poate fi descris recursiv astfel: având în memorie toate cele (n-1)! permutări, atunci permutările de n obiecte se generează înserând pe n în toate poziţiile posibile ale fiecărei permutări de n-1 obiecte. Dar ne aducem aminte că 10!=3628800 şi capacitatea stivei se depăşeşte repede.
Exemple:
1) Programul determină recursiv cmmdc (algoritmul lui Euclid) a două numere întregi (de tip long):
cmmdc (a,b) = b, dacă a%b =0 (restul împărţirii lui a la b e zero)
cmmdc (a,b) = cmmdc (b,a%b), în caz contrar.
#include <iostream.h>
#include <conio.h>
long cmmdc(long a, long b)
{ if (!(a % b)) return b;
else return cmmdc(b, a % b);
}
void main(void)
{ long x,y;
clrscr();
cout << “dati un numar natural=”;
cin >> x;
cout << “dati alt numar natural=”;
cin >> y;
cout << “cmmdc(” << x << “,” << y << “)=” << cmmdc (x,y);
}
Am folosit funcţiile de intrare / ieşire cin şi cout, imediat se observă modul lor de utilizare.
2) Programul determină recursiv suma unor elemente de tablou unidimensional
a[1]+a[2]+ . . . + a[n]
#include <iostream.h>
#define MAX 100
int a[MAX];
// suma(n)= 0, daca n=0
// suma(n)=suma(n-1) + a[n] daca n>0
int suma(int n)
{ if (!n) return 0;
else return a[n]+suma(n-1);
}
void main(void)
{int n,i;
cout << “dati n= “;
cin >> n;
for (i=1; i<=n; i++)
{ cout << “a[” << i << “]= “;
cin >> a[i];
}
cout << “suma numerelor este ” << suma(n);
}
3) Programul determină recursiv termenul al n-lea din şirul lui Fibonacci definit după cum urmează:
fibonacci[0]=0
fibonacci[1]=1
fibonacci[n]=fibonacci[n-1]+fibonacci[n-2], dacă n>1
#include<iostream.h>
long fibonacci (long n)
{if (!n) return 0;
else if (n==1) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
void main (void)
{ long n;
cout << “dati n = “;
cin >> n;
cout << “fibo(” << n << “) =” << fibonacci (n);
}
4) Programul determina maximul dintr-un vector de numere astfel:
M(n)= a[1] dacă n=1
M(n)= max { M(n-1),a[n] } dacă n>1
#include<iostream.h>
#define MAX(x,y) (x > y ? x : y)
int a[100];
int M(int n)
{ if (n= =1) return a[1];
else return MAX (M(n-1), a[n]);
}
void main(void)
{int n,i;
cout << “dati n=”;
cin >> n;
for (i=1; i<=n; i++)
{ cout << “a[” << i << “]= “;
cin >> a[i];
}
cout << “maximul este ” << M(n);
}
5) Programul afisează un şir de caractere în mod recursiv, caracter cu caracter, considerând că şirul de caractere este format din primul caracter(capul) + restul şirului de caractere (coada).
#include <iostream.h>
#include <conio.h>
#define max 100
char sir [max];
int n;
void afis (int m)
{ if (m = = n+1) return;
else { cout << sir[m];
afis(m+1);
}
}
void main (void)
{int i;
do { cout << “\ndati lungimea sirului =”;
cin >> n;
}
while ( (n< 0) || (n > max));
for(i=1; i<=n; i++)
{ cout << “sir[” << i << “]=”;
cin >> sir[i];
}
afis(1);
getch();
}
6) Programul ce urmează e oarecum asemănător cu exemplul anterior doar că afişează şirul de caractere de la sfârşit spre început.
#include <iostream.h>
#include <conio.h>
#define max 100
char sir [max];
void afis (int m)
{ if (m==0) return;
else { cout << sir[m];
afis(m-1);
}
}
void main (void)
{int n,i;
do {cout << “\ndati lungimea sirului =”), cin >> n;}
while ( (n< 0) || (n > max));
for(i=1; i<=n; i++)
{ cout << “sir[” << i << “]=”;
cin >> sir[i];
}
afis(n);
getch();
}
7) Programul sortează prin metoda quicksort un vector de numere întregi:
#define dim 50
#include <stdio.h>
#include <conio.h>
int x[dim+1],i,n;
void tipsir ()
{ for (i=1; i<=n; i++)
{ printf(“%3d”,x[i]);
if (!(i % 20)) printf (“\n”);
}
}
void quik(int st, int dr)
{int i,j,y;
i=st; j=dr; y=x[i];
do { while ((x[j] >= y) && (i<j)) j – -;
x[i]=x[j];
while ((x[i] <= y) && (i<j)) i++;
x[j]=x[i];
}
while (i != j);
x[i]=y;
if (st < i-1) quik(st,i-1);
if (i+1 < dr) quik(i+1,dr);
x[j]=x[i];
}
void citire (void)
{ int cod = 0;
n = dim+1;
while ( n <= 0 || n > dim || ! cod )
{ printf (“\ndati dim. sir:”);
cod=scanf (“%d”,&n);
}
i = 1;
while (i<=n)
{ printf (“x[%2d]=”,i);
scanf (“%d”, &x[i]);
i++;
}
}
void main(void)
{ clrscr();
citire();
clrscr();
printf (“\n\nsir initial\n”);
tipsir();
quik(1,n);
printf (“\n\nsir sortat\n”);
tipsir();
getche();
}