[C] Codice ricorsivo deallocazione lista

[felpone]

typedef int itemType;

typedef struct listNode listNode;
typedef listNode *List;
struct listNode {
	itemType item;
	List next;
};







void freeListR(List head){
     if (head==NULL) return;
     freeListR(head->next);
     free(head);     
}

Salve, nella funzione ricorsiva freelistr non riesco a capire come si faccia ad arivare all ultimariga di codice free(head) se appena prima c'è la chiamata ricorsiva...

[MItaly]

La chiamata ricorsiva dealloca tutti i nodi successivi, quindi ritorna, a quel punto viene eseguita la free.
Facciamo un esempio con una lista di tre elementi: chiami freeListR sul primo elemento; head!=NULL, quindi la funzione non esce e richiama sé stessa sull'elemento successivo; accade la stessa cosa per questo elemento e per quello successivo.
Al terzo livello di ricorsione freeListR viene richiamata con NULL (dato che siamo all'ultimo elemento, head->next è NULL), il che fa sì che al quarto livello di ricorsione freeListR ritorni immediatamente. A questo punto viene eseguita la free al terzo livello di ricorsione e la funzione ritorna; idem per il secondo e il primo livello di ricorsione. Quando la "prima chiamata" a freeListR ritorna tutta la lista è stata deallocata.

[Vincenzo1968]

Meglio, comunque, usare la versione iterativa:

void FreeList(List *head)
{
	List *n1 = head, *n2;

	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}