RECURSIVITATE

RECURSIVITATE

Spunem ca o functie C este recursiva daca ea se autoapeleaza înainte 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 într-o zona independenta. De asemenea, orice apel recursiv al unei functii va conduce la o revenire din functie la instruc&# 757f58h 355;iunea 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

În limbajul C avem :

double factorial (int)

Observatii:

1^o. În 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 însa o descriere mai compacta si mai clara a functiilor. Acest lucru rezulta si din exemplul de mai sus de calcul al factorialului.

3^o. În 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: având în memorie toate cele (n-1)! permutari, atunci permutarile de n obiecte se genereaza înserând pe n în 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 întregi (de tip long):

cmmdc (a,b) = b, daca a%b =0 (restul împartirii 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)

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 în mod recursiv, caracter cu caracter, considerând 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 sfârsit spre început.

#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 întregi:

#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)