View Full Version : Funzione Ricorsiva in C
Salve a tutti, mi sto affacciando alla programmazione in C da un po' di tempo, ma non riesco a capire come si faccia una funzione ricorsiva, fra gli esempi portava il calcolo del fattoriale, e lì qualcosina c'ho capito, ma del tipo calcolare la somma di un array di interi mi sembra una cosa criptica :eek:
Qualcuno di buon cuore può darmi una mano?
Simonex84
16-02-2015, 11:23
Per esempio
int somma(int A[]; int n)
{
if (n=0) {
return 0
} else {
return A[n] + somma(A, n-1)
}
}
"A" è il vettore
"n" il numero di elementi
La logica è che la somma di un vettore è la somma del primo elemento più la somma del restante pezzo, la somma del restante peezzo, è la somma del primo elemento più la somma del restante pezzo, e così via.... finchè sei arirvato alla fine (return 0) che corrisponde al valore dell'elemento dopo la fine del vettore
Per esempio
int somma(int A[]; int n)
{
if (n=0) {
return 0
} else {
return A[n] + somma(A, n-1)
}
}
"A" è il vettore
"n" il numero di elementi
scusa la domanda da tremendo ignorante, credo già di stare per sparare una stronzata, ma sbagliando si impara :D
return A[n]+somma(A,n-1)
vuol dire prendere l'elemento di A puntato da n e richiamare la funzione somma che andrà a prendere l'elemento n-1 di A?
Simonex84
16-02-2015, 11:36
scusa la domanda da tremendo ignorante, credo già di stare per sparare una stronzata, ma sbagliando si impara :D
return A[n]+somma(A,n-1)
vuol dire prendere l'elemento di A puntato da n e richiamare la funzione somma che andrà a prendere l'elemento n-1 di A?
n quando richiami la funzione indica il numero di elementi, all'interno della funziona viene usato anche come indice.
Leggi l'EDIT che ho aggiunto sopra
Per esempio
int somma(int A[]; int n)
{
if (n=0) {
return 0
} else {
return A[n] + somma(A, n-1)
}
}
"A" è il vettore
"n" il numero di elementi
La logica è che la somma di un vettore è la somma del primo elemento più la somma del restante pezzo, la somma del restante peezzo, è la somma del primo elemento più la somma del restante pezzo, e così via.... finchè sei arirvato alla fine (return 0) che corrisponde al valore dell'elemento dopo la fine del vettore
Tre appunti:
1) Non controlli se l'indice è negativo (conviene passare un unsigned)
2) A[n] provoca un buffer overflow, in C gli indici degli array vanno da 0 a N-1.
3) Per le variabili è meglio usare nomi con lettere minuscole
int somma(int a[], size_t n)
{
if (n == 0) return 0;
return a[n-1] + somma(a, n-1);
}
Simonex84
16-02-2015, 14:03
Tre appunti:
1) Non controlli se l'indice è negativo (conviene passare un unsigned)
2) A[n] provoca un buffer overflow, in C gli indici degli array vanno da 0 a N-1.
3) Per le variabili è meglio usare nomi con lettere minuscole
int somma(int a[], size_t n)
{
if (n == 0) return 0;
return a[n-1] + somma(a, n-1);
}
ma se do a nasio91 una soluzione perfetta poi lui non deve più fare nulla :D
a parte gli scherzi l'ho buttato giù al volo prima di andare a pranzo, comunque anche la tua non va bene perchè così non sommi l'elemento in prima posizione a(0)
così invece dovremmo esserci
int somma(int a[], int n)
{
if (n < 0) return 0;
return a[n-1] + somma(a, n-1);
}
ma se do a nasio91 una soluzione perfetta poi lui non deve più fare nulla :D
a parte gli scherzi l'ho buttato giù al volo prima di andare a pranzo, comunque anche la tua non va bene perchè così non sommi l'elemento in prima posizione a(0)
...
Aspetta eh... fammici pensare :D.
Quando n = 1 prendo a[0], quindi in teoria dovrebbe funzionare.
La cosa più semplice per capirlo è considerare che n indica il numero di elementi da sommare.
Quindi mi sa che la mia è ancora valida :D.
Cmq spero che i nostri ragionamenti aiutino nasio a capire.
Aspetta eh... fammici pensare :D.
Quando n = 1 prendo a[0], quindi in teoria dovrebbe funzionare.
La cosa più semplice per capirlo è considerare che n indica il numero di elementi da sommare.
Quindi mi sa che la mia è ancora valida :D.
Cmq spero che i nostri ragionamenti aiutino nasio a capire.
quando n==1 chiami somma(a,0)
ma in quest'ultima chiamata fai il check if n==0 e restituisci subito 0, non il contenuto di a[0]
quindi correggendo (io non lo scriverei mai così) sarebbe:
int somma(int a[], size_t n)
{
if (n == 0) return a[n];
return a[n-1] + somma(a, n-1);
}
resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema :asd:
wingman87
16-02-2015, 17:55
Quando n=1 return a[n-1] + somma(a, n-1) cioè a[0] + somma(a, 0) cioè a[0] + 0 quindi è corretto
Simonex84
16-02-2015, 17:59
resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema :asd:
in questo esempio usare la ritorsione è una forzatura a scopo didattico (userei anche io un ciclo), però è bene prenderci la mano perché una tecnica di programmazione molto utile
quando n==1 chiami somma(a,0)
ma in quest'ultima chiamata fai il check if n==0 e restituisci subito 0, non il contenuto di a[0]
...
E dev'essere così.
L'ultimo passo rimane: a[0] + 0, che quindi è corretto ;).
resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema :asd:
Chiaro, ma l'autore del thread voleva delucidazioni sulla versione ricorsiva.
Al di là della questione sugli indici del vettore restituito, il problema credo sia un altro, ovvero che ti concentri troppo sull'aspetto implementativo e poco sull'aspetto matematico. Devi provare a scrivere la funzione ricorsiva prima in termini matematici e poi vedrai che tradurla in qualsiasi linguaggio di programmazione diventa un problema banale.
Il fattoriale, che già ti è chiaro può essere definito come
factorial 0 = 1
factorial n = n * factorial (n - 1)
Quello che ho scritto è codice Haskell, ma ho fatto questa scelta semplicemente perché è un linguaggio molto ad alto livello con una notazione vicinissima a quella matematica.
Il codice significa la seguente cosa. Il fattoriale di 0 è uguale 1, mentre il fattoriale di un generico numero n è uguale a n moltiplicato il fattoriale di n-1. Mi sembra piuttosto semplice da interpretare.
Personalmente sono abituato a scrivere prima il caso generale (la seconda riga dell'esempio) e poi il caso base (la prima riga). Questo perché in pratica il caso base serve come condizione di arresto della ricorsione. Ripeto, è solo un consiglio e non una regola.
Il tuo problema di calcolare la somma di un vettore può quindi essere risolto come:
sum [] = 0
sum (head:tail) = head + sum tail
Considerando che (head:tail) scompone il vettore affinché head contenga la testa del vettore, ovvero il primo elemento, e tail la sua coda, ovvero tutti i restanti elementi, nel seguente esempio abbiamo:
vettore = [3,5,6,7,8,2]
quindi
head = 3
tail = [5,6,7,8,2]
La funzione ricorsiva della sommatoria di un vettore, può quindi essere pensata nel caso generale come la somma del primo elemento più la sommatoria della parte restante del vettore. Il caso base ovviamente è quello della lista vuota la cui somma assumiamo sia 0.
Questo è quello che dovrebbe essere il tuo modo di pensare, ad alto livello aiutandoti con una notazione vicina a quella matematica.
Ora purtroppo per te implementare questa funzione ricorsiva in C non può essere fatto in maniera diretta usando i vettori, quindi quello che si fa è usare un contatore che scorre il vettore durante la ricorsione.
Usando uno pseudo-codice simile a quello usato finora, ma più vicino al C:
sum vect index =
if index < 0
return 0
else
return vect[index] + sum vect (index-1)
Ho fatto questo giro lunghissimo e forse un po' complicato per mostrarti quello che dovrebbe essere il tuo modo di ragionare.
Per questo problema, come sottolineato anche da altri utenti, la ricorsione è un po' una forzatura, soprattutto perché l'implementazione in C con vettori forza l'uso di un contatore.
Al contrario, usando un altro linguaggio che supporta nativamente le liste il codice sarebbe risultato pressoché identico a quello che ho scritto prima in Haskell.
Ad esempio in Python:
def sumList(list):
if len(list)==0:
return 0
else:
return list[0] + sumList(list[1:])
Come vedi, se trascuri la sintassi, la logica è esattamente la stessa. Nota che list[1:] è l'equivalente del tail definito in precedenza.
Quando n=1 return a[n-1] + somma(a, n-1) cioè a[0] + somma(a, 0) cioè a[0] + 0 quindi è corretto
E dev'essere così.
L'ultimo passo rimane: a[0] + 0, che quindi è corretto ;).
si è vero, avevo letto male
in questo esempio usare la ritorsione è una forzatura a scopo didattico (userei anche io un ciclo), però è bene prenderci la mano perché una tecnica di programmazione molto utile
Chiaro, ma l'autore del thread voleva delucidazioni sulla versione ricorsiva.
altrettanto chiaro che fosse una battuta, o quando leggete non parsificate le emoticon? [segue faccina "asd"] :asd:
vbextreme
19-02-2015, 20:32
int somma(int v[], int n)
{
return ( --n ) ? v[n] + somma(v,n) : v[n];
}
Simonex84
20-02-2015, 07:11
int somma(int v[], int n)
{
return ( --n ) ? v[n] + somma(v,n) : v[n];
}
per utente alle prime armi io userei un codice più "semplice" e meno sintetico
per utente alle prime armi io userei un codice più "semplice" e meno sintetico
Yep è un po criptica come codice... Grazie comunque a tutti ragazzi! Chiarissimi e disponibili :)
sottovento
03-03-2015, 09:31
int somma(int v[], int n)
{
return ( --n ) ? v[n] + somma(v,n) : v[n];
}
Ovviamente assumendo che n > 0. Per n == 0 va in crash.
sottovento
03-03-2015, 09:35
così invece dovremmo esserci
int somma(int a[], int n)
{
if (n < 0) return 0;
return a[n-1] + somma(a, n-1);
}
Andrai in crash per n == 0. Quella che aveva scritto warduck era invece corretta:
int somma(int a[], size_t n)
{
if (n == 0) return 0;
return a[n-1] + somma(a, n-1);
}
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.