recursivitate [Algoritmi si Tehnici de Programare] Introducere in Recursivitate (1)

[NOT a MERCEDES]

** Iterativitate vs Recursivitate ** 

Algoritmii , in general , pot fi implementati iterativ sau recursiv . Astfel ca , intr-o abordare iterativa folosim bucle (loopuri) iar in cea recursiva , folosim apelul repetitiv a unei functii , pentru repetarea unor parti din cod . Totusi , avem pe de o parte avantaje si dezavantaje , pentru fiecare tip de abordare. Astfel ca : 

• Pe parte de eficienta & putere , iterativitatea este mult mai avantajoasa in defavoarea recursivitatii . In sensul ca , apelul repetat al functiilor pot consuma din memoria stack si pot ingreuna programul sau chiar , sa producem un blocaj de tip "stackoverflow" . (Supraincarcarea memoriei stack) . Plus , pe partea de iterativitate , avem un control mai bun pe numarul de repetari . 
• Pe de alta parte , recursivitatea ofera posibilitatea de a construi un cod elegant , usor de mentinut . (Mai ales , daca discutam de o problema de natura recursiva !!) . 

 

** Exemple in C ** 

Sa presupunem ca vrem sa aflam suma numerelor introduse la tastura . 

Abordare Iterativa 

#include <stdio.h>
#include <stdlib.h> // Pentru malloc & free


int insertArray(int** arr) // RETURNAM LUNGIMEA COLECTIEI 
{
	*arr = (int*)malloc(sizeof(int));  // Alocam colectie doar pentru un numar (MOMENTAN) 

	char yesOrNo = 'n';
	int bufferArr = 1;

	do {

		if (yesOrNo == 'y')
		{
			bufferArr++; // Marim lungimea colectiei cu +1 element
			*arr = (int*)realloc(*arr, sizeof(int) * bufferArr); // Mai alocam spatiu pentru un numar
		}
	

		printf("Dati-mi un numar : ");
		scanf_s("%d", &(*arr)[bufferArr-1]); // Inseram un nou element in colectie de la tastatura

		printf("Continuam [y/n] ?");
		scanf_s(" %c", &yesOrNo, 1);  // Daca yesOrNo = y (continuam) altfel iesim din functie 

	} while (yesOrNo != 'n'); // Continuam bucla atat cat yesOrNo e DIFERIT DE 'n'

	return bufferArr;
}


int sumArray(int arr[],int bufferArr)
{
	int sum = 0; // Initializam cu 0 

	for (int i = 0; i < bufferArr; i++) // Parcurgem toata colectia 
	{
		sum += arr[i]; // Insumam toate elementele colectiei 
	}

	return sum;
}

int main()
{
	
	int* a = NULL;

	int bufferArr = insertArray(&a); // Trimitem pointerul a prin adresa (VOM MODIFICA STRUCTRURA ACESTUIA IN FUNCTIE ) si 
	// ++ Vom returna lungimea finala in bufferArr


	// Afisam suma colectiei 

	printf("\n INSUMAND TOATE VALORILE COLECTIEI VOM AVEA CA REZULTAT : %d ", sumArray(a,bufferArr));

		// Eliberam Memoria Ocupata de Array (Sa prevenim Memory Leak)

		free(a);  // Eliberam Colectia in sine 
		a = NULL; // Setam NULL Pointer 


	return 0;
}

 Nota ** : In aceasta abordare , se pot observa in ambele functii , utilizarea buclelor (do-while si for) pentru inserarea , traversarea si accesarea membriilor din colectie !! 

Abordare Recursiva : 

Subprogramul de introducere a numerelor in colectie : 

int insertArray(int** arr) // RETURNAM LUNGIMEA COLECTIEI 
{
	// AM ALOCAT IN AFARA FUNCTIEI +1 element ca tot acest va deveni repetitiv 

	char yesOrNo;

   static int index = 1; // STATIC sa retinem indexu intre apelurile recursive a functiei 
	
	printf("Dati-mi un numar : ");
	scanf_s("%d",&(*arr)[index-1]); // Inseram un nou element in colectie de la tastatura


	printf("Continuam[y/n] ?");
	scanf_s(" %c", &yesOrNo,1); // Primim confirmarea de la utilizare de a continua sau nu inserarea 

	if (yesOrNo == 'n') // Daca nu continuam inserarea 
	{ 
		 return 1; // Oprim algoritmul (1 si nu 0 deoarece luam in calcul si primul element al listei )
	}

	else {
		index++;  // Indexu se mareste cu un element 
		*arr = realloc(*arr, index * sizeof(int)); // Realocam inca o zona de memorie 
		return 1 + insertArray(arr);  // Apelam din nou functia de inserare pentru noul element (++ adaugam un nou elemnt )
	}
	
}

Subprogramul de insumare a elementelor din colectie :

int sumArray(int arr[],int bufferArr)
{
	if (bufferArr <= 0) // Daca indexu ajunge la 0 
	{
		return 0; // returnam 0 in suma 
	}

	else
	{
		int sum = sumArray(arr, bufferArr - 1) + arr[bufferArr - 1]; // Colectia se INSUMEAZA CU APELUL REPETITIV
		  // al functiei ==> arr[bufferArr-1] + arr[bufferArr-2] + arr[bufferArr-3] + ... + arr[0]

		/*
		* 
		*    De exemplu daca avem arr = {5,3,4,5,2 } & Lungimea Colectiei : 5 
		
		    sum = 2 + {5,3,4,5} ;  bufferArr =  5 ;
			sum = 2 + 5 + {5,3,4} ;  bufferArr = 4 ; 
			sum = 7 + 4 + {5,3} ; bufferArr = 3 ; 
			sum = 11 + 3 + {5} ; bufferArr = 2 ; 
			sum = 14 + 5  ; bufferArr = 1 ; 
			sum = 19 + 0 ; // BufferArr = 0 ==> Se incheie algoritmul 

			sum = 19 ; 

		*/

		return sum;
	}
}

 Functia principala cu apelurile la functiile respective : 

#include <stdio.h>
#include <stdlib.h> // Pentru realloc ,  malloc & free

int main()
{
	int* a = (int*)malloc(sizeof(int)); // Alocam o zona de memorie int

	int bufferArr = insertArray(&a);// Trimitem pointerul a prin adresa (VOM MODIFICA STRUCTRURA ACESTUIA IN FUNCTIE ) si 
	// ++ Vom returna lungimea finala in bufferArr

	printf("\n INSUMAND TOATE VALORILE COLECTIEI VOM AVEA CA REZULTAT : %d ", sumArray(a,bufferArr));

		// Eliberam Memoria Ocupata de Array (Sa prevenim Memory Leak)

		free(a);  // Eliberam Colectia in sine 
		a = NULL; // Setam NULL Pointer 

	return 0;
}

NOTA 1 ** : Operatiunile de inserare , parcurgere si accesare , din cadrul colectiei , sunt efectuate prin apelurile repetitive/recursive a functiei .

NOTA 2 ** : Apelurile recursive trebuie sa se faca intr-un mod controlat (Prin if-else) , altfel pot genera erori sau repetari , la infinit , al functiei . (Vom vedea in tutorialele ce urmeaza !!)