Recursivitate

Spunem ca o functie C este recursiva daca ea se autoapeleaza inainte de a se reveni din ea. Functia se poate reapela fie direct, fie indirect (prin intermediul altor functii).

La fiecare apel al unei functii, parametrii si variabilele locale se aloca pe stiva intr-o zona independenta. De asemenea, orice apel recursiv al unei functii va conduce la o revenire din functie la instructiunea urmatoare apelului respectiv. La revenirea dintr-o functie se realizeaza curatarea stivei, adica zona de pe stiva afectata la apel parametrilor si variabilelor automatice se elibereaza.

Un exemplu simplu de functie apelata recursiv este functia de calcul al factorialului. Putem defini recursiv functia factorial astfel:

factorial(n)= 1, daca n=0

factorial(n)=n*factorial(n-1), daca n>0

In limbajul C avem :

double factorial (int)

Observatii:

1^o. In general, o functie recursiva se poate realiza si nerecursiv, adica fara sa se autoapeleze.

2^o. De obicei, recursivitatea nu conduce nici la economie de memorie si nici la executia mai rapida a programelor. Ea permite insa o descriere mai compacta si mai clara a functiilor. Acest lucru rezulta si din exemplul de mai sus de calcul al factorialului.

3^o. In general, functiile recursive sunt de preferat pentru procese care se definesc recursiv. Exista si exceptii. De exemplu algoritmul de generare a permutarilor de n obiecte poate fi descris recursiv astfel: avand in memorie toate cele (n-1)! permutari, atunci permutarile de n obiecte se genereaza inserand pe n in toate pozitiile posibile ale fiecarei permutari de n-1 obiecte. Dar ne aducem aminte ca 10!=3628800 si capacitatea stivei se depaseste repede.

Exemple:

Programul determina recursiv cmmdc (algoritmul lui Euclid) a doua numere intregi (de tip long):

cmmdc (a,b) = b,     daca a%b =0 (restul impartirii lui a la b e zero)

cmmdc (a,b) = cmmdc (b,a%b), in caz contrar.

#include <iostream.h>

#include <conio.h>

long cmmdc(long a, long b)

void main(void)

Am folosit functiile de intrare / iesire cin si cout, imediat se observa modul lor de utilizare.

Programul determina 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)

void main(void)

cout << 'suma numerelor este ' << suma(n);

Programul determina recursiv termenul al n-lea din sirul lui Fibonacci definit dupa cum urmeaza:

fibonacci[0]=0

fibonacci[1]=1

fibonacci[n]=fibonacci[n-1]+fibonacci[n-2], daca n>1

#include<iostream.h>

long fibonacci (long n)

void main (void)

Programul determina maximul dintr-un vector de numere astfel:

M(n)= a[1], daca n=1

M(n)= max , daca n>1

#include<iostream.h>

#define MAX(x,y) (x > y ? x : y)

int a[100];

int M(int n)

void main(void)

cout << 'maximul este ' << M(n);

5) Programul afiseaza un sir de caractere in mod recursiv, caracter cu caracter, considerand ca sirul de caractere este format din primul caracter(capul) + restul sirului de caractere (coada).

#include <iostream.h>

#include <conio.h>

#define max 100

char sir [max];

int n;

void afis (int m)

void main (void)

while ( (n< 0) || (n > max));

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

afis(1);

getch();

6) Programul ce urmeaza e oarecum asemanator cu exemplul anterior doar ca afiseaza sirul de caractere de la sfarsit spre inceput.

#include <iostream.h>

#include <conio.h>

#define max 100

char sir [max];

void afis (int m)

void main (void)

while ( (n< 0) || (n > max));

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

afis(n);

getch();

7) Programul sorteaza prin metoda quicksort un vector de numere intregi:

#define dim 50

#include <stdio.h>

#include <conio.h>

int x[dim+1],i,n;

void tipsir ()

void quik(int st, int dr)

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)

i = 1;

while (i<=n)

void main(void)