Funzione ricorsiva in c

[mic85rm]

Scrivere una funzione in c,sia in versione iterativa che ricorsiva,che conta le occorrenze di un valore intero all'interno di una lista di variabili strutturate di tipo




struct item{
int val;
struct item *next;
}

a partire dall'indirizzo del suo primo elemento.

La mia soluzione iterativa è questa:


int conta_lista(struct item *p,int valore)
{
int conta=0;
/* ciclo di scansione */
while(p != NULL)
{
if(p->val==valore){conta++;} //verifico se il valore della lista è
//è uguale a quello che voglio contare
p = p->next; // scorre di un elemento
}
return conta;
}



qualcuno ha qualche idea su come renderla ricorsiva?

[oNaSsIs]

Prova a pensare a queste due cose:

qual è la condizione di arresto
cosa devi fare ad ogni chiamata prima di dover richiamare la funzione

[banryu79]

Per renderla ricorsiva, oltre ai due parametri presenti nella versione iterativa, è neccessario un argomento in più: il contatore delle occorrenze trovate (che nella versione iterativa è una variabile locale)

La funzione 'conta_lista' ricorsiva, compie tre 'passi' nel suo corpo:
1) controlla se siamo arrivati al 'caso base' (cioè se la ricorsione è terminata) ovvero se il puntatore alla struttura vale NULL, nel qual caso ritorna il controllo al chiamante;
2) esegue la sua funzionalità, ovvero controlla se il valore del campo val è uguale a quello cercato e in tal caso incrementa il contatore;
3) infine esegue la chiamata ricorsiva: ovvero incrementa il valore del puntatore alla struct in modo che punti all'elemento successivo e richiama se stessa passando i tre argomenti.

Ti è chiaro il ragionamento?

[wingman87]

Un altro modo è, senza il parametro "conta", restituire 1 + la chiamata ricorsiva se l'elemento corrente è quello cercato altrimenti 0 + la chiamata ricorsiva

[banryu79]

Un altro modo è, senza il parametro "conta", restituire 1 + la chiamata ricorsiva se l'elemento corrente è quello cercato altrimenti 0 + la chiamata ricorsiva
Bello :) l'importante è che mic85rm capisca la logica

[mic85rm]

ora provo...cmq la funzione iterativa è corretta?

[mic85rm]

int conta_lista(struct item *p,int valore)
{
int conta=0;
if (p==NULL){ return conta;}
if (p->val==valore){conta++;conta_lista(p->next,valore)}
if (p->val!=valore){conta_lista(p->next,valore)}
}

[wingman87]

Nelle chiamate ricorsive non viene conservato il valore di "conta" se non lo passi come parametro.
La versione iterativa ad occhio sembra corretta

[clockover]

Si può fare in 2 righe (come già consigliato da wingman87 nel suo primo post)


se puntatore == NULL return 0;
return (puntatore->val == valore) + chiamata ricorsiva(...)

e ti ho detto anche troppo :D :D

edit:
comunque cerca di capire come funziona la cosa.. per capire bene usa carta e penna

[british]

Che cos'è un libro? un insieme ordinato di capitoli. Oppure? un capitolo seguito eventualmente da un altro libro.
Che cos'è un treno? Un insieme ordinato di vagoni. oppure? un vagone eventualmente seguito da un altro treno.

Quindi, se un vagone è lungo 1, quanto è lungo un treno?
1 (il primo vagone) + la lunghezza del treno "rimanente".. e quest'altro treno quanto è lungo? 1 + la lunghezza del suo treno "rimanente"... e quando arrivo all'ultimo vagone che non ha più niente attaccato? questo è il cosiddetto "passo base": 1 +0.

ciao!

british