FUNCTII RECURSIVE

FUNCTII recursive

1. SCOPUL LUCRARII

In aceasta lucrare se va studia recursivitatea.

2. BREVIAR TEORETIC

2.1. Functii recursive

O functie recursiva este o functie care se apeleaza pe ea insasi. La fiecare apel al functiei, parametrii functiei si variabilele locale ei (cele care nu sunt statice) sunt alocate pe stiva (la fiecare apel in zone diferite). La revenirea din apelul functiei recursive, are loc descarcarea stivei.

Functiile recursive au avantajul ca permit o exprimare usoara, clara, a relatiilor recurente. Dezavantajul lor este ca determina marirea timpului de executie a programului, fata de varianta nerecursiva (datorita timpului consumat cu incarcarea / descarcarea stivei ).

3. DESFASURAREA LUCRARII

Se vor edita si apoi executa programele descrise in continuare.

Programul nr. 1

Sa se scrie functia factorial, implementandu-se recursiv urmatoarea definitie:

1! =1

n!=n*(n-1)! , daca n>1

Sursa programului:

#include <stdio.h>

#include <conio.h>

long int factorial (int n);

void main(void)

long int factorial (int n)

Programul nr. 2

Sa se implementeze o functie recursiva care sa calculeze termenul de rang n din sirul lui Fibonacci.

Sirul Fibonacci se defineste astfel:

a₀=1

a₁=1

a_n=a_n-1 + a_n-2 daca n>1

Sursa programului:

#include <stdio.h>

#include <conio.h>

int fib(int n);

void main (void)

int fib (int n)

Programul nr. 3

Se citeste un numar natural de la tastatura. Sa se afiseze daca este termen in sirul lui Fibonacci sau nu.

#include<stdio.h>

#include<conio.h>

int fib(int n);

void main(void)

if(termenFib>nr)

n++;}

getch();

int fib (int n)

Programul nr. 4

Sa se scrie o functie recursiva ce calculeaza suma elementelor unui vector.

Sursa programului:

#include <stdio.h>

#include <conio.h>

#define N 5 //numarul de elemente din vector

int suma(int A[], int n);

void main()

int S;//suma

clrscr();

S=suma(A,N);

printf('S=%d',S);

int suma(int A[], int n)

Programul nr. 5

Sa se scrie o functie recursiva ce stabileste daca un numar x este prezent intr-un vector A de N componente.

Sursa programului:

#include <stdio.h>

#include <conio.h>

#define N 5//numarul de componente din A

int estePrezent(int x, int A[], int n);

void main()

int x=3;

clrscr();

if(estePrezent(x,A,N)==1)printf('Este.');

else printf('Nu este.');

int estePrezent(int x, int A[], int n)

else

Programul nr. 6

Sa se scrie o functie recursiva ce compara doi vectori de aceeasi dimensiune. Returneaza 1, daca cei doi vectori sunt egali, si 0, in caz contrar.

Sursa programului:

#include <stdio.h>

#include <conio.h>

#define N 4

int compara(int A[], int B[], int n);

void main()

int B[N]=;

clrscr();

if(compara(A,B,N)==1)printf('Sunt egali.');

else printf('Nu sunt egali.');

int compara(int A[], int B[], int n)

else

Programul nr. 7

Sa se scrie o functie recursiva ce calculeaza si returneaza maximul dintr-un vector.

Sursa programului:

#include <stdio.h>

#include <conio.h>

#define N 5 //numarul de elemente din vector

int maxim(int A[], int n);

void main()

int max;

clrscr();

max=maxim(A,N);

printf('maxim=%d',max);

int maxim(int A[], int n)

Programul nr. 8

Sa se sorteze in ordine crescatoare, folosind metoda selectiei maximului, un vector de N componente, numere intregi.

Se va proceda astfel: mai intai calculam maximul dintre cele N numere. Acesta se va muta de pe pozitia lui, pe ultima pozitie (pozitia N-1), comutand cele doua numere intre ele. Apoi, se calculeaza maximul dintre primele N-1 numere, si acesta se comuta cu numarul de pe penultima pozitie (pozitia N-2), s.a.m.d.

Exemplu:

N=5

A=

Pasul 1: maxim1=17. Dupa comutare: A=

Pasul 2: maxim2=9. Dupa comutare: A=

Pasul 3: maxim3=5. Dupa comutare: A=

Pasul 4: maxim4=4. Dupa comutare: A=

Sursa programului:

#include <stdio.h>

#include <conio.h>

#define N 5 //numarul de elemente din vector

void ordonare(int A[], int dim);//prototipul functiei recursive.

//functia getPozMax() afla pozitia maximului, intr-un vector

//ce are dim componente:

int getPozMax(int A[], int dim);

void main()

int i;

clrscr();

ordonare(A,N);

//Afisare vector ordonat:

for(i=0;i<N;i++)

printf('n%d',A[i]);

void ordonare(int A[], int dim)

int getPozMax(int A[], int dim)

Programul nr. 9

Se dau trei tije notate cu 'I' (tija initiala), 'M' (tija de manevra) si 'F' (tija finala). Pe tija 'I' se afla N discuri, de diametre diferite, asezate in ordinea descrescatoare a diametrelor (cel mai mare se afla la baza). Acestea trebuie mutate pe tija finala 'F', folosind eventual, pentru manevra, tija intermediara (de manevra) 'M'. O mutare consta din luarea unui disc din varful unui turn si asezarea sa in varful altui turn. Nu se poate aseza insa, un disc de diametru mai mare, peste un disc de diametru mai mic.

Aceasta problema este cunoscuta sub numele de "problema turnurilor din Hanoi".

Algoritmul este explicat in comentariile programului.

Sursa programului:

#include <conio.h>

#include <stdio.h>

#define N 3 //numarul de discuri

void Hanoi(char tI, char tF, char tM, int n);

//tI: tija initiala (tija de unde se iau discurile ce trebuie mutate)

//tF: tija finala (tija unde se muta toate discurile de pe tija initiala)

//tM: tija de manevra (tija intermediara)

void main()

void Hanoi(char tI, char tF, char tM, int n)

//Cazul cand sunt mai multe discuri (n>1):

//La inceput, se muta n-1 discuri de pe tija tI, pe tija tM, folosind

//ca tija de manevra tija tF:

Hanoi(tI, tM, tF, n - 1);

//ultimul disc, ramas la baza tijei initiale tI, se muta direct pe tija

//finala tF, care este libera:

printf('%c -> %cn', tI, tF);

//cele n-1 discuri de pe tija tM, se muta pe tija tF, folosind ca tija

//de manevra tija tI (tI era libera):

Hanoi(tM, tF, tI, n - 1);

4. PROBLEME PROPUSE

1. Sa se scrie o functie recursiva care calculeaza produsul scalar a doi vectori de aceeasi dimensiune.

2. Sa se scrie o functie recursiva care returneaza indexul maximului dintr-un vector.

Sa se scrie o functie recursiva ce calculeaza suma 1³+2³+3³++n³, unde n este un numar natural citit de la tastatura.

4. Sa se scrie o functie recursiva care returneaza produsul elementelor unui vector.

5. Se citeste un numar natural N. Sa se copieze primii N termeni din sirul lui Fibonacci intr-un vector.